Linked_List

 2021/06/24 

Linked list

Linked list是一種常見的資料結構，利用指標的指向來得到下一個資料，那為什麼要用Linked list呢？為何不使用array就好，接下來說說Linked list的優缺點。

優點：

Linked list和array不一樣的地方就是Linked list可以動態配置大小，而array的大小是固定的，接著Linked list要新增或刪除元素都比較方便快速。

缺點：

Linked list是沒有index的，所以在搜尋資料中會相對的耗時。

接著來看看Linked list的樣子大概長怎樣，我們每個node都有一個記憶體位置，而它所存取的內容會有資料以及下一個node的記憶體位置，而最後一個node存取的記憶體位置為NULL，這樣一個Linked list就結束了，看看圖增加印象吧！

建立兩個節點:

#include <stdio.h>
#include <stdlib.h>
typedef struct linked_list *link_ptr;
typedef struct linked_list{
    int data;
    link_ptr add;
};
int main(){
    link_ptr vertex1 = NULL;
    link_ptr vertex2 = NULL;
    vertex1 = malloc(sizeof(linked_list));
    vertex2 = malloc(sizeof(linked_list));
    vertex2->add = NULL;
    vertex2->data = 100;
    vertex1->add = vertex2;
    vertex1->data = 10;
    printf("%d\n", vertex1->add->data);
    printf("%p\n", vertex2);

    return 0;
}

我們這裡使用C語言撰寫，首先建立一個結構叫linked_list，接著宣告一個結構指標叫做link_ptr，在main裡我們利用link_ptr來宣兩個變數，分別初始化為NULL，由於我們使用link_ptr宣告，代表vertex1和vertex2也是指標結構，同時擁有資料和下一個位置的記憶體位置，接著我們使用malloc()做動態記憶體配置，由於vertex2是最後一個元素，所以它指向NULL，而vertex1則指向vertex2，即完成linked list。 ## 例子:

#include <stdio.h>
#include <stdlib.h>
typedef struct linked_list *l_ptr;
typedef struct linked_list{
    int height;
    l_ptr ptr;
};
void print(l_ptr person){
    while(person != 0){
        printf("%d\n",person->height);
        person = person->ptr;
    }
}
int main(){
    l_ptr first = NULL;
    l_ptr Max = NULL,Tom = NULL;
    Max = (l_ptr)malloc(sizeof(linked_list));
    Tom = (l_ptr)malloc(sizeof(linked_list));
    Max->height = 171;
    Max->ptr = Tom;
    first = Max;
    Tom->height = 180;
    Tom->ptr = NULL;
    //在Max和Tom之間插入一個Kevin
    l_ptr Kevin = NULL;
    Kevin = (l_ptr)malloc(sizeof(linked_list));
    Kevin->ptr = Max->ptr;
    Max->ptr = Kevin;
    Kevin->height = 165;
    print(Max);
    
    free(Max);
    free(Tom);
    free(Kevin);

    return 0;
}

這裡運用到的觀念和上面一個一樣，這邊只是運用例子使它更容易明白，這邊唯一不同的地方是我用free()來釋放記憶體位置，在C++是使用delete，這麼做是因為如果不要使用此資料的時候沒有將它釋放會造成記憶體的浪費。

by 中和高中吳振榮

Next Post

ctime
Previous Post

Stringstream

CATALOG

1. Linked list

Linked_List

Linked list

優點：

缺點：

建立兩個節點:

by 中和高中 吳振榮

by 中和高中吳振榮