單鏈表尾

Question

，如果你想創建一個單向鏈表是這樣的：

struct Node { 
    int data; 
    Node *next; 
}; 

struct List{ 
    Node *head; 
    // Node *tail; --> necessary? 
    Node *last; 
}; 

而且這個名單有辦法「追加」，「刪除」，「的printList」和「findElement」。 是否需要尾巴？因爲使用「last」，你可以尋址最後一個節點。

那麼當所有三個節點都需要「頭」，「尾」和「最後」時呢？例如，當你想插入排序到列表中的節點時？

Answer 1

不，這不是必要的。尾部等於head->next，因此它將是多餘的，並增加簿記開銷以保持該字段更新。

另請注意，字段last是一種不尋常的。在大多數使用情況下，您需要將元素添加到單個鏈接列表的頭部，並在真正需要添加到結尾時使用不同的數據結構。

Answer 2

這不是必須的，但是如果您使用隊列式FIFO方式而不是堆棧式LIFO方式處理鏈接列表，或希望能夠從一個列表中移除整個元素列表在不破壞元素的相對順序的情況下轉向另一個人的尾巴。

請注意，我指的是'尾部'作爲列表中最後一個節點的引用，我相信這是安全的假設問題是關於。

很多非常微優化的SLL實現通常是無尾的，並且像堆棧一樣工作，同時由有效的固定分配器支持引用的地方性（緩存友好性）和更快的節點分配/釋放。 SLL相對於基於陣列的可變大小的序列的主要優勢在於只需更改指針/引用的next指針/引用的值即可開始移動，並且在您正在工作時插入/刪除元素時缺少無效在涉及指針的本地低級語言中。缺少尾部可以通過減少操作中推送和彈出堆棧所需的分支指令的數量來提高性能。

對於您列出的需求，尾部是否會幫助或者只是增加不必要的複雜性和開銷，如果您的操作可以嚴格地從LIFO堆棧方式的前端工作，或者如果您希望能夠追加到後面，但以前進的方式從FIFO中移除而不需要任何迭代，例如如果在後一種情況下沒有尾部，這些操作之一將從恆定時間複雜度變爲線性時間複雜度，並且可以通過交換相對線性時間算法複雜度來改善您的使用情況保持尾巴的較小微觀開銷。

Answer 3

我認爲這取決於你想使用什麼操作。

1. 假設你想插入和在列表的尾部刪除節點，它無疑是一個明智的選擇，以保持最後的節點在列表中。

2. 否則，如果您想在列表開始處執行操作，則不需要最後的節點。

Answer 4

其實，你可以實現排隊（附加在尾部），推（在頭前置），出隊（從頭部取出），當然找到並用一個終場頭打印。訣竅是使列表成爲循環，並將標題指向尾部。然後tail->next是頭。

#include <stdio.h> 
#include <stdlib.h> 

typedef struct node_s { 
    struct node_s *next; 
    int data; 
} Node; 

typedef struct list_s { 
    Node *tail; 
} List; 

Node *new_node(int data) { 
    Node *node = malloc(sizeof *node); 
    node->data = data; 
    node->next = node; 
    return node; 
} 

void init_list(List *list) { 
    list->tail = NULL; 
} 

int is_empty(List *list) { 
    return list->tail == NULL; 
} 

void enqueue(List *list, Node *node) { 
    if (list->tail) { 
    Node *head = list->tail->next; 
    node->next = head; 
    list->tail->next = node; 
    list->tail = node; 
    } else list->tail = node->next = node; 
} 

void push(List *list, Node *node) { 
    if (list->tail) { 
    Node *head = list->tail->next; 
    node->next = head; 
    list->tail->next = node; 
    } else list->tail = node->next = node; 
} 

Node *dequeue(List *list) { 
    Node *head = list->tail->next; 
    if (head == list->tail) 
    list->tail = NULL; 
    else 
    list->tail->next = head->next; 
    return head; 
} 

void print_list(List *list) { 
    printf("The list:\n"); 
    if (list->tail) { 
    Node *head = list->tail->next; 
    Node *p = head; 
    do { 
     printf("%d\n", p->data); 
     p = p->next; 
    } while (p != head); 
    } 
} 

int main(int argc, char *argv[]) { 
    List list[1]; 
    init_list(list); 

    // Build the list in order and print it. 
    for (int i = 0; i < 4; i++) enqueue(list, new_node(i)); 
    print_list(list); 

    // Remove elements from head until empty. 
    printf("Dequeueing:\n"); 
    while (!is_empty(list)) { 
    Node *node = dequeue(list); 
    printf("%d\n", node->data); 
    free(node); 
    } 

    // Build the list in reverse order and print it. 
    for (int i = 0; i < 4; i++) push(list, new_node(i)); 
    print_list(list); 

    return 0; 
}