链表：使用最后一个指针插入到末尾

Question

我正在学习链表，并且想知道我为在列表末尾插入元素而编写的以下程序（基本上是 InsertAtEnd 函数）是否正确。

基本思想是 *HEAD 指向列表的第一个元素，*LAST 指向最后一个元素。这节省了遍历列表的最后一个元素然后添加元素的时间和计算。

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

// Structure for the list element/node
struct node 
{
 int data; // Stores the data
 struct node *next; // Points to the next element in the list.
};

int InsertAtEnd(struct node **, struct node **, int); /*Declaration of the function which 
                                                    inserts elements at the end.*/

int main()
{
 struct node *HEAD=NULL; //Points to the first element in the list.
 struct node *LAST=NULL; //Points to the last element in the list.
 int i=1;

 for(i=1;i<11;i++)
   {
     InsertAtEnd(&HEAD,&LAST,i);
   }
 }

// Function to insert element at the end.
int InsertAtEnd(struct node **headref,struct node **lastref,int i)
 {
   struct node *newnode=malloc(sizeof(struct node)); /*Allocates memory for the newnode 
                                                     and store the address in pointer 
                                                     newnode*/
   newnode->data=i; // Assign value to the data variable of the newnode.
   newnode->next=NULL; // Assign NULL to the next pointer of the newnode.

   if(*headref==NULL) //Checks if the list is empty.
    {
      *headref=newnode; // Places the address of the new node in HEAD pointer.
      *lastref=newnode; // Places the address of the new node in LAST pointer.

       return 0; //Exit function
    }

/* If the list is not empty, then make the next pointer of the present last node point to the new node*/

   (*lastref)->next=newnode;

   *lastref=(*lastref)->next; // Increment LAST to point to the new last node.

    return 0;
}

我想具体问的问题是：

a) 上面在末尾添加元素的代码（即InsertAtEnd函数）是否正确？ （注：我在我的机器上测试过，它按预期工作。但我仍然想向你们确认）

b）代码（InsertAtEnd函数）是否高效？

c)如果我尝试制作更长的列表，代码（InsertAtEnd函数）的效率会受到影响吗？

d)是否有更高效、更简单的算法来在末尾插入元素？你能指引我去找他们吗？

Answer 1

a) 看起来正确

b) 确实如此。您可以使函数返回 void，因为您不需要 int 返回值

c) 否。换句话说，执行时间是恒定的。

d) malloc 需要时间。您可以使用缓冲技术，提前分配一块节点，然后从缓冲区中获取下一个节点。当缓冲区变空时，分配另一个块。可以使用统计算法配置甚至（复杂）计算块尺寸。

此外，您不检查 malloc 的 NULL 返回，但它可能会失败。

Answer 2

该代码与列表的大小无关（除了空的特殊情况），即它是一个恒定时间算法。因此可能很难想出更有效的插入算法。

然而，唯一可以改进的部分是 malloc() 的使用。看起来您正在单独分配每个节点。如果您准备使用比实际需要更多的内存，则可以考虑一次分配多个节点，这样就可以减少对 malloc() 的调用。因此，当您尝试创建节点时，它首先检查池中是否还有空闲节点。如果是，则只需连接指针即可。如果没有，您将需要分配一个新的池。显然，这将需要更复杂的代码。

Answer 3

a) 不检查malloc的结果。它可能在内存不足的情况下返回 NULL，从而导致崩溃。我相信算法的其余部分是正确的。

B+C+D）非常高效； O(1)意味着插入最后一个元素所需的时间是恒定的。事实上我想不出更简单、更高效的算法。

Answer 4

a) 是的，它应该可以工作（假设您的列表永远不会损坏并且 headref != NULL 但 lastref == NULL）。

如果返回值始终为 0，那它还有什么意义呢？

b) 当然，除了为每个节点分配内存之外。这是您的设计决定，但不同的解决方案会复杂得多，并且超出了本练习的范围。

至于函数本身 - 链表的好处是它们的复杂度为 O(1)。现在删除元素是另一回事，除非您有双链表，否则会更慢。

c) 不，它的复杂度是 O(1)。正如您所看到的，没有循环或任何涉及的内容，无论列表中有 5 个还是 5000 个元素，您都执行完全相同的步骤。

d) 您可以通过使用哨兵（即代替 headref 的虚拟节点）来避免检查列表是否为空。您只需将一个节点放置在内存中的某个位置并将 lastref 设置为它即可。现在您不需要将空列表作为特殊情况来处理。

Answer 5

a）我认为你的代码是正确的，因为它做了你期望它做的事情。您可能想检查 malloc 的返回值。

b）我认为你的代码也很高效。我唯一能想到的是 *lastref=(*lastref)->next; 行，我将其替换为 *lastref=newnode;。但我认为几乎每个编译器都会自动优化这一点。

c) 您的方法具有恒定的运行时间 (O(1))，因此添加到更大的列表不会改变运行时间。但是，如果元素连续存储在内存中，则遍历列表可能会更快。

d) 我不认为 insertAtEnd 可以实现得更快。您可以尝试在内存中连续存储元素，并检查 malloc 的返回。

我个人在实现这些东西时唯一做的事情是：

• 为整个链接列表数据结构创建一个自己的结构（保存size和head - 和lastElement-pointers)

• 我不会将列表限制为保存整数，而是保存任意元素（因此 void*s）

Answer 6

抱歉，这并不能回答问题，但我认为您可能会发现它有用。我提供了一个稍微改变的方法：

int InsertAtEnd(struct node ***, int); /*Declaration of the function which 
                                         inserts elements at the end.*/

struct node *HEAD=NULL; //Points to the first element in the list.
struct node **LAST=&HEAD; //Points to the last (NULL) *pointer* in the list.

// Function to insert element at the end.
int InsertAtEnd(struct node ***lastrefref,int i) // no need to pass HEAD
{
    struct node *newnode=malloc(sizeof(struct node)); /*Allocates memory for the newnode 
                                                        and store the address in pointer 
                                                        newnode*/

    // And here we should be checking for errors...

    newnode->data=i; // Assign value to the data variable of the newnode.
    newnode->next=NULL; // Assign NULL to the next pointer of the newnode.

    **lastrefref = newnode; // Put new element at end of list
    *lastrefref=&(newnode->next); // Update last pointer location
}

调用约定失去了一个参数，并且不需要任何条件。如果您想快速访问最后一个列表元素，这会有所损失，因为它并不那么简单。

struct <anything> ***

请注意，开始变得愚蠢了。