鏈接列表邏輯

Question

我對理解鏈表的流程有點麻煩。

我有我的列表和它的節點的這些類型定義。

typedef struct node node_t; 

struct node{ 
    data_t data; 
    node_t *next; 
}; 

typedef struct { 
    node_t *head; 
    node_t *foot; 
} list_t; 

list_t *insert_at_foot(list_t *list, data_t value) { 
    node_t *new; 
    new = malloc(sizeof(*new)); 
    assert(list!=NULL && new!=NULL); 
    new->data = value; 
    new->next = NULL; 
    if(list->foot==NULL){ 
     //this is the first insertion into the list 
     list->head = list->foot = new; 
    }else{ 
     list->foot->next = new; 
     list->foot = new; 
    } 
    return list; 
} 

Specificly下面

if(list->foot==NULL){ 
    //this is the first insertion into the list 
    list->head = list->foot = new; 
}else{ 
    list->foot->next = new; 
    list->foot = new; 
} 

這個代碼，我得到我們分配頭和腳節點「新的」，因爲它是第一個節點，但我不明白以下行。這似乎對我來說，如果我們在分配這筆新的節點列表的末尾（到腳），

list->foot->next = new; 

應該是，

list->foot->next = NULL; 

我只是不明白了吧分配腳指針和它的下一個指針到同一節點（新）

這一直在擾亂我，因爲這個概念很容易理解。

Answer 1

如果我們沒有列表的尾部，在鏈表的末尾插入O（n）。如果我們只有列表的頭部，我們應該遍歷列表並找到結尾，並將該項目插入列表的末尾（以防止我們要保留插入順序）。爲了避免這種情況，人們通常會保留列表的尾部。例如，如果您的列表是1-> 2-> 3並且您想要在列表中添加4。在這種情況下，頭部是1，尾部是3。所以

list->foot->next = 4 

意味着我們的列表將是1-> 2-> 3-> 4和下一行list->foot = new;分配尾（腳）至4，以確保對於另一插入我們有更新的尾部（腳丫子）。

Answer 2

你打什麼是簡單鏈表和一個叫做循環鏈表細化的區別。由於模糊描述了一個簡單的列表，通常分別保留附加的1或2個指針（HEAD）或（HEAD, TAIL），分別保存列表的開始節點（HEAD）和當前結束節點（TAIL）。 HEAD/TAIL有什麼意義？

簡單的答案是雙重的。 （1）它允許在列表的開始或結束處添加節點的永久引用，以及（2）它們提供用於遍歷列表的開始和結束點。但是你必須讓他們實現一個鏈表嗎？ 號

一個循環鏈表無需通過讓end->next點first（因而名字保留任何HEAD,TAIL指針（S）圓形鏈表。我都用了，並迅速放棄了HEAD,TAIL簡單列表，轉而使用圓形鏈表。爲了獲得好處，你可以添加額外的指針node->prev並使列表成爲圓形雙鏈表它保留了訪問HEAD & TAIL的能力節點沒有迭代。

是一個比簡單列表難以實現的循環列表 - >沒有，它只需要不同的add_node函數。讓我們來看看。顯示簡單和圓形列表之間的關係和區別的圖幫助（如圖所示的雙鏈表）：

   Tail     Current    Head 
     (node->prev)    node    (node->next) 
     +------------+  +------------+  +------------+ 
     | payload |  | payload |  | payload | 
     +------------+  +------------+  +------------+ 
+<------| prev  |<-------| prev  |<-------| prev  |<------+ 
|  +------------+  +------------+  +------------+  | 
| +--->| next  |------->| next  |------->| next  |--->+ | 
| | +------------+  +------------+  +------------+ | | 
| |                 | | 
| +<--------------------<---------------------<----------------------+ | 
|                  | 
+------------------------>--------------------->------------------------>+ 

如果你仔細觀察，你會看到一個簡單和圓形列表中的所有實際用途都完全相同，但是，在簡單的列表中，您的必須跟蹤您的HEAD,TAIL指針，但對於圓形列表，實施的邏輯會爲您追蹤它們。這就是區別，這就是爲什麼你的問題的答案：分配HEAD,TAIL指針的重點？只是爲了提供插入新節點和迭代的開始和結束點。如果您在實施過程中很聰明，那麼您不必擔心分配它們，您的列表邏輯會爲您保留跟蹤。考慮到這一點，下面是一個實現循環列表的示例，無需跟蹤HEAD,TAIL。

爲您的數據結構，你會通常有：

typedef struct list { 
    char *data; 
    struct list *prev; 
    struct list *next; 
} list; 

然後你有你的功能create node和insert node末。 注：的insert node函數調用create node，但都可以在insert node如果你選擇：

list *create_node (char *str) { 

    list *node = NULL; 

    node = malloc (sizeof (struct list)); /* allocate memory for new node  */ 
    node-> data = strdup (str);    /* allocate and save payload data */ 

    return node;       /* return node poiter to add to list */ 
} 

list *insert_at_end (list **ll, char *str) { 

    /* create the node and allocate memory for node and payload 
    if no list, then create and assign as list address 
    else, insert new node at end of list */ 

    list *node = NULL;    // create a new node pointer for list 

    node = create_node (str);  // allocate new node and fill payload 

     /* now just Wire/Rewire list pointers to accept node */ 

    if (!*ll) {      // this is the first node 

     node-> next = node;   // circular linked-list 
     node-> prev = node;   // set next, prev = node 
     *list = node;     // set *list = node (adding node to list) 

    } else {      // add - insert new node at end 

     node->next = *ll;    // set node->next to list 
     node->prev = (*ll)->prev;  // set node->prev to list->prev 
     node-> prev-> next = node;  // set (old end)->next to this node 
     (*ll)-> prev = node;   // set list->prev to node 
    } 
    return node;     // return pointer to current node for convenience 
            // (immediate reference) and to test success 
} 

在你main()完成後，你只需類似於：

list *mylist = NULL; 
int i = 0; 

// add data to your list (example using argv entries) 
for (i = 0; i < argc; i++) 
    insert_at_end (&mylist, argv[i]); 
... 

希望這有助於你的理解。無論您使用的是簡單或圓形，單或雙鏈表，只要確保你明白爲什麼每個分配所取得的邏輯和。這只是一個指針遊戲。它們都是簡單的數據結構，但它們確實需要一個陡峭而短暫的學習曲線。花一些時間來學習一下，從那時起他們就會很好地爲你服務。網上有許多教程和howto，用於簡單和循環列表。現在知道不同之處，它會讓你更容易找到你所需要的東西。