Java实现一个简单的链表结构------LinkedList

水深无声 2022-06-07 13:47 165阅读 0赞

我觉得理解一件事情最好的办法就是经历它，同样的，当我们纠结该使用ArrayList还是LinkedList的时候，不妨我们自己先想一下他们的实现原理，然后在看看他们各自的源码，应该会比较容易理解，然后根据自己的理解写出简单的实现，这对于编程能力的提高也有很大的帮助。下面来看代码，该说的都在注释里面了，其实我们不懂链表关键是不理解链表的的定义。一定要记住的是链表有数据域跟指针域，链表的节点总是指向下一个的。

package com.ynsmile.LinkList;
    
    public class MyLinkedList {
    
    	public static class Node{
    		//链表分为指针域跟数据域
    		protected Node next;
    		protected int data;
    		
    		public Node(int data) {
    			this.data = data;
    		}
    		public void display(){
    			System.out.println("data="+data);
    		}
    	}
    	
    	private Node firstNode;//第一个节点元素
    	private int pos;//节点的位置
    	
    	public MyLinkedList(){
    		this.firstNode = null;
    	}
    	
    	//添加第一个节点元素
    	public void addFirstNode(int data){
    		Node node = new Node(data);
    		node.next = firstNode;
    		firstNode = node;
    	}
    	//删除第一个节点元素
    	public Node deleteFirstNode(){
    		Node node = firstNode;
    		firstNode = firstNode.next;
    		return node;
    	}
    	//根据指定的位置添加数据
    	public void addNodeByIndex(int index,int data){
    		Node currentNode = firstNode;
    		Node previousNode = firstNode;
    		
    		while(index!=pos){
    			previousNode = currentNode;
    			currentNode = currentNode.next;
    			pos++;
    		}
    		Node node = new Node(data);
    		previousNode.next = node;
    		node.next = currentNode;
    		pos = 0;
    	}
    	//根据指定位置删除元素
    	public Node deleteNodeByIndex(int index){
    		
    		Node currentNode = firstNode;
    		Node previousNode = firstNode;
    		while(pos!=index){
    			previousNode = currentNode;
    			currentNode = currentNode.next;
    			pos++;
    		}
    		if(currentNode == firstNode){
    			firstNode  = firstNode.next;
    		}
    		else{
    			pos = 0;
    			previousNode.next = currentNode.next;
    		}
    		return currentNode;
    	}
    	//根据指定的data来删除数据
    	public Node deleteNodeByData(int data){
    		Node previousNode = firstNode;
    		Node currentNode = firstNode;
    		while(currentNode.data!=data){
    			if(currentNode.next == null){
    				return null;
    			}
    			previousNode = currentNode;
    			currentNode = currentNode.next;
    		}
    		if(currentNode == firstNode){
    			firstNode = firstNode.next;
    		}
    		else{
    			previousNode.next = currentNode.next;
    		}
    		return currentNode;
    	}
    	//根据index来查找结点元素
    	public Node findNodeByIndex(int index){
    		
    		Node currentNode = firstNode;
    		
    		if(pos!=index){
    			currentNode = currentNode.next;
    			pos++;
    		}
    		return currentNode;		
    	}
    	//根据data来查找结点元素
    	public Node finNodeByData(int data){
    		Node currentNode = firstNode;
    		
    		if(currentNode.data!=data){
    			if(currentNode.next==null) return null;
    			currentNode = currentNode.next;
    		}
    		return currentNode;
    	}
    	 public void displayAllNodes() {  
             Node current = firstNode;  
              while (current != null) {  
                 current.display();  
                 current = current. next;  
             }  
             System. out.println();  
        }  
    	public static void main(String[] args) {
    		MyLinkedList linkList = new MyLinkedList();  
            linkList.addFirstNode(1);  
            linkList.addFirstNode(2);  
            linkList.addFirstNode(3);  //这个时候链表为3，2，1
            
            linkList.addNodeByIndex(1, 4); //3，4,2,1  
            linkList.addNodeByIndex(2, 5); //3，4,5，2,1  
            linkList.addNodeByIndex(3, 6); //3，4,5，6，2,1   
            linkList.displayAllNodes();  
            Node node = linkList.deleteNodeByData(6);   
            System. out.println("刚才的节点数据 : " + node. data);  
            linkList.displayAllNodes();  
            Node node1 = linkList.findNodeByIndex(0);  
            System.out.println("查找的节点数据: " + node1. data);  
            Node node2 = linkList.finNodeByData(3);  
            System. out.println("查找的节点数据：: " + node2. data);  
    	}
    }

如果自己可以写出一个这样的单向链表，对于理解为什么插入和删除的时候，采用链表的结构会比采用顺序表结构的集合的性能要好会起到很好的效果！

带着问题去解惑吧。