链接列表逻辑

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，用于简单和循环列表。现在知道不同之处，它会让你更容易找到你所需要的东西。