Java链表及源码解析

1. **链表是通过逻辑储存的方式通过节点的引用来获取元素值，每个节点包含两个部分 首先第一部分是value元素值。 第二部分是next来获取下个节点的地址，通过next来串联各个地址获取其中的value元素
   有序数组如果想要新增或者删减元素需要从头开始遍历逐个进行覆盖确保有序数组中的有序,时间复杂度为O(m*n)。
   链表的复杂度相对有序数组要方便他的时间复杂度分别是O(1)和O(N)。 **
   

创建一个ILindkedList接口创建方法(模拟实现链表方法)

public interface ILinkedList {//首位置新增元素public void addFirst(int data);//最后位置新增元素public void addLast(int data);//在指定位置新增元素public void addIndex(int index,int data);//在链表中删除key元素public void remove(int key);//删除所有key的元素public void removeAll(int key);//打印链表元素public void display();//是否包含datapublic boolean contains(int data);//获取链表中元素的大小public  int size();void clean();
}

创建MyLinkedList来实现接口的方法

import javax.xml.soap.Node;public class MyLinkedList implements ILinkedList{//创建一个static内部类来初始化节点属性static class NodeList{//元素值public int value;//节点指向的下一个地址public NodeList next;//构造方法只给value通过这个值来next下一个节点public NodeList(int value) {this.value = value;}}

创建链表节点

 //这里可以尝试创建一个链表public void createLinkedList(){NodeList node1=new NodeList(23);NodeList node2=new NodeList(25);NodeList node3=new NodeList(38);NodeList node4=new NodeList(55);//通过获取的对象来访问next链接下一个节点实现链接node1.next=node2;node2.next=node3;node3.next=node4;//这里node4的next节点为空值//head作为头部来访问各个节点this.head=node1;}

addFirst方法（新增头部属性）

 @Overridepublic void addFirst(int data) {//增加一个元素到链表中,增加到头部//将data元素放入到类中NodeList node=new NodeList(data);NodeList cur=this.head;//这里node.next来获取头部地址node.next=head;//将node赋给headhead=node;}

addLast方法（新增到末尾一个属性）

 @Overridepublic void addLast(int data) {//增加一个元素到末尾NodeList node=new NodeList(data);NodeList cur=this.head;//这里我们查找最后一个位置的next节点是否为null，如果是null；while(cur.next!=null){cur = cur.next;}//循环出来cur.next的节点为nullcur.next=node;}

remove方法（删除指定属性）

    @Overridepublic void remove(int key) {//删除指定元素的next地址节点if(this.head==null){return;}//得到前缀NodeList cur = findRemoveKey(key);//判断返回值是否是空的if(cur==null){System.out.println("未找到该元素"+key);return;}//将cur.next给到dele得到节点NodeList dele=cur.next;//将后一个节点的next给到cur.next从而指向其他节点dele原有节点消失cur.next=dele.next;}private NodeList findRemoveKey(int key){NodeList cur=this.head;//cur.next不等于null数值while(cur.next!=null){if(cur.next.value==key){return cur;}//cur.next节点获取下一个curcur = cur.next;}return null;}

addIndex方法（任意位置添加一个元素属性）

removeAll（删除所有指定元素）

   @Overridepublic void removeAll(int key) {if(this.head==null){return;}NodeList pre=this.head;NodeList cur=pre.next;//cur！=null说明有数据while(cur!=null){//value值为key进入循环if(cur.value==key){//pre的下个节点为cur的下一个节点，取消掉cur=key这个节点的链接pre.next=cur.next;cur=cur.next;}else{//如果不等于pre要跳到cur的位置来继续作为前一项pre=cur;//cur获取下一项cur=cur.next;}}//不要忽略头部，如果是key要替换掉if(this.head.value==key){this.head=this.head.next;}}

    @Overridepublic void addIndex(int index, int data)throws ErrorRuntimeExcepetion {//给一个位置，放入data元素//如果index的值小于0或者大于本身长度抛出异常显示下标try {if(index<0||index>size()){throw new ErrorRuntimeExcepetion("范围不准确"+index);}}catch (ErrorRuntimeExcepetion e){e.printStackTrace();return;}//如果index的位置是0或者index的位置是最后一个if(index==0){addFirst(data);}if(index==size()){addLast(data);}//走到这里index的值为其范围内容，首先获取index-1的位置NodeList cur = searchPre(index);//生成data元素链表NodeList node=new NodeList(data);if(cur==null){return;}//将原来cur.index的地址赋值给node.index来后移node.next=cur.next;//将现在的cur.index的地址指向nodecur.next=node;}private NodeList searchPre(int index){NodeList cur=this.head;//求一个index-1的范围int count=0;while(count<index-1){cur=cur.next;count++;}//获取到index-1位置的curreturn cur;}

display打印

 @Overridepublic void display() {//创建一个对象接收head值，来进行打印NodeList cur=this.head;//cur不等于nullwhile(cur!=null){//通过cur引用value来打印元素System.out.print(cur.value+" ");//通过next中下一个节点的地址来访问元素cur=cur.next;}System.out.println();}

contains（链表中包含某个元素）

   @Overridepublic boolean contains(int data) {//链表中是否包含dataNodeList cur=this.head;if(cur.value==data){//如果value是data返回truereturn true;}else{while(cur.next!=null){//循环每个节点判断是否为dataif(cur.next.value==data){return true;}cur=cur.next;}}return false;}

size（获取链表元素的数量）

@Overridepublic int size() {//获取链表的元素大小NodeList cur = this.head;//如果cur中为null没有任何元素大小是0if (cur == null) {return 0;}int count=0;//计数while(cur!=null){count++;cur=cur.next;}return count;}

clean（清空）

   @Overridepublic void clean() {if(this.head==null){return;}//将每个节点置为空属性并且回收NodeList cur=this.head;while(cur!=null){NodeList curNext=cur.next;cur.next=null;cur=curNext;}//置空nullthis.head=null;}

MyLinkedList代码如下：

import javax.xml.soap.Node;public class MyLinkedList implements ILinkedList{//创建一个static内部类来初始化节点属性static class NodeList{//元素值public int value;//节点指向的下一个地址public NodeList next;//构造方法只给value通过这个值来next下一个节点public NodeList(int value) {this.value = value;}}//创建一个带头链表来获取当前的节点第一个元素public NodeList head;//这里可以尝试创建一个链表public void createLinkedList(){NodeList node1=new NodeList(23);NodeList node2=new NodeList(25);NodeList node3=new NodeList(38);NodeList node4=new NodeList(55);//通过获取的对象来访问next链接下一个节点实现链接node1.next=node2;node2.next=node3;node3.next=node4;//这里node4的next节点为空值//head作为头部来访问各个节点this.head=node1;}@Overridepublic void addFirst(int data) {//增加一个元素到链表中,增加到头部//将data元素放入到类中NodeList node=new NodeList(data);NodeList cur=this.head;//这里node.next来获取头部地址node.next=head;//将node赋给headhead=node;}@Overridepublic void addLast(int data) {//增加一个元素到末尾NodeList node=new NodeList(data);NodeList cur=this.head;//这里我们查找最后一个位置的next节点是否为null，如果是null；while(cur.next!=null){cur = cur.next;}//循环出来cur.next的节点为nullcur.next=node;}@Overridepublic void remove(int key) {//删除指定元素的next地址节点if(this.head==null){return;}//得到前缀NodeList cur = findRemoveKey(key);//判断返回值是否是空的if(cur==null){System.out.println("未找到该元素"+key);return;}//将cur.next给到dele得到节点NodeList dele=cur.next;//将后一个节点的next给到cur.next从而指向其他节点dele原有节点消失cur.next=dele.next;}private NodeList findRemoveKey(int key){NodeList cur=this.head;//cur.next不等于null数值while(cur.next!=null){if(cur.next.value==key){return cur;}//cur.next节点获取下一个curcur = cur.next;}return null;}@Overridepublic void removeAll(int key) {if(this.head==null){return;}NodeList pre=this.head;NodeList cur=pre.next;//cur！=null说明有数据while(cur!=null){//value值为key进入循环if(cur.value==key){//pre的下个节点为cur的下一个节点，取消掉cur=key这个节点的链接pre.next=cur.next;cur=cur.next;}else{//如果不等于pre要跳到cur的位置来继续作为前一项pre=cur;//cur获取下一项cur=cur.next;}}//不要忽略头部，如果是key要替换掉if(this.head.value==key){this.head=this.head.next;}}@Overridepublic void addIndex(int index, int data)throws ErrorRuntimeExcepetion {//给一个位置，放入data元素//如果index的值小于0或者大于本身长度抛出异常显示下标try {if(index<0||index>size()){throw new ErrorRuntimeExcepetion("范围不准确"+index);}}catch (ErrorRuntimeExcepetion e){e.printStackTrace();return;}//如果index的位置是0或者index的位置是最后一个if(index==0){addFirst(data);}if(index==size()){addLast(data);}//走到这里index的值为其范围内容，首先获取index-1的位置NodeList cur = searchPre(index);//生成data元素链表NodeList node=new NodeList(data);if(cur==null){return;}//将原来cur.index的地址赋值给node.index来后移node.next=cur.next;//将现在的cur.index的地址指向nodecur.next=node;}private NodeList searchPre(int index){NodeList cur=this.head;//求一个index-1的范围int count=0;while(count<index-1){cur=cur.next;count++;}//获取到index-1位置的curreturn cur;}@Overridepublic void display() {//创建一个对象接收head值，来进行打印NodeList cur=this.head;//cur不等于nullwhile(cur!=null){//通过cur引用value来打印元素System.out.print(cur.value+" ");//通过next中下一个节点的地址来访问元素cur=cur.next;}System.out.println();}@Overridepublic boolean contains(int data) {//链表中是否包含dataNodeList cur=this.head;if(cur.value==data){//如果value是data返回truereturn true;}else{while(cur.next!=null){//循环每个节点判断是否为dataif(cur.next.value==data){return true;}cur=cur.next;}}return false;}@Overridepublic int size() {//获取链表的元素大小NodeList cur = this.head;//如果cur中为null没有任何元素大小是0if (cur == null) {return 0;}int count=0;//计数while(cur!=null){count++;cur=cur.next;}return count;}@Overridepublic void clean() {if(this.head==null){return;}//将每个节点置为空属性并且回收NodeList cur=this.head;while(cur!=null){NodeList curNext=cur.next;cur.next=null;cur=curNext;}//置空nullthis.head=null;}
}

Test代码：

public class Test {public static void main(String[] args) {MyLinkedList myLinkedList=new MyLinkedList();//这里创建链表对象
//    myLinkedList.createLinkedList();//访问创建的链表myLinkedList.addFirst(10);myLinkedList.addFirst(10);myLinkedList.addLast(10);myLinkedList.addLast(10);myLinkedList.addIndex(3,39);myLinkedList.addIndex(5,10);System.out.println(myLinkedList.contains(39));myLinkedList.display();myLinkedList.remove(39);myLinkedList.removeAll(10);myLinkedList.display();myLinkedList.clean();myLinkedList.addFirst(1);myLinkedList.display();System.out.println("链表中的元素大小为"+myLinkedList.size());}
}

#运行结果