链表的实现

男娘i 2023-06-21 03:58 2阅读 0赞

##### 一、单链表 #####

1.  创建一个节点类，并应以节点内容，下一个节点和构造方法

public class Node {
            //一个节点
    	
    	//节点内容
    	int data;
    	
    	//下一个节点
    	Node next;
    	
    	public Node(int data) {
        
    		this.data = data;
    	}

1.  追加节点  
    先定义一个当前节点，循环找到当前节点的下一个节点，每次循环都把下一个节点赋值给当前节点，并判断下一个节点是否为空，如果下一个节点为空，跳出循环，将需要添加的节点赋值给当前节点的下一个节点。

//追加节点
    	public Node append(Node node) {
        
    		
    		//当前节点
    		Node currentNode = this;
    		
    		//循环找当前节点的下一个节点
    		while(true) {
        
    			Node nextnode = currentNode.next;
    			
    			//判断下一个节点是否为空，如果为空结束循环
    			if(nextnode == null) {
        
    				currentNode.next = node;
    				break;
    			}
    			//把下一个节点赋给当前节点
    			currentNode = nextnode;
    			
    		}
    		//把它本生返回
    		return this;
    	}

1.  删除节点  
    删除节点需要借助它的上一个节点，找到当前节点得下下一个节点，也就是需要删除的节点得下一个节点，并将其赋值给一个新的节点，再将新节点的值赋给当前节点的下一个节点

//删除下一个节点
    	public void removeNode() {
        
    		
    		//先找到当前节点的下下个节点,并将其赋值给一个新的节点
    		Node newnode = next.next;
    		
    		//再将新的节点赋值给当前节点的下一个节点
    		this.next = newnode;
    		
    	}

1.  插入一个节点  
    先找到一个当前节点，将当前节点的下一个节点赋给下下一个节点，再将需要插入的节点赋给当前节点的下一个节点，再将当前节点的下下一个节点赋值给需要插入节点的下一个节点

//插入一个节点
    	public void insert(Node node) {
        
    		//获取当前节点
    		Node currentnode = this;
    		
    		//将当前节点的下一个节点作为下下个节点
    		Node Next = currentnode.next;
    		
    		//将需要插入的节点插入到当前节点的后面，也就是当前节点的下一个节点
    		currentnode.next = node;
    		
    		//将当前节点得下下节点设置为新增节点得下一个节点
    		node.next = Next;
    	}

##### 二、循环链表 #####

1.  它的下一个节点指向当前节点

//节点内容
    	int data;
    	//下一个节点
    	LoopNode next = this;
    	
    	public LoopNode(int data) {
        
    		this.data = data;
    	}

1.  删除节点

//删除节点(需要借助一个新的节点和他的上一个节点)
    	public void delete() {
        
    		//当前节点
    		LoopNode currentNode = this;
    		//将当前节点的下下一个节点赋值给一个新的节点
    		LoopNode newNode = next.next;
    		//将新的节点赋值给当前节点的下一个节点
    		currentNode.next = newNode;
    	}

1.  插入节点

//插入节点
    	public void insert(LoopNode node) {
        
    		
    		//当前节点
    		LoopNode currentNode = this;
    		
    		//将当前节点的下一个节点赋值给下下一个节点
    		LoopNode Next = currentNode.next;
    		
    		//将需要插入的节点赋值给当前节点的下一个节点
    		currentNode.next = node;
    		
    		//将当前节点的下下一个节点赋值给插入节点的下一个节点
    		node.next = Next;
    	}

1.  循环链表测试

package node.test;
    
    public class LoopNodeTest {
            //循环链表测试类
    	public static void main(String[] ages) {
        
    		//创建节点
    		LoopNode n1 = new LoopNode(1);
    		LoopNode n2 = new LoopNode(2);
    		LoopNode n3 = new LoopNode(3);
    		LoopNode n4 = new LoopNode(4);
    		LoopNode n5 = new LoopNode(5);
    		
    		//插入节点
    		n1.insert(n2);
    		System.out.println(n1.next.getDate());
    		n2.insert(n3);
    		System.out.println(n2.next.getDate());
    		System.out.println(n3.next.getDate());
    		
    	}
    
    }

1.  运行结果  
    ![在这里插入图片描述][20191211184955428.png]

##### 三、双向循环链表 #####

1.  定义节点内容，下一个节点，上一个节点以及构造函数

//节点内容
    	int data;
    	//下一个节点
    	DoubleNode next = this;
    	//上一个节点
    	DoubleNode pre = this;
    	
    	public DoubleNode(int data) {
        
    		this.data = data;
    	}

1.  插入节点  
    定义下一和节点，

//插入节点
    	public void insert(DoubleNode node) {
        
    		//当前节点的下一个节点
    		DoubleNode Next = next;
    		
    		//把新节点作为当前节点的下一个节点
    		next = node;
    		
    		//把当前节点作为新节点的上一个节点
    		node.pre = this;
    		
    		//把当前节点的下一个节点作为新节点的下一个节点
    		node.next = Next;
    		
    		//把当前节点的下一个节点的上一个节点作为新节点
    		Next.pre = node; 
    	}

1.  测试类

package node.test;
    
    public class DoubleNodeTest {
            //双向训话链表测试类
    	public static void main(String[] args) {
        
    		
    		//创建节点
    		DoubleNode n1 = new DoubleNode(1);
    		DoubleNode n2 = new DoubleNode(2);
    		DoubleNode n3 = new DoubleNode(3);
    		
    		//追加节点
    		n1.insert(n2);
    		n2.insert(n3);
    		
    		//查看上一个，自己，下一个节点内容
    		System.out.println(n1.pre().getData());
    		System.out.println(n1.getData());
    		System.out.println(n1.next().getData());
    		System.out.println("n3的下一个节点的内容："+n3.next().getData());
    		System.out.println("n1的上一个节点内容："+n1.pre().getData());
    	}
    
    }

1.  运行截图  
    ![在这里插入图片描述][20191211200730601.png]

[20191211184955428.png]: https://img-blog.csdnimg.cn/20191211184955428.png
[20191211200730601.png]: https://img-blog.csdnimg.cn/20191211200730601.png