链表：使用尾指针在末尾插入节点

Question

链表：使用尾指针在末尾插入节点

3

我正在学习链表，并想知道我编写的以下程序（基本上是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）是否有更有效和简单的算法来插入元素到末尾？能否指导我去查看相关资料？

- Naruto Uzumaki

谢谢大家。你们的回答非常有帮助。你们提供了很多我没有考虑过的观点。现在对我来说选择一个最佳答案变得困难了 :) 所以我会选择得票最多的答案。再次感谢。 - Naruto Uzumaki

我还想问一件事。你说我不需要一个返回语句。那么我怎样退出这个 "if" 语句呢？我的意思是，如果我传递了一个空列表，那么 if 语句会执行，但是如果我不返回 0，那么下面的两个语句也将被执行。对吗？我想我应该把最后两行代码放在 else 块中。这样是否就足够了？或者我犯了一个逻辑错误？ - Naruto Uzumaki

1

将该函数的剩余部分放在if语句的else{}分支中确实可以起作用。 - Chowlett

1

你应该创建一个结构体，将起始和结束组合在一起。 - alternative

6个回答

2

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

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

- Oliver Charlesworth

2

a) 没有检查malloc的结果。在低内存条件下，它可能会返回NULL，导致崩溃。我相信算法的其余部分是正确的。

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

- Dominik Weber

2

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

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

b) 除了为每个节点分配内存之外，当然可以。这是您的设计决策，但不同的解决方案将更加复杂，超出了本练习的范围。

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

c) 不。它是O(1)。如您所见，没有循环或任何其他内容，无论列表中有5个还是5000个元素，您都执行完全相同的步骤。

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

- EboMike

1

抱歉，这并不是回答问题的方法，但我认为你可能会发现它有用。我提供一种略微不同的方法：

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> ***

开始变得有点傻了，注意一下。

- ijw

谢谢！非常有帮助。在InsertAtEnd函数中，可以不用创建指向LAST指针的指针，而是将LAST指针作为按值调用传递，然后在InsertAtEnd函数中：InsertAtEnd(struct node** lastref,int i)。这将创建一个指向节点的下一个指针而不是LAST指针/变量的指针。现在，我没有足够的经验来想出这个解决方案，但我在Nick Parlante的论文《链表基础》的第20页找到了我刚才告诉你的解决方案。 - Naruto Uzumaki

2

我改变了lastref指向的->next（或HEAD）指针的内容，然后我改变了lastref本身的内容。他也是这样做的 - 这是相同的解决方案。不同之处在于他没有在函数中更新lastref指针，而是在循环体中执行。额外的'*'是必需的参数，以便您可以从函数内部更新lastref。 - ijw

1

对于普通读者，我在http://cslibrary.stanford.edu/103/LinkedListBasics.pdf找到了这篇论文。 - ijw

1

a) 我认为你的代码在实现你期望的功能方面是正确的。你可能需要检查malloc的返回值。

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

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

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

当我实现这样的东西时，我个人只做以下几件事：

为整个链表数据结构创建一个自己的结构（包含size和head和lastElement指针）
我不会限制列表仅包含整数，而是任意元素（因此是void*）

- phimuemue

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- vulkanino · Accepted Answer

a) 这似乎是正确的。

b) 是的。你可以使函数返回void，因为你不需要那个int返回值。

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

d) malloc需要时间。你可以使用缓冲技术，在预先malloc一块节点的情况下从缓冲区中取出下一个节点。当缓冲区变为空时，分配另一块。块的尺寸可以配置甚至（复杂）使用统计算法进行计算。

此外，你没有检查malloc的NULL返回值，但它可能失败。