java实现链表

曾经终败给现在 2024-01-20 06:36 7阅读 0赞

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存储下一个节点的指针（Pointer）。

示例：

//算法部分
    class NodeManager{
        
    	private Node root;//根节点
    	private int currentIndex = 0;//节点的序号，每次操作从0开始
    	
    	//添加
    	public void add(int data) {
        
    		if(root!=null) {
        
    			root.addNode(data);
    		}else {
        
    			root = new Node(data);
    		}
    	}
    	//删除
    	public void del(int data) {
        //假设存储的数据没有相同的
    		if(root==null) {
        
    			return;
    		}
    		if(root.getData()!=data) {
        
    			root.delNode(data);
    		}else {
        
    			root = root.next;
    		}
    	}
    	//打印
    	public void print() {
        
    		if(root!=null) {
        
    			System.out.print(root.getData()+"->");
    			root.printNode();
    			System.out.println();//换行
    		}
    	}
    	//查找
    	public boolean find(int data) {
        
    		if(root==null) {
        
    			return false;
    		}
    		if(root.getData()!=data) {
        
    			return root.findNode(data);
    		}else {
        
    			return true;
    		}
    	}
    	//修改
    	public boolean update(int oldData,int newData) {
        
    		if(root==null) {
        
    			return false;
    		}
    		if(root.getData()!=oldData) {
        
    			return root.updateNode(oldData, newData);
    		}else {
        
    			root.setData(newData);
    			return true;
    		}
    	}
    	//插入（向index之前插入）
    	public void insert(int index,int data) {
        
    		if(index<0) {
        
    			return;
    		}
    		currentIndex = 0;
    		if(index!=currentIndex) {
        
    			root.insertNode(index, data);
    		}else {
        
    			Node newNode = new Node(data);
    			newNode.next = root;
    			root = newNode;
    		}
    	}
    	private class Node{
        
    		private int data;
    		private Node next;//把当前类型作为属性
    		public Node(int data) {
        
    			this.data = data;
    		}
    		public void setData(int data) {
        
    			this.data = data;
    		}
    		public int getData() {
        
    			return data;
    		}
    		//添加节点
    		public void addNode(int data) {
        
    			if(this.next!=null) {
        
    				this.next.addNode(data);
    			}else {
        
    				this.next = new Node(data);
    			}
    		}
    		//删除节点
    		public void delNode(int data) {
        
    			if(this.next!=null) {
        
    				if(this.next.data!=data) {
        
    					this.next.delNode(data);
    				}else {
        
    					this.next = this.next.next;
    				}
    			}
    		}
    		//输出所有节点
    		public void printNode() {
        
    			if(this.next!=null) {
        
    				System.out.print(this.next.data);
    				if(this.next.next!=null) {
        
    					System.out.print("->");
    				}
    				this.next.printNode();
    			}
    		}
    		//查找节点是否存在
    		public boolean findNode(int data) {
        
    			if(this.next!=null) {
        
    				if(this.next.data!=data) {
        
    					return this.next.findNode(data);
    				}else {
        
    					return true;
    				}
    			}
    			return false;
    		}
    		//修改节点
    		public boolean updateNode(int oldData,int newData) {
        
    			if(this.next!=null) {
        
    				if(this.next.getData()!=oldData) {
        
    					return this.next.updateNode(oldData, newData);
    				}else {
        
    					this.next.data = newData;
    					return true;
    				}
    			}
    			return false;
    		}
    		//插入节点
    		public void insertNode(int index,int data) {
        
    			currentIndex++;
    			if(index!=currentIndex) {
        
    				this.next.insertNode(index, data);
    			}else {
        
    				Node newNode = new Node(data);
    				newNode.next = this.next;
    				this.next = newNode;
    			}
    		}
    	}
    }
    
    
    
    
    //主函数
    class LinkList{
        
    	public static void main(String[] args) {
        
    		NodeManager nm = new NodeManager();
    		System.out.println("--------add--------");
    		nm.add(5);
    		nm.add(4);
    		nm.add(3);
    		nm.add(2);
    		nm.add(1);
    		nm.print();
    		System.out.println("--------del--------");
    		nm.del(3);
    		nm.print();
    		System.out.println("--------find--------");
    		System.out.println(nm.find(1));
    		System.out.println("--------update--------");
    		nm.update(1, 10);
    		nm.print();
    		System.out.println("--------insert--------");
    		nm.insert(1, 20);
    		nm.print();
    	}
    }

输出结果：

--------add--------
    5->4->3->2->1
    --------del--------
    5->4->2->1
    --------find--------
    true
    --------update--------
    5->4->2->10
    --------insert--------
    5->20->4->2->10

对比链表与数组：  
数组适合查找、遍历，固定长度。  
链表适合插入、删除，长度不宜过长，否则会导致遍历性能下降。