Java-实现双向环形链表

        双向链表是一种常用的数据结构，其特点是每个节点不仅包含数据，还持有指向前一个节点和后一个节点的指针。与普通双向链表不同的是，它的哨兵节点的prev指向最后一个元素，而最后一个元素的next指向哨兵。

        具体双向普通链表可以参考我的上篇文章，这里是传送门。

什么是双向环形链表？

        双向环形链表不仅支持双向遍历，还形成一个闭合环，即最后一个节点的next指针指向链表的头部，第一个节点的prev指针指向链表的尾部。使用这种结构可以实现更加灵活的循环遍历操作。

基本结构

        在Java实现中，常见地使用一个“哨兵节点”来简化对表头和表尾的处理逻辑，使链表的实现更加一致和高效。

以下是一个基本的双向环形链表的结构模块：

private static class Node {
    Node prev;
    Node next;
    int data;

    public Node(Node prev, Node next, int data) {
        this.prev = prev;
        this.next = next;
        this.data = data;
    }
}

private Node sentinel = new Node(null, null, -1);

基本操作

1. 初始化

在构造函数中，我们需要初始化哨兵节点，使其next和prev指向自身，从而形成一个初始的空环。

 public BidirectionlRingList() {
        sentinel.next = sentinel;
        sentinel.prev = sentinel;
    }

2. 添加元素

        我们提供了添加元素的方法addfirst和addlast和add,这三个方法分别更新哨兵节点的指针，使新节点插入链表的相应位置。

   public void addfirst(int data) {
        Node newNode = new Node(sentinel, sentinel.next, data);
        sentinel.next.prev = newNode;
        sentinel.next = newNode;
    }

    public void addlast(int data) {
        Node a = sentinel.prev;
        Node b = sentinel;
        Node newNode = new Node(a, b, data);
        a.next = newNode;
        b.prev = newNode;
    }

    public void add(int index, int data) {
        Node a = findNode(index-1);
        Node b = a.next.next;
        Node newNode = new Node(a, b, data);
        a.next = newNode;
        b.prev = newNode;
        if (a ==sentinel || b == sentinel){
            throw new RuntimeException("Index out of range");
        }
    }

3. 删除元素

        删除元素方法removefirst和removelast和removeByIndex，首先检查链表是否为空，然后更新相关指针去除节点。

    public void removefirst() {
        Node removedNode = sentinel.next;
        if (removedNode == sentinel) {
            throw new RuntimeException("List is empty");
        }
        removedNode.next.prev = sentinel;
        sentinel.next = removedNode.next;
    }

    public void removelast() {
        Node removedNode = sentinel.prev;
        if (removedNode == sentinel){
            throw new RuntimeException("List is empty");
        }
        removedNode.prev.next = sentinel;
        sentinel.prev = removedNode.prev;
    }

    public void removeByindex(int index) {
        Node removedNode = findNode(index);
        if(removedNode == null){
            throw new RuntimeException("Index out of range");
        }
        removedNode.prev.next = removedNode.next;
        removedNode.next.prev = removedNode.prev;
    }

4. 遍历

        遍历操作通过trverse实现，它遍历链表中的所有节点并打印节点数据，让用户可以观察链表中存储的数据。

 public void trverse(){
        for(Node p = sentinel.next; p != sentinel; p = p.next){
            System.out.println(p.data + " ");
        }

    }

5.修改

我们可以根据索引修改值

  public void setdata(int index, int data){
        Node node = findNode(index);
        node.data = data;
        if (node == null){
            throw new RuntimeException("Index out of range");
        }
    }

源码

package school.bidirectionlRingList;

import java.util.Iterator;

/**
 * 文件名: null.java
 * 作者: 20526
 * 创建时间: 2024/9/10 10:35
 * 描述:双向环形链表
 */
public class BidirectionlRingList implements Iterable<Integer> {

     private Node sentinel = new Node(null, null, -1);

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node current = sentinel.next;
            @Override
            public boolean hasNext() {
                return current != sentinel;
            }

            @Override
            public Integer next() {
                int data = current.data;
                current = current.next;
                return data;
            }
        };
    }

    private static class Node {
        Node prev ;
        Node next ;
        int data ;

        public Node(Node prev, Node next, int data) {
            this.prev = prev;
            this.next = next;
            this.data = data;
        }
    }

    public BidirectionlRingList() {
        sentinel.next = sentinel;
        sentinel.prev = sentinel;
    }


    public void addfirst(int data) {
        Node newNode = new Node(sentinel, sentinel.next, data);
        sentinel.next.prev = newNode;
        sentinel.next = newNode;
    }

    public void addlast(int data) {
        Node a = sentinel.prev;
        Node b = sentinel;
        Node newNode = new Node(a, b, data);
        a.next = newNode;
        b.prev = newNode;
    }

    public void add(int index, int data) {
        Node a = findNode(index-1);
        Node b = a.next.next;
        Node newNode = new Node(a, b, data);
        a.next = newNode;
        b.prev = newNode;
        if (a ==sentinel || b == sentinel){
            throw new RuntimeException("Index out of range");
        }
    }



    public void removefirst() {
        Node removedNode = sentinel.next;
        if (removedNode == sentinel) {
            throw new RuntimeException("List is empty");
        }
        removedNode.next.prev = sentinel;
        sentinel.next = removedNode.next;
    }

    public void removelast() {
        Node removedNode = sentinel.prev;
        if (removedNode == sentinel){
            throw new RuntimeException("List is empty");
        }
        removedNode.prev.next = sentinel;
        sentinel.prev = removedNode.prev;
    }
    public Node findNode(int index){
        int i = 0;
        for(Node p = sentinel.next; p != sentinel; p = p.next,i++){
            if(index == i){
                return p;
            }
        }
        return null;
    }

    public void removeByindex(int index) {
        Node removedNode = findNode(index);
        if(removedNode == null){
            throw new RuntimeException("Index out of range");
        }
        removedNode.prev.next = removedNode.next;
        removedNode.next.prev = removedNode.prev;
    }

    public void trverse(){
        for(Node p = sentinel.next; p != sentinel; p = p.next){
            System.out.println(p.data + " ");
        }

    }
    public void setdata(int index, int data){
        Node node = findNode(index);
        node.data = data;
        if (node == null){
            throw new RuntimeException("Index out of range");
        }
    }




}

总结

        双向环形链表是编程中一种强大且灵活的数据结构，它可用于在循环访问中保持高效。通过合理设计Node结构和使用哨兵节点，我们简化了边界条件的处理，提供了更直观的操作方法。希望对你有所帮助。