链表超详细讲解（双向链表与循环链表实现）

上一篇我们实现了单向链表，体会到哨兵节点简化边界处理的优势。本文将进一步学习双向链表和双向循环链表，它们在实际场景中应用更广（如 LinkedList 底层），通过哨兵节点可实现更高效的双向操作。

一、带哨兵的双向链表的实现

双向链表相比单向链表增加了前驱指针，支持双向遍历，而哨兵节点的引入进一步简化了边界条件处理。
带哨兵的双向链表通过头哨兵和尾哨兵节点，统一了空链表、头部操作、尾部操作的逻辑，避免了大量的空指针判断。降低了代码复杂度，同时保留了双向链表双向访问、插入删除高效的优势，适用于需要频繁在头部 / 尾部操作或双向遍历的场景。

1、初始化带哨兵的双向链表

双向链表的节点含prev（前驱）和next（后继）指针，支持双向遍历。我们通过头哨兵和尾哨兵进一步简化操作。

• 定义内部节点类Node，包含前驱指针prev、数据域value、后继指针next。
• 初始化头哨兵head和尾哨兵tail，并通过指针将两者连接，形成初始空链表（仅含哨兵节点）。

public class DoubleSentinelLinkedList implements Iterable<Integer> {
    private static class Node{
        //前驱节点
        private Node prev=null;
        //当前节点值
        private int value;
        //后继节点
        private Node next=null;
        public Node(Node prev, int value, Node next) {
            this.prev = prev;
            this.value = value;
            this.next = next;
        }
    }
    /*带哨兵的双向链表属性：1、头哨兵 2、尾哨兵*/
    //头哨兵:前驱为空，因为已经到头了，值无意义，next暂设null
    private  Node head=new Node(null,666,null);
    //尾哨兵:后继为空，因为已经到尾了，值无意义，prev暂设null
    private  Node tail=new Node(null,888,null);
    //初始化头哨兵和尾哨兵：初始化时链表只有头哨兵和尾哨兵，将其链接成双向链表的形式
    public DoubleSentinelLinkedList(){
        head.next=tail;
        tail.prev=head;
    }
   }

2、在双向链表中查找节点

• 从头哨兵开始遍历，索引从-1（头哨兵索引）开始计数，有效节点索引从0开始。
• 遍历终止条件为节点等于尾哨兵，避免越界访问。

    /*获取双向链表中的节点*/
    //寻找指定节点
    public Node findNode(int index)
    {
        int point=-1;
        //注意循环条件，由于有尾节点，尾节点为链表中最后一个节点。遍历到最后一个尾节点的时候停止循环
        for (Node node=head;node!=tail;node=node.next,point++)
        {
            //找到对应的index个的节点
            if (point==index)
            {
                return node;
            }

        }
        //如果查找范围内没有找到就返回空值
        return null;
    }

3、在双向链表中插入节点

• 插入逻辑统一：通过前驱节点prevNode定位插入位置，新节点的prev指向prevNode，next指向prevNode.next
• 复用insert方法实现头部插入，通过尾哨兵的前驱直接定位尾部实现尾部插入
• 头部插入：复用insert(0, value)
• 尾部插入：利用尾哨兵的prev直接定位最后一个有效节点
• 指定位置插入：通过索引找前驱节点

（1）在任意位置插入节点

    /*插入节点*/
    //在任意位置插入节点
    public void insert(int index,int value)
    {
        //找出要插入节点的前驱
        Node prevNode=findNode(index-1);
        //判断前驱节点如果为空，则用户给的index要么超出了头部哨兵，要么超出了尾部哨兵，此时抛异常
        if (prevNode==null)
        {
            throw new IllegalArgumentException(String.format("index值不合法"));
        }
        //找到前驱节点后通过next可找到，要插入值的当前节点
        Node nextNode=prevNode.next;
        //创建要插入的节点（前驱节点为找到的要插入值的前驱节点，后继节点为插入值位置的原节点）
        Node insertNode=new Node(prevNode,value,nextNode);
        //将前驱节点的后继节点设置为当前插入的节点
        prevNode.next=insertNode;
        //将原节点的前驱设置为当前节点
        nextNode.prev=insertNode;
    }

（2）在双向链表头部插入节点

   //在链表头部插入节点，调用insert方法即可
    public void  addFirst(int value){
        insert(0,value);
    }

（3）在双向链表尾部插入节点

 //在链表的尾部添加一个节点（忽略尾哨兵）
    public void addLast(int value)
    {
       //可以通过尾哨兵找到当前的最后一个节点
       Node lastNode=tail.prev;
       //建立要插入的目标节点，前驱设置为找到的最后一个节点。后继为尾节点
       Node insertNode=new Node(lastNode,value,tail);
       //将最后一个节点的后继设置为插入节点
       lastNode.next=insertNode;
       //将尾哨兵的前驱设置为插入节点，完成节点的插入
       tail.prev=insertNode;
    }

4、删除节点

• 通过前驱节点定位目标节点，修改前驱的后继和后继的前驱，跳过目标节点实现删除。
• 尾部删除通过尾哨兵的前驱直接定位最后一个有效节点，无需遍历。

（1）删除指定位置的节点

    /*删除节点*/
    //删除指定位置的节点
    public void remove(int index)
    {
        //找到删除元素的上一个节点
        Node removeNodePrev=findNode(index-1);
        //判断前驱节点如果为空，则用户给的index要么超出了头部哨兵，要么超出了尾哨兵，此时抛异常
        if (removeNodePrev==null )
        {
            throw  new IllegalArgumentException(String.format("index值不合法"));
        }
        //找到要删除的节点
        Node removeNode=removeNodePrev.next;
        //判断要删除的节点是否为尾哨兵，尾哨兵不可被删除。抛异常
        if (removeNode==tail)
        {
            throw  new IllegalArgumentException(String.format("index值不合法"));
        }
        //当removeNode!=tail时证明next值一定不为null，找到要删除节点的下一个节点
        Node removeNodeNext=removeNode.next;
        /*--完成删除操作--*/
        //将删除节点的前驱节点的后继修改为删除节点的后继
        removeNodePrev.next=removeNodeNext;
        //将删除节点的前驱节点的前驱修改为删除节点的前驱
        removeNodeNext.prev=removeNodePrev;
    }

（2）删除双向链表中最后一个节点

 //删除链表的最后一个节点（忽略尾哨兵）
    public void removeLast()
    {
        //直接用尾哨兵找到当前的最后一个节点
        Node lastNode=tail.prev;
        //判断尾哨兵的前驱是否为头哨兵，如果为头哨兵则链表此时为空，抛出异常
        if (lastNode==head)
        {
            throw  new IllegalArgumentException(String.format("链表为空"));
        }
        //找到最后一个节点的前驱节点
        Node lastPrev=lastNode.prev;
        /*--完成删除操作--*/
        //将删除节点的前驱节点的后继修改为尾哨兵
        lastPrev.next=tail;
        //将尾哨兵的前驱修改为删除节点的前驱
        tail.prev=lastPrev;
    }

5、遍历链表(支持双向遍历，此处以正向遍历为例)

• 遍历起点为头哨兵的后继（第一个有效节点），终点为尾哨兵（不含尾哨兵）。
• 支持while循环、for循环和迭代器三种遍历方式，适配不同使用场景。

（1）使用while循环遍历双向链表

   /*遍历双向链表：1、while 2、for 3、迭代器*/
    //while循环遍历双向链表
    public void foreachUseWhile(Consumer<Integer> consumer)
    {

        int index=-1;
        Node node=head.next;
        while (node!=tail)
        {
            consumer.accept(node.value);
            node=node.next;
            index++;
        }
    }

（2）使用for循环遍历双向链表

  //用for遍历双向链表
    public void foreachUseFor(Consumer<Integer> consumer)
    {
        //注意循环条件，由于有尾节点，尾节点为链表中最后一个节点。遍历到最后一个尾节点的时候停止循环
        for (Node node=head.next;node!=tail;node=node.next)
        {
            //找到对应的index个的节点
            consumer.accept(node.value);
        }
    }

（3）使用迭代器遍历双向链表

    //用迭代器遍历双向链表
    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node node=head.next;
            @Override
            public boolean hasNext() {
                return node!=tail;
            }

            @Override
            public Integer next() {
                int value= node.value;
                node=node.next;
                return value;
            }
        };
    }

6、带哨兵的双向链表使用示例

验证头部插入、尾部插入、指定位置插入、删除、遍历等功能的正确性。

public class TextDoubleSentinelLinkedList {
    public static void main(String[] args) {
        DoubleSentinelLinkedList list = new DoubleSentinelLinkedList();

        // 1. 插入节点
        list.addFirst(1);    // 头部插入：[1]
        list.addLast(3);     // 尾部插入：[1, 3]
        list.insert(1, 2);   // 指定位置插入：[1, 2, 3]
        // 2. 遍历测试
        System.out.print("While循环遍历：");
        list.foreachUseWhile(value -> System.out.print(value + " "));  // 输出：1 2 3
        System.out.print("\nFor循环遍历：");
        list.foreachUseFor(value -> System.out.print(value + " "));    // 输出：1 2 3
        System.out.print("\n迭代器循环遍历：");
        for (int value : list) {
            System.out.print(value + " ");  // 输出：1 2 3
        }
        // 3. 删除测试
        System.out.print("\n删除测试：\n");
        list.remove(1);  // 删除索引1的节点（值为2）：[1, 3]
        list.foreachUseFor(value -> System.out.print(value + " "));    // 输出：1 2
        System.out.print("\n");
        list.removeLast();  // 删除最后一个节点（值为3）：[1]
        list.foreachUseFor(value -> System.out.print(value + " "));    // 输出：1

    }
}

运行结果如下：

二、带哨兵的双向循环链表的实现

带哨兵的双向循环链表是一种特殊的双向链表，通过单个哨兵节点实现首尾闭环：哨兵的prev指向尾节点，next指向头节点，所有有效节点位于哨兵节点的循环链路中。这种结构支持双向遍历和循环访问，同时通过哨兵统一了边界处理，避免空链表的特殊判断。

1、初始化带哨兵的双向循环链表

• 节点类Node包含前驱指针prev、数据域value、后继指针next。
• 哨兵节点sentinel是唯一的边界节点，初始化时prev和next均指向自身，形成初始闭环。

/*双向循环链表*/
public class DoublyCircularSentinelLinkedList implements Iterable<Integer>{

    private static class Node{
         //前驱节点
         private Node prev=null;
         //当前节点值
         private int value;
         //后继节点
         private Node next=null;
         public Node(Node prev, int value, Node next) {
             this.prev = prev;
             this.value = value;
             this.next = next;
         }
     }
    /*带哨兵的双向循环链表属性：1、哨兵（此时该哨兵即当头也当尾巴） 2、节点*/
    //sentinel哨兵的前驱和后继都应该指向自己，但由于自己还没被创建，先设初值为null
    private Node sentinel=new Node(null,-1,null);
    //在构造方法中完成前驱和后继都应该指向自己，此时自己已被创建
    public DoublyCircularSentinelLinkedList() {
        this.sentinel.next = sentinel;
        this.sentinel.prev=sentinel;
    }
}

2、查找节点

• 按索引查找：从哨兵开始遍历，索引从0开始，终止条件为遍历回到哨兵。

（1）根据index查找指定节点

/*查找节点*/
//根据index查找指定节点
private Node findNodeByIndex(int index)
{
    int i=-1;
    Node findNode=sentinel;
    for (;findNode.next!=sentinel;findNode=findNode.next,i++)
    {
        if(i==index)
        {
            return findNode;
        }
    }
    return null;
}

（2）根据值找到指定节点

• 按值查找：从哨兵的下一个节点（第一个有效节点）开始，匹配到第一个值相等的节点即返回。

//根据值找到指定节点（值相同返回前面那个）
private Node findNodeByValue(int value)
{
    for (Node findNode=sentinel.next;findNode!=sentinel;findNode=findNode.next)
    {
        if (findNode.value==value)
        {
            return findNode;
        }
    }
    return null;
}

3、插入节点

• 插入逻辑统一：通过调整前驱和后继节点的指针，将新节点接入闭环链路。
• 头部插入：在哨兵和原头节点之间插入。
• 尾部插入：在原尾节点和哨兵之间插入。
• 指定位置插入：通过索引定位前驱节点后插入。

（1）在头部插入

/*插入节点*/
//在双向循环链表的头部插入节点
public  void  addFirst(int value)
{
    //sentinel为哨兵，找到哨兵的下一个节点，也就是链表首节点
    Node addNext=sentinel.next;
    //创建要添加的节点
    Node addNode=new Node(sentinel,value,addNext);
    //将哨兵的后继设置为新节点
    sentinel.next=addNode;
    //将原首节点的前驱设置为为新节点，完成闭环
    addNext.prev=addNode;
}

（2）在尾部插入

//在双向循环链表的尾插入节点
public  void  addLast(int value)
{
    //sentinel为哨兵，找到哨兵的上一个节点，也就找到了链表的最后一个节点（环状）
    Node addPerv=sentinel.prev;
    //创建新节点，前驱为原尾节点，后继为哨兵节点
    Node addNode=new Node(addPerv,value,sentinel);
    //将哨兵节点的前驱设置为新插入的节点
    sentinel.prev=addNode;
    //将原尾节点的后继设置为新插入的节点完成闭环
    addPerv.next=addNode;
}

（3）在指定位置插入

//在双向循环链表的指定位置插入节点
public void  insert(int index,int value)
{
    //通过findNodeByIndex方法找到插入位置节点的前驱节点
    Node insertPrev=findNodeByIndex(index-1);
    //如果前驱节点==null则index超出边界，抛异常
    if (insertPrev==null)
    {
        throw  new IllegalArgumentException(String.format("超出边界"));
    }
    //找到插入位置的原节点即插入节点的后继
    Node insertNext=insertPrev.next;
    //创建要插入的节点
    Node insertNode=new Node(insertPrev,value,insertNext);
    //将原节点的前驱节点的后继节点设置为插入节点
    insertPrev.next=insertNode;
    //将原节点的前驱设置为要插入节点，完成插入，形成闭环
    insertNext.prev=insertNode;
}

4、删除节点

• 删除逻辑统一：通过调整目标节点的前驱和后继节点的指针，将目标节点从闭环链路中移除。
• 支持头部删除、尾部删除、按索引删除和按值删除，均无需单独处理空链表（通过哨兵判断链表是否为空）。
• 头部删除：移除sentiel.next；
• 尾部删除：移除sentiel.prev；
• 遍历终止条件：节点等于哨兵（避免无限循环）

（1）删除头部节点

/*删除节点*/
//删除头节点
public void removeFirst()
{
    //哨兵节点的后继节点为链表的头节点
    Node firstNode=sentinel.next;
    //如果头节点==哨兵则链表为空，抛出异常
    if (firstNode==sentinel)
    {
        throw  new IllegalArgumentException(String.format("链表为空"));
    }
    //找到原头节点的后继，如原头节点为最后一个节点，会指向哨兵
    Node firstNext=firstNode.next;
    //将哨兵节点的后继设置为原头节点的后继
    sentinel.next=firstNext;
    //将原头节点的后继节点的前驱设置为哨兵节点完成删除操作
    firstNext.prev=sentinel;
}

（2）删除尾部节点

//删除尾节点
public void removeLast()
{
    //哨兵节点的前驱节点为链表的头节点
    Node lastNode=sentinel.prev;
    //如果头节点==哨兵则链表为空，抛出异常
    if (lastNode==sentinel)
    {
        throw  new IllegalArgumentException(String.format("链表为空"));
    }
    //找到原尾节点的前驱，如原尾节点为最后一个节点，会指向哨兵
    Node lastPrev=lastNode.prev;
    //将哨兵节点的前驱设置为原尾节点的前驱
    sentinel.prev=lastPrev;
    //将原尾节点的前驱节点的前驱设置为哨兵节点完成删除操作
    lastPrev.next=sentinel;
}

（3）根据值进行删除节点

   //根据值进行删除
    public void removeByValue(int value)
    {
        //调用前面的寻找指定值的节点，找到要删除的节点
        Node removeNode=findNodeByValue(value);
        //如果返回节点为null则，要删除的值不在链表中，抛出异常
        if (removeNode==null)
        {
           throw   new IllegalArgumentException(String.format("删除值不存在链表中"));
        }
        //找到要删除节点的前驱
        Node nodePerv=removeNode.prev;
        //找到要删除节点的后继
        Node nodeNext=removeNode.next;
        //将删除节点的前驱节点的后继设置为删除节点的后继
        nodePerv.next=nodeNext;
        //将删除节点的后继节点的前驱设置为删除节点的前驱，完成删除操作
        nodeNext.prev=nodePerv;
    }

（4）根据索引进行删除节点

//在双向循环链表的指定位置删除节点
public void removeByIndex(int index)
{
    //找到要删除节点的前驱节点
    Node removePrev=findNodeByIndex(index-1);
    //如果删除节点的前驱节点为null则证明index超出边界，抛出异常
    if (removePrev==null)
    {
        throw  new IllegalArgumentException(String.format("超出边界"));
    }
    //找到删除节点的后继节点
    Node removeNext=removePrev.next.next;
    //将删除节点的前驱节点的后继设置为删除节点的后继
    removePrev.next=removeNext;
    //将删除节点的后继节点的前驱设置为删除节点的前驱，完成删除操作
    removeNext.prev=removePrev;
}

5、遍历链表

• 遍历终止条件为 “节点等于哨兵”，避免循环遍历无限执行。
• 支持迭代器遍历、递归遍历等方式，适配不同场景。

（1）迭代器遍历

/*遍历链表*/
//通过迭代器遍历
@Override
public Iterator<Integer> iterator() {
    return new Iterator<Integer>() {
        //从哨兵的下一个节点开始遍历
        Node node=sentinel.next;
        @Override
        public boolean hasNext() {
            //当节点再次等于哨兵时证明已经完成一个循环
            return node!=sentinel;
        }
        @Override
        public Integer next() {
            int value= node.value;
            node=node.next;
            return value;
        }
    };
}

（2）递归遍历

/*通过递归遍历：从哨兵的下一个节点开始，递归访问至哨兵终止*/
private void recursion(Node node, Consumer<Integer>consumer)
{
    //如果node为哨兵则以循环完一次链表return结束递归
    if (node==sentinel)
    {
        return;
    }
     //处理当前节点值
    consumer.accept(node.value);
    //递归访问下一个节点
    recursion(node.next,consumer);
}
//对外提供的递归遍历方法
public void foreachByRecursion(Consumer<Integer>consumer)
{
	 //从第一个有效节点开始递归
    recursion(sentinel.next,consumer);
}

遍历说明：
其余遍历方式（如while循环、for循环）可参考以下逻辑：

• 起始节点：sentinel.next（第一个有效节点）。
• 终止条件：node != sentinel（未回到哨兵节点）。
• 遍历步骤：通过node = node.next（正向）或node = node.prev（反向）移动节点。

三、总结

• 双向链表：通过prev和next支持双向遍历，适合频繁前后查找的场景
• 双向循环链表：闭环结构适合循环访问（如约瑟夫问题），单个哨兵简化边界处理
• 哨兵节点：是所有链表优化的核心，统一了空链表、头部 / 尾部操作的逻辑，减少代码复杂度。

至此，我们从基础到进阶完整实现了链表的主要类型。掌握这些结构后，你将能更深入理解 Java 集合（如 LinkedList）的底层原理，也能更灵活地解决链表相关的算法问题。