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

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

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

链表的结构很简单，就是一个个节点连接在一起，形成一个完整的链条，每个节点包含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函数，我们随意写了几个测试方法，控制台打印结果：

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