双向循环链表的实现详解

迈不过友情╰ 2022-02-03 14:03 196阅读 0赞

双向循环链表直接体现为  **双向和循环**，一般的单链表只有节点数据data和next指向地址(应该也是引用的意思)，而在此需要增加前面部分的pre指向地址，同时还需要循环

循环则在定义节点时可以解决，如下所示

即假想只有一个节点的时候，不论是上一个节点的指向还是下一个节点的指向都是自己。

![20190509164028746.png][]

双向可以假想三个节点，实际上就是3个节点之间完成pre和next的指向替换，如下图所示

![20190509163549564.png][]

**//原来的下一个节点2的表示  
        DoubleLoopNode nextNode =next;  
        //把新节点作为节点1的下一个节点  
        this.next = node;  
        //把节点1当作新节点的pre  
        node.pre = this;  
        //将节点2作为新节点的下一个指向  
        node.next = nextNode;  
        //将新节点作为节点2 的上一个指向  
        nextNode.pre = node;**

**这样以来就完成了双向循环链表。具体代码如下**

public class DoubleLoopNode {
    	//上一个节点
    	DoubleLoopNode pre=this;
    	//下一个节点
    	DoubleLoopNode next=this;
    	//循环的体现  pre=this   next=this
    	//数据
    	int data;
    	//构造函数
    	public DoubleLoopNode(int data) {
    		this.data=data;
    	}
    	//增加节点
    	//      | pre|data|next|  原来节点1（this）
    	
    	//      | pre|data|next|   node新节点
    	
    	//      | pre|data|next|  原来节点2
    	
    	public void after(DoubleLoopNode node) {
    		//原来的下一个节点2的表示
    		DoubleLoopNode nextNode =next;
    		//把新节点作为节点1的下一个节点
    		this.next = node;
    		//把节点1当作新节点的pre
    		node.pre = this;
    		//将节点2作为新节点的下一个指向
    		node.next = nextNode;
    		//将新节点作为节点2 的上一个指向
    		nextNode.pre = node;
    		
    	}
    	public DoubleLoopNode next() {
    		return this.next;
    	}
    	public DoubleLoopNode pre() {
    		return this.pre;
    	}
    	public int getData() {
    		return this.data;
    	}
    }

**测试代码及结果**

DoubleLoopNode n1 = new DoubleLoopNode(1);
    DoubleLoopNode n2 = new DoubleLoopNode(2);
    DoubleLoopNode n3 = new DoubleLoopNode(3);
    DoubleLoopNode n4 = new DoubleLoopNode(4);
    		
    n1.after(n2);
    n2.after(n3);
    System.out.println(n1.next.getData());
    System.out.println(n1.pre.getData());

最后显示的结果为2，3

n1、n2、n3三个节点循环相接，n1的前一个节点为n3(3)，n1的下一个节点为n2(2)

[20190509164028746.png]: /images/20220203/c973204b5cf949a89d437af37771ae8f.png
[20190509163549564.png]: /images/20220203/59e7cb79a3c040b685669548530c4960.png