java实现单链表

分手后的思念是犯贱 2023-10-18 15:14 138阅读 0赞

**链表是java数据结构中一种很基础很常见却也很重要的数据结构，JDK中许多内置jar包基于单链表实现，比如像我们熟悉的linkedList等，为什么要使用链表呢？**

我们知道java中很多集合的底层是基于数组实现的，数组有一个很重要的结构就是索引，通过索引可以快速定位数据，并对数据进行删除等操作，但问题是，我们的业务中，数组有自身的局限性，如果知道索引还好，如果不知道索引就需要一个个遍历查找，然后再进行操作，假如是删除一个数据，对于数组来说，要进行的操作是：根据索引定位到数据，然后删除这条数据，然后数组中的数据进行重新位置的移动，平均来看，这个时间复杂度应该是2logN，尤其是重新调整位置使得性能开销较大，

我们看看下面这张链表的图：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70]

链表的结构很简单，就是一个个节点连接在一起，形成一个完整的链条，每个节点包含2部分，数据域，和一个指向下一个节点引用的指针next,具体的更详细的大家可以参考相关资料解释，再说说删除操作，同样需要找到数据所在的位置，然后进行删除，不同的是，删除的时候，链表只需要改变一下前后节点的引用关系即可，就完成了节点的删除，而没有像数组那样触发一次全部数据的移动，从这个描述来看，链表在进行删除的时候，速度比数组快，

链表的分类有很多种，比如单链表，双端链表，双向链表，单向链表等，下面说说单链表的具体实现，单链表是其他链表的基础，掌握了单链表实现其他的就好理解了，下面直接上代码，可以结合注释看，

class ListNode<T> {
    	
    	private int foot;		//根节点索引位置
    	private int count;		//代表链表程度
    	private Node root;		//标识根节点
    	
    	//链接点类,内部方法实现，外部使用
    	private class Node{
    		
    		private T data;		//数据信息
    		private Node next;	//下一个节点引用
    		
    		public Node(T data) {
    			this.data = data;
    		}
    		
    		//添加节点
    		private void add(T data){
    			if(this.next == null){
    				this.next = new Node(data);		//如果当前节点的next为null,直接创建一个新的节点
    			}else {
    				this.next.add(data);			//否则进行递归调用，直到最后在某个为空的节点创建一个新节点
    			}
    		}
    		
    		//删除节点1
    		public void remove(Node previous, int index){
    			
    			if(ListNode.this.foot++ == index){
    				previous.next = this.next;	//this表示当前要删除的节点
    				this.next = null;	
    				ListNode.this.count--;
    				return;
    			}else{
    				this.next.remove(this,index);	//递归删除
    			}
    			
    		}
    		
    		//删除节点2 
    		public void remove(Node previous, T data){
    			if(this.data.equals(data)){
    				previous.next = this.next;
    				this.next = null;
    				ListNode.this.count--;
    				return ;
    			}else{
    				if(this.next != null){
    					this.next.remove(this,data);
    				}else{
    					return;
    				}
    			}
    		}
    		
    		//修改数据  -- 新数据替换旧数据
    		public void replace(T oldData,T newData){
    			if(this.data.equals(newData)){
    				this.data = newData;
    			}else{
    				this.next.replace(oldData, newData);  //递归修改，寻找当前节点下一个节点，直到某个节点的值匹配入参
    			}
    	
    		}
    		
    		//修改数据  -- 利用索引修改
    		public void replace(int index,T newData){
    			if(ListNode.this.foot++ == index){	//找到了某个值的索引和传入的索引相同，直接替换
    				this.data = newData;
    			}else{
    				this.next.replace(index, newData);
    			}
    		}
    		
    		//查询
    		public T get(int index){
    			if(ListNode.this.foot++ == index){
    				return this.data;
    			}else{
    				return this.next.get(index);
    			}
    		}
    		
    		//链表是否包含某个节点
    		public boolean contains(T data){
    			if(this.data.equals(data)){	//如果当前的这个data正好和传入的data匹配
    				return true;
    			}else{
    				//如果当前的这个不匹配，则需要查找下一个节点
    				if(this.next == null){
    					return false;
    				}else{
    					return this.next.contains(data);
    				}
    			}
    		}
    		
    	}
    	
    	public ListNode() {
    		
    	}
    	
    	//检查链表是否为空
    	public boolean isEmpty(){
    		if(count == 0 || this.root == null){
    			return true;
    		}else{
    			return false;
    		}
    	}
    	
    	//获取链表的长度
    	public int size(){
    		return this.count;
    	}
    	
    	//添加
    	public void add(T data){
    		if(this.isEmpty()){ //如果链表为空，新建一个节点
    			this.root = new Node(data);
    		}else{
    			this.root.add(data);
    		}
    		this.count++;
    	}
    	
    	//删除  -- 按照索引删除
    	public void remove(int index){
    		if(this.isEmpty()){
    			return;
    		}
    		if(index < 0 || this.count <= index){
    			return ;
    		}
    		if(index == 0){	//想要删除根节点
    			Node temp = this.root;
    			this.root = this.root.next;
    			temp.next = null;
    			this.count--;
    			return ;
    		}else{
    			this.foot = 0;
    			this.root.remove(this.root, index);
    		}
    	}
    	
    	//根据传入的数值删除
    	public void remove(T data){
    		if(this.isEmpty()){
    			return;
    		}
    		if(this.root.data.equals(data)){	//如果删除的正好是根节点
    			Node temp = this.root;
    			this.root = this.root.next;
    			temp.next = null;
    			this.count--;
    			return ;
    		}else{
    			this.root.remove(this.root, data);
    		}
    	}
    	
    	//修改  -- 根据索引修改
    	public void replace(int index,T newData){
    		if(this.isEmpty()){
    			return;
    		}
    		if(index < 0 || this.count <= index){
    			return ;
    		}
    		this.foot = 0;
    		this.root.replace(index, newData);
    	}
    	
    	//修改 -- 新老数据替换
    	public void replace(T oldData,T newData){
    		if(this.isEmpty()){
    			return;
    		}
    		this.root.replace(oldData, newData);
    	}
    	
    	//查询 --- 根据索引查找
    	public T get(int index){
    		if(this.isEmpty()){
    			return null;
    		}
    		this.foot = 0;
    		return this.root.get(index);
    	}
    	
    	//是否包含
    	public boolean contains(T data){
    		if(this.isEmpty()){
    			return false;
    		}
    		return this.root.contains(data);
    	}
    	
    	//打印  toArray
    	public Object[] toArray(){
    		if(this.isEmpty()){
    			return null;
    		}
    		int count = this.count;
    		Object[] retVal = new Object[count];
    		for(int i=0;i<count;i++){
    			retVal[i] = this.get(i);
    		}
    		return retVal;
    	}
    }

下面是测试代码，

public static void main(String[] args) {
    		ListNode<String> myList = new ListNode<String>();
    		myList.add("a");
    		myList.add("b");
    		myList.add("c");
    		myList.add("d");
    		myList.add("e");
    		myList.add("f");
    		System.out.println("第三个元素是:" + myList.get(3));
    		myList.remove(3);
    		System.out.println("删除之后，第三个元素是:"+myList.get(3));
    		
    		System.out.println("-----------替换之后--------");
    		
    		myList.replace(1, "b11");
    		System.out.println(myList.get(1));
    		
    	}

运行一下上述main函数，我们随意写了几个测试方法，控制台打印结果：

![在这里插入图片描述][2019030622063476.png]

**大家可以看到，代码中大量使用了递归来实现，主要是想深入的使用一下递归，同时使用递归来实现节省了较多的代码量，而且比较容易理解，单链表的实现到此结束，谢谢观看！**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190306214800807.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw,size_16,color_FFFFFF,t_70
[2019030622063476.png]: https://img-blog.csdnimg.cn/2019030622063476.png