single linked list

本文关键字：list linked single | 更新日期: 2023-09-27 17:49:01

Internet上可用的一些示例对单个链表使用头节点和尾节点，而有些示例不知道为什么会有这样的差异。

single linked list

尾部节点使得将一个项目附加到列表末尾的操作为O(1)，而不是在附加之前必须从头部一直迭代到尾部，使其成为O(n)操作。因此，它有助于提高效率，但并不是制作可用列表的根本要求。我怀疑例子的区别在于学术纯粹和拥有一个相对有用的列表。

这将是完全没有意义的有一个单链表没有记住头节点虽然:)

保留头和尾的原因主要是当列表需要在列表末尾添加新项时速度。

虽然查找列表的末尾很简单，但与在列表修改期间跟踪它所花费的精力相比，它花费的时间太多了。

单链表使用更少的空间-每个单元格少1个指针。它也更有效地添加到列表的头部和从列表的前半部分删除(更少的操作，因为不需要维护另一个链接)。

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

在广泛使用列表的Lisp中，只使用单链表。实际上，有些实现(如Symbolics)在列表小于一定长度时使用数组。

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

正如其他人指出的那样，尾部引用提供了一种在常量时间内将节点附加到列表末尾的方法。如果链表实现没有尾部引用，则必须遍历列表中的所有节点，以便将其添加到末尾。下面是一个java链表示例，使用3种不同的方法向列表添加元素。

  • push(Node Node) -将节点添加到列表的开头。由于头部引用，这需要常数时间O(1)。
  • add(int index, Node Node) -添加指定索引处的节点。这需要O(n)时间，因为它必须遍历每个节点直到找到正确的索引。

  • add(Node Node) -将节点添加到列表末尾。如上所述，由于使用的是尾部引用，因此此操作只需要常量时间。

    // 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++;
}

添加尾部引用显著减少了在链表末尾插入元素的时间。请查看我的博客，了解在Java、c++、Python和JavaScript中使用尾部引用的链表实现。

相关文章：