对于单向链表，是否总是必须添加一个新节点作为第一个元素？

Question

通常在单向链表中，您是否总是添加一个新元素作为 head.next，换句话说作为第一个元素？或者你走到列表的末尾并将它添加到那里？

Answer 1

两种方式都可以，但出于性能原因，通常首选在前面插入。

插入一个新元素作为头部非常快，O(1)，因为你只需要创建一个元素和一个指向旧头部的指针。

在末尾插入意味着遍历列表以找到最后一个元素并更新它指向新元素的指针。这是 O(n)。

您也可以通过跟踪列表的尾部并在末尾进行 O(1) 插入来用时间换取存储。但是你得到了比单向链表更复杂的东西。

通常排位赛

当我说 usually 时，我指的是手工制作的单向链表，尤其是用 C 编写的，也许对于某些 space 处于溢价和额外的 space 来存储尾巴太多了。

对于通用语言，比如 Java，LinkedList 实现存储尾部，因此两个操作都是 O(1)。有趣的是，在 Java 的情况下，List 的抽象接口只定义了一个追加到列表的操作。

一个实现（在伪 C 中）

假设我有一些列表，例如

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

如果我想在开头插入，我会写

List* insert(List *original_list, int data) {
    List* head = allocate new List(data, original_list);
    return head;
}

如果我想追加，我会写

void append(List *original_list, int data) {
    List* new_tail = allocate new List(data, null);
    ptr = original_list
    while(ptr->next != null)
        ptr++
    ptr->next = new_tail;
}

Answer 2

正如@munk 所说，任何一种方式都是可能的。但是，插入的时间复杂度可能因您使用的结构而异。让我更清楚。

让我们使用 C 语言只是为了让它简单明了。实现单个链表的一种可能方法是：

typedef struct node {
    int foo;
    node_t* next;
} node_t;

typedef struct list {
    node_t* head;
} list_t;

这样，您首先创建一个结构node来存储您要存储的信息，然后声明第二个结构list，它仅包含指向第一个节点的指针列表，即 head。使用此实现：

在开头插入需要 O(1) 时间（您只需更改 head 字段并使用 next 进行一些调整。
最后插入需要 O(n) 时间，因为您必须遍历整个列表。

实现单链表的第二种方式是这样的：

typedef struct node {
    int foo;
    node_t* next;
} node_t;

typedef struct list {
    node_t* head;
    node_t* tail;
} list_t;

您维护一个指向列表的 last 元素的指针，这使得最后的插入也需要 O(1) 时间。但是，这种实现比另一种占用更多space。

Answer 3

根据斯坦福大学的 this lecture（在 13:00 分钟后），将 walk 添加到列表的末尾并在那里添加新节点。这是代码的屏幕截图 (C++)

在 lecture notes from UC Berkley (Java) 中，他们将其添加为第一项，但随后他们明确地将其调用为 insertFront()

public class SList {
  private SListNode head;             // First node in list.
  private int size;                   // Number of items in list.

  public SList() {                    // Here's how to represent an empty list.
    head = null;
    size = 0;
  }

  public void insertFront(Object item) {
    head = new SListNode(item, head);
    size++;
  }
}

在LinkedList class in java framework（这是双向链表）中，just add表示添加到链表的末尾。因此，如果您添加 1，则添加 2，然后添加 3，则 3 将是列表中的最后一项。

简而言之： 除非明确调用 addFront（或类似的东西），否则添加到 LinkedList 上，意味着作为最后一项添加。

对于单向链表，是否总是必须添加一个新节点作为第一个元素？

For a singly linked list, does a new node always have to be added as the first element?

singly-linked-list