单个链接列表

Question

互联网中可用的一些示例使用单个链接列表的头部和尾部节点，并且一些示例并不表示为何存在这种差异。

Answer 1

尾节点使它O（1）将一个项目附加到列表的末尾，而不必在追加前从头部一路迭代找到尾部，使其成为O（n）操作。因此它对提高效率非常有用，但从根本上不需要制定可用的清单。我怀疑例子中的不同之处在于学术的纯粹性和具有相对有用的名单之间。

这将是毫无意义的有一个单向链表，无需记住头节点虽然:)

Answer 2

之所以保持头部和尾部，主要是速度时，列出需要增加新项目结束的名单。

虽然查找列表的末尾很简单，但与花费在记录列表修改期间的费用相比，花费的时间太多。

Answer 3

单链表使用较少的空间 - 每个单元少一个指针。添加到列表头并从列表的前半部分删除（因为不需要维护另一个链接，所以操作更少）也更有效。

双链表对于删除或添加列表的后半部分更有效。

在Lisp中，广泛使用列表，只使用单链表。实际上，如果列表比特定长度短，某些实现（如Symbolics）会使用数​​组。

要使用哪个选择取决于应用程序。如果追加是常见的操作，并且速度比空间更重要，那么双向链接列表可能是合适的。但是，我认为单链表在大多数情况下更合适，因此更常见。

Answer 4

正如其他人指出的那样，尾部引用提供了一种在常量时间内将节点附加到列表末尾的方法。如果您的链接列表实现没有尾部引用，则必须迭代列表中的所有节点才能将其添加到最后。下面是一个Java链接列表示例，它使用3种不同的方法将元素添加到列表中。

• push（节点节点） - 将节点添加到列表的开头。由于头部参考，这需要恒定的时间O（1）。
• add（int index，节点节点） - 在指定索引处添加节点。这需要O（n）时间，因为它必须迭代每个节点直到找到正确的索引。

• add（节点节点） - 将节点添加到列表的末尾。如上所述，由于我们使用尾部参考，因此此操作只需要一段时间。

  // Insert element at the beginning of the list 
  public void push(T _data) { 
  
      Node<T> addNode = new Node<T>(_data); 
  
      // Set head and tail to new pointer if list is empty 
      if(this.head == null) { 
       this.head = addNode; 
       this.tail = addNode; 
      } else { 
       addNode.setNext(this.head); // Set new node's next pointer to the current head 
       this.head = addNode; // Set head to new node 
      } 
  
      this.numberNodes++; 
  } 
  
  // Insert element at the specified index 
  public void add(int _index, T _data) { 
  
      // Continue if _index is valid 
      if(_index >= 0 && _index <= this.numberNodes) { 
  
       if(_index == 0) { // Push element to front of list if _index is 0 
        this.push(_data); 
       } else if(_index == this.numberNodes) { // Add element to end of list if index is last element 
        this.add(_data); 
       } else { 
  
        // Continue if list is not empty 
        if(this.head != null && this.tail != null) { 
  
         Node<T> addNode = new Node<T>(_data); 
         Node<T> currentNode = this.head.getNext(); 
         Node<T> previousNode = this.head; 
  
         int count = 1; 
         while(currentNode != null) { // Traverse list to find element at _index 
  
          // Insert element when _index is found 
          if(count == _index) { 
           previousNode.setNext(addNode); 
           addNode.setNext(currentNode); 
           this.numberNodes++; 
           break; 
          } 
  
          // Prepare for next iteration 
          previousNode = currentNode; 
          currentNode = currentNode.getNext(); 
          count++; 
         } 
        } 
       } 
      } 
  } 
  
  // Insert element at the end of the list 
  public void add(T _data) { 
  
      Node<T> addNode = new Node<T>(_data); 
  
      // Set head and tail to new pointer if list is empty 
      if(this.head == null) { 
       this.head = addNode; 
       this.tail = addNode; 
      } else { 
       this.tail.setNext(addNode); // Set tail's next pointer to new node 
       this.tail = this.tail.getNext(); // Set tail to new node 
      } 
  
      this.numberNodes++; 
  } 
  

添加尾参考急剧下降到插入在一个链表的末端元件的时间。查看my blog的链接列表实现，使用Java，C++，Python和JavaScript中的尾部引用。