1.1 InitList#

本小节首先讲述如何定义一个简易的链表。理解链表的基本构成，是后续掌握其初始化方法（例如递归实现等技巧）的基础。

回顾一下定义：链表（Linked List）是一种线性数据结构，它的每一个元素都是一个独立的节点（Node）对象。这些节点通过“引用”（可以理解为指针）相互连接。“引用”记录了序列中下一个节点的内存地址，从而允许我们从当前节点访问到下一个节点。

• 具体示例代码

  package ListsSinglyLinked;
  
  public class InitList{
      public int first;
      public InitList rest;
  
      public InitList(int f,InitList r){
          first=f;
          rest=r;
      }
      public static void main(String [] args){
          InitList L=new InitList(15,null);
          //System.out.println(L);
  
          L=new InitList(10,L);
          //System.out.println(L);
  
          L=new InitList(5,L);
          //System.out.println(L);
      }
  }

  我们可以从下面的可视化图片中得知，这里5指向10，10又指向了第一个生成的15，并且Frames显示的是15，15 代表 main 函数栈帧中的某个其他变量的值，或者是某个操作的结果。其指向的列表头是5

1.2 从 Naked LinkedLists (InitLists) 到 SLList#

NOTE

这里引入了 SLList (Singly Linked List) 的概念，旨在提供一个更封装、更易用的链表接口。

在上图，我们发现在InitNode中L1，L2分别指向的是存储5，10数值的结构单元，这种将裸露的节点并不方便我们的后续调用，而且时分多余。这时候我们需要借助SLList这个中间人来解决这个问题，我们可以把SLList当作一个优秀的管理员，他可以帮我们规划好其中的节点如何指向下一个节点，而下一个节点又指向其下一个节点，直到没有指向的下一个数据域，此时记作null。

TIP

为什么直接用InitNode有点麻烦？

如果你有一堆这样零散的“小卡片”（或者说一堆散装的火车车厢），让你自己去手动把它们一个一个串起来，还要时刻记住第一张是哪张，哪张连着哪张……这就有点太折腾人了，很容易出错。程序员们觉得这种“裸露”的、需要自己动手精细操作的节点不太好用。

举个例子，这里以《赛博朋克2077》中的中间人概念来讲解：

每个“任务步骤” (InitNode) 本身很简单，只管好自己的信息 (item) 和指向下一个步骤的连接 (next)，但是不够安全，或者步骤过于繁杂。

而“中间人” (SLList) 则运筹帷幄，灵活地组织、调整这些步骤，确保整个“任务”能顺利进行。当用户想知道下一步干嘛，或者想在计划里加点料，都得通过这位 SLList 中间人，来协调这些“任务”的进行。

WARNING

一开始我们可能让大家都能看到中间人的小本上写的第一张是谁，但以后为了更专业、更安全，中间人可能会把这个信息藏起来——也就是设为 private，甚至用一些更高级的技巧比如“哨兵节点”来管理。

用户本身作为一个发布任务的金主，其可以对该任务的步骤进行删减，这也是其addFirst()的作用，我们把这个任务步骤添置到第一步，getFirst()获得到第一个步骤的具体信息。

这样做最大的好处是：我们那些“小卡片”(InitNode) 就可以设计得非常“傻瓜”或者说“单纯”。它们只需要负责两件事：保存好自己的数据 (item)，以及保存好指向下一张卡片的箭头 (next) 就行了，不需要懂任何复杂的逻辑。

所有复杂的组织、添加、查找等“脑力活”，都交给 SLList 这个“中间人”去操心。这样一来，我们作为使用这个卡片串（链表）的程序员，工作就变得轻松、不容易出错了。

1.3 size方法#

这里我们再向ListSinglyLinked包中放入一个方法，名作size()：

public int size(){
    if(this.rest == null){ // or use the rest directly
        return 1;
    }
     return 1 + this.rest.size();
}

考虑到这是递归版本，会增加其空间复杂度到$O(N)$，我们可以自写一个可以计算长度的方法，名作iterativeSize()，以下为其实现：

public int iterativeSize(){
    int totalSize=0;
    InitList p=this;
    while(p!=null){
        totalSize+=1;
        p=p.rest;
    }
    return totalSize;
}

在这里使用的是巧妙运用链表和其下一节点p.rest，这里遍历不会产生额外的堆栈开销。

1.4 get方法#

public int get(int i){
    if(i==0){
        return first;//this.first
    }
    return rest.get(i-1);
}

这儿使用递归来获取链表中第 i 个元素（0-indexed）。

这些方法直接在 InitList 类上操作，用户需要理解其递归结构和手动管理节点，这在进一步地程序编写中为我们带来了一定的麻烦，这时候我们可以自定义一个更为完善的类方法，我们称之为InitNode和SLList，这里引入节点的概念，在 Java 中，当我们说一个 InitNode 对象的 rest 字段“指向”另一个 InitNode 对象时，实际上 rest 存储的是另一个对象的内存地址（或者更准确地说，是一个能够让 JVM 找到该对象的引用）。

package ListsSinglyLinked;

public class InitNode{
    public int item;
    public InitNode rest;
    public InitNode(int itemValue,InitNode  nextNode){
        this.item = itemValue;
        this.rest =nextNode;
    }
}

我们把item称之为数据域，这表示其可以存储许多类型的数据，包括但不限于常用数据类型，也包括引用类型，即它也可以是一个对象。我们把rest称之为指向下一数据域的指针，所以，rest 让我们能够从当前节点“导航”到链表中的下一个完整结构单元。

TIP

后文提到的结构单元我们都默认为由数据域和指针域组成的结构。

package ListsSinglyLinked;

/**
 * @author Mongxin
 */
public class SLList{
    /**Dear User,it is incredibly important that you do not touch this.*/
    public InitNode first;
    //Using private access modifiers is more than using public access modifiers.

    /**Creates a new SLList with a item,namely x.*/
    public SLList(int x){
        first=new InitNode(x,null);
    }

    /**Adds items x to the front of the list*/
    public void addFirst(int x){
        first=new InitNode(x,this.first);
    }

    /**Gets the first item in the list.*/
    public int getFirst(){
        return this.first.item;
    }

    public static void main(String[]args){
        SLList t=new SLList(5);
        t.addFirst(10);
        System.out.println(t.getItems());
    }
}

1.5 add方法#

// SLList.java
public class SLList<Item> {
    private static class Node<Item> { // 通常是内部类
        public Item item;
        public Node<Item> next;
        public Node(Item i, Node<Item> n) {
            item = i;
            next = n;
        }
    }
    private Node<Item> first; // point the first Node , which will replace by a later the Sentinel Node 
    private int size;

    public SLList(){//constructor
        first=null;
     	size=0;
    }
    
    public SLList(Item x) {
        first = new Node<>(x, null);
        size = 1;
    }
    
    public void addFirst(Item x) {
        first = new Node<>(x, first); // new Node point the old first，and will be the new first
        size += 1;
    }
    
     /**
     * Adds an item to the end of the list.
     * @param item the item to add to the end of the list.
     */
    public void addLast(T item){
        Node<T> newNode=new Node<>(item,null);

        if(first==null){
            first=newNode;
        }else{
            Node<T> p= first;
            while(p.next!=null){
                p=p.next;
            }
            p.next=newNode;
        }
        size++;
    }

    // ... another methods
}

这里有两个add方法，分别为:

1. 在头部插入，并且为第一个结构单元，指向原本的第一个节点first。
2. 在尾部插入，作为最后一个结构单元，被原本的最后一格结点的next所指向。

但是显然是有问题的，我们每次增加尾部节点我们都需要 先找到最后一个结点，也就是需要利用循环 while(p.next != null) 找到最后一个节点 p，再将 p.next = new InitNode(x, null);，这样的查找并不高效。

并且还会遇到另一个问题——空链表问题，如果说first为null，直接访问则会造成NullPointerException，除了添加if(first==null)外，为了同时避免这两种问题，哨兵节点（Sentinel Node）的使用是必然的。

NOTE

怎样理解哨兵节点呢？

我们可以这样认为，哨兵节点记住了第一个单元结构，以及最后的一个单元结构（在双向链表中），使得我们删除最后一个元素时候，不用直接循环遍历到最后，因为在初始化的时候，我们的哨兵节点就替我们记住了它们的位置。

• 在指定位置插入: 找到插入位置的前一个节点，然后调整指针以插入新节点。

1.6 remove方法#

//SLList.java
	/**
     * Removes and returns the last item from the list.
     * @return the item that was removed from the end of the list.
     * @throws NoSuchElementException if the list is empty.
     */
    public T removeLast(){
        if(first==null){
            throw new NoSuchElementException("Cannot removeLast from an empty lists");
        }

        T itemToReturn;// store the elements that wait for returning

        if(first.next==null){
            itemToReturn=first.item;
            first=null;
        } else {
            Node<T>p=first;

            while(p.next.next!=null){
                p=p.next;
            }
            itemToReturn = p.next.item;
            p.next=null;
        }
        size--;
        return itemToReturn;
        /*the item that was removed from the end of the list.*/
    }

    /**
     * Remove and returns the first item from the list.
     * @return the item that was removed from the end of the list.
     * @throws NoSuchElementException if the list is empty.
     * */
    public T removeFirst(){
        if(first==null){
            throw new NoSuchElementException("Cannot removeLast from an empty lists");
        }
        T itemToReturn = first.item;// store the elements that wait for returning
        first = first.next;

        size--;

        return first.item; // Actually donot need the itemToReturn
    }

可以看到我们同样实现了两个方法，removeLast和removeFirst都实现了类似的逻辑，先判断有无结构单元可以移除外，对size--，再最后返回删除的数据域。

但是removeLast也与addLast有同样的境遇，还是需要先找到最后一个结构单元，才能进行增删，并且我们还要更新原本倒数第二个结构单元，将其的next指向空指针。

1.7 reverse方法#

反转单链表意味着改变所有节点的 next 指针的方向，使原来的尾节点变成头节点，头节点变成尾节点。这通常可以通过迭代或递归实现。

    private Node<Item> reverseIterative(Node<Item> headNode) {
        Node<Item> prev = null;
        Node<Item> current = headNode;
        Node<Item> next = null;
        while (current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        // headNode = prev; // This line is optional if you just return prev
        return prev; // Directly returning prev is common
    }

迭代法: 需要三个指针：previous, current, next_node。遍历链表，在每一步中断开 current.next，将其指向 previous，然后向前移动所有三个指针。

1.8 last指针#

我们将last指针当作指向最后一个结构单元的指针，其作用就是定位最后一个元素：

public class SLList<T>{

    /**Dear User,it is incredibly important that you do not touch this.*/
    private Node<T> first;
    private Node<T> last;
}

并且为了获得last的定位，我们在add，remove时候，根据情况定位到last指针，这时候我们对removeLast，addLast方法就有了一个很好的复杂度$O(1)$，这比我们前面每次循环的$O(N)$高效多了。

public void addLast(T item){
    Node<T> newNode=new Node<>(item,null);

    if(first==null){// optional
        first=newNode;
    }else{
        last.next=newNode;
    }
    size++;
}

但是，即使 SLList 有了 last 指针，removeLast 仍然麻烦，因为需要找到倒数第二个元素。因此双向链接可以解决此问题。

2.1 引入双向链接的动机与优势#

即使为 SLList 添加一个 last 指针以快速访问尾节点，removeLast() 操作仍然困难，因为需要找到倒数第二个节点来更新其 next 指针，而 last 指针无法直接提供这个信息。为了让 last 指针指向新的尾节点（原倒数第二个节点），需要从头遍历或有反向指针。这就引出了双向链表的概念，它允许节点有指向前一个节点的 prev 链接，我们默认我们已经实现了last指针，方便我们增加/删除单元结构。

• 优点:

  • 可以双向遍历。
  • 从尾部删除或在已知节点前后插入操作更高效，$O(1)$ 时间复杂度，如果持有相关节点的引用。

• 实现 (DLList):

  • 通常会使用一个或两个哨兵节点（见下文）来简化边界条件的处理。

  • 插入操作需要更新新节点以及其前后节点的 prev 和 next 指针。

    

  • 删除操作需要更新被删除节点的前后节点的 prev 和 next 指针。

    

2.2 DLList 节点的定义#

private static class Node<T> {
    public T item;
    public Node<T> prev;
    public Node<T> next;
    public Node<T> last;

    public Node(T i, Node<T> p, Node<T> n) {
        item = i;
        prev = p;
        next = n;
    }
}

可以看到与SLLIst不同的是，多了一个public Node<T> prev表示指向前一个单元结构，由于这种定义会引发与SLList不同的效果，这时候我们需要重新写方法，如下：

NOTE

下面的结构相当于在原倒数第二个指针上直接引用到空指针。

4.1 哨兵节点 (Sentinel Node) 的引入#

在单向链表（SLList）的实现中，引入哨兵节点是一种常见的优化技巧，旨在简化链表操作的逻辑，特别是处理边界情况（如空链表）。

public class SLList<T> {
    private static class Node<T> {
        public T item;
        public Node<T> next;
        // ... 构造函数 ...
        public Node(T i, Node<T> n) {
            item = i;
            next = n;
        }
    }

    private Node<T> sentinel;
    private Node<T> last; // 指向最后一个实际节点，或在空列表时指向 sentinel
    private int size;

    /**
     * 创建一个空的 SLList。
     * 哨兵节点被初始化，last 指向哨兵节点，size 为 0。
     */
    public SLList() {
        sentinel = new Node<>(null, null); // 哨兵节点的值可以是任意，这里用 null
        last = sentinel; // 初始时，last 也指向 sentinel
        size = 0;
    }

    /**
     * 创建一个带有一个初始元素 x 的新 SLList。
     */
    public SLList(T x) {
        sentinel = new Node<>(null, null);
        Node<T> newNode = new Node<>(x, null);
        sentinel.next = newNode;
        last = newNode; // 新节点也是最后一个节点
        size = 1;
    }
    // ... 其他方法 ...
}

4.2 哨兵节点的特性与核心优势#

(参考教材或资料的第 34-35 页内容)

1. sentinel 引用本身永远不为 null：

   • 一旦 SLList 对象被创建，其 sentinel 实例变量就指向一个实际的 Node 对象（哨兵节点）。这意味着在任何方法内部，您都可以安全地解引用 sentinel (例如 sentinel.next) 而不必担心 sentinel 本身是 null。

2. 第一个实际数据节点（如果存在）总是在 sentinel.next：

   • 这提供了一个统一的访问点来获取链表的头部。无论是空链表还是非空链表，这个规则都成立（空链表时 sentinel.next 为 null）。

3. 许多操作不再需要对 first == null 的特殊检查：

   • 例如，在非哨兵版本的 addFirst 中，您可能需要：

     // 非哨兵版本的 addFirst (概念性)
     // if (first == null) {
     //     first = new Node(x, null);
     // } else {
     //     Node newNode = new Node(x, first);
     //     first = newNode;
     // }

   • 使用哨兵后，如上所示，addFirst 的逻辑更为直接。对于 addLast（即使是遍历版本），循环的初始化也更简单。

   • 您提到的“addLast 方法不再需要 if (sentinel == null) 这样的特殊检查”是正确的，因为 sentinel 永不为null。更广泛地说，是消除了对链表头指针（在非哨兵版本中为 first）是否为 null 的许多检查。

4.3 不变量 (Invariants)#

哨兵节点帮助我们更容易地建立和维护代码中的不变量（Invariants）。不变量是在程序执行期间，在特定点或在对象生命周期内始终为真的条件。它们对于推理代码的正确性至关重要。

对于带有哨兵节点的 SLList，一些关键不变量包括：

1. sentinel 引用总是指向哨兵节点对象
   • 贡献：这是最基本的不变量，由构造函数保证。它允许所有方法安全地使用 sentinel 变量。
   • 用途：消除了对 sentinel 变量本身的空检查。
2. 第一个真实节点（如果链表非空）总是在 sentinel.next。如果链表为空，sentinel.next 为 null。
   • 贡献：addFirst、removeFirst 等操作通过修改 sentinel.next 来维护这个不变量。
   • 用途：提供了一个一致的方式来访问链表的头部数据，简化了如 getFirst 等操作。
3. size 变量总是准确反映列表中实际元素的数量。
   • 贡献：所有修改链表内容的操作（addFirst, addLast, removeFirst, removeLast 等）都有责任正确更新 size。哨兵节点本身不直接维护 size，但简化的操作逻辑使得正确更新 size 更容易。
   • 用途：允许O(1)时间复杂度的 size() 方法，并且可以用于快速判断链表是否为空，这对于 getFirst、removeFirst 等操作的先决条件检查非常有用。
4. last 指针或者指向链表中的最后一个实际节点，或者在链表为空时指向 sentinel 节点。last 引用本身永不为 null。
   • 贡献：构造函数初始化 last = sentinel。addLast, removeLast, addFirst (当列表为空时) 和 removeFirst (当列表变为空时) 等方法会更新 last 以维持此不变量。
   • 用途：确保了O(1)的 addLast 操作，因为可以直接通过 last.next 添加新节点。

这些不变量使得推理代码行为和编写正确的链表操作代码更加容易。

截至目前，我们总共有以下的优化：

4.2 DLList 中哨兵节点的使用:#

但如果 DLList 的 last 指针在列表为空时指向 sentinel (或 null)，而在非空时指向实际的最后一个节点，这会导致代码中出现两种情况，增加了复杂性。

两种哨兵方案:

1. 两个哨兵 (sentFront, sentBack): 一个在最前，一个在最后。空列表时，sentFront.next 指向 sentBack，sentBack.prev 指向 sentFront。

   

2. 单个循环哨兵 (Even Better topology): 这是推荐的方案。

   

   空列表: sentinel.next == sentinel&&sentinel.prev == sentinel;

   

   非空列表: sentinel 节点逻辑上位于第一个真实元素之前和最后一个真实元素之后，形成一个环。sentinel.next 指向第一个真实元素，sentinel.prev 指向最后一个真实元素。第一个真实元素的 prev 指向 sentinel，最后一个真实元素的 next指向 sentinel。

   这种循环哨兵结构极大地统一了对空列表和非空列表的操作，以及对头部和尾部附近元素的操作。