转载请注明本文出处：http://www.cnblogs.com/Starshot/p/6918569.html
链表的结构是由一个一个节点组成的，所谓链，就是每个节点的头尾连在一起。而单向链表就是：每个节点包含了当前节点的值和下一个节点引用。双向链表就是每个节点包含了当前节点的值和上下两个节点的引用。相对于数组结构，链表的增删效率会更加高。
这边文章主要讲怎么用Java实现一个简单的链表结构：单向无环链表。以及实现一些数据处理的方法。
首先，新建一个节点类（本次例子中的节点值都是字符串类型）：
1 public class Node { 2 3 private String value; 4 private Node next; 5 6 public Node(String value){ 7 this.value=value; 8 } 9 public Node(){ 10 11 } 12 13 public String getValue(){ 14 return value; 15 } 16 17 public Node getnext(){ 18 return next; 19 } 20 21 public void setValue(String value){ 22 this.value=value; 23 } 24 25 public void setNext(Node next){ 26 this.next=next; 27 } 28 }
然后再建一个链表类：
public class MyLinkedTable { Node head=new Node(); //向链表中增加值 public boolean add(String str){ Node node=new Node(str); if(head.getnext()==null){ head.setNext(node);; return true; } Node tmp=head; while(tmp.getnext()!=null){ tmp=tmp.getnext(); } tmp.setNext(node); return true; } //已知某个节点，然后删除该节点 public boolean delete(Node node){ Node next=node.getnext(); Node nextAddress=next.getnext(); String nextValue=next.getValue(); node.setNext(nextAddress); node.setValue(nextValue); return true; } //删除第index个节点，index从1开始 public boolean delete(int index){ if(index>length()||index<1){ return false; } int i=1; Node temp=head.getnext(); while(i<index){ temp=temp.getnext(); i++; } Node next=temp.getnext(); Node nextAddress=next.getnext(); String nextValue=next.getValue(); temp.setNext(nextAddress); temp.setValue(nextValue); return true; } //获得第index个节点的值 public String get(int index){ if(index>length()||index<1){ return null; } int i=1; Node temp=head.getnext(); while(i<index){ temp=temp.getnext(); i++; } return temp.getValue(); } //获取链表里面数据的长度，也就是插入了多少个值。 public int length(){ if(head.getnext()==null){ return 0; } int i=1; Node temp=head.getnext(); while((temp=temp.getnext())!=null){ i++; } return i; } //反转链表 public void reverseTable(){ Node node1=head.getnext(); if(node1==null){ return; } Node preNode=null; Node curNode=node1; while(true){ Node origNextNode=curNode.getnext(); curNode.setNext(preNode); if(origNextNode==null){ head.setNext(curNode); break; } preNode=curNode; curNode=origNextNode; } } //获取中间链表 public String getMid(){ Node slowPointer=this.head.getnext(),fastPointer=this.head.getnext(); while(fastPointer!=null&&fastPointer.getnext()!=null&&fastPointer.getnext().getnext()!=null){ slowPointer=slowPointer.getnext(); fastPointer=fastPointer.getnext().getnext(); } return slowPointer.getValue(); } //删除重复链表 public void deleteDuplicateNode(){ Node nodeCur=head.getnext(); if(nodeCur==null) return; while(nodeCur.getnext()!=null){ Node lastNode=nodeCur; Node compareNode=lastNode.getnext(); while(compareNode!=null){ if(nodeCur.getValue().equals(compareNode.getValue())){ lastNode.setNext(compareNode.getnext()); compareNode=compareNode.getnext(); }else{ lastNode=compareNode; compareNode=compareNode.getnext(); } } nodeCur=nodeCur.getnext(); } } }
需要说明一下，这个链表结构是以head为起始节点，head指向插入的第一个节点（反转后就是最后一个），head本身的value一直都是空的，它只作为起始节点入口存在，不参与节点的计数，所以链表的节点总数（插入数据总数）是不包括head在内的。
接下来对某些方法进行说明：
1.链表反转
//链表翻转就是把原来的1>2>3>4变成4>3>2>1，所以原来在最前面的节点要变成在最后面，最后面的要变成最前面 //就是head的地址引用要变成最后一个节点的，原来head后的第一个节点的地址引用要由第二的节点变为NULL,原来第二个节点的地址引用要由第三个节点变成第一个节点 //以此类推，一直翻转到最后一个。然后把head的地址引用变成最后一个。 //在这个链表里面，head的位置是一直不变的，它永远是最前面，在head之后的节点才开始翻转。 public void reverseTable(){ Node node1=head.getnext(); if(node1==null){ return; } Node preNode=null; Node curNode=node1; while(true){ Node origNextNode=curNode.getnext(); curNode.setNext(preNode); if(origNextNode==null){ head.setNext(curNode); break; } preNode=curNode; curNode=origNextNode; } }
2.获得中间节点：
//通过用快慢指针来找到中间节点，快指针的速度为慢指针的两倍，慢指针一次走一个节点，快指针一次走两个节点， //当快指针走到尽头时，慢指针刚好为中间值，当快指针走到倒数第二个节点时，慢指针为上中位数。 //fastPointer!=null用来判断链表表内除head外有没有其它节点，fastPointer.getnext()!=null判断是否为最后一个节点， //fastPointer.getnext().getnext()!=null判断是否为倒数第二个节点。 public String getMid(){ Node slowPointer=this.head.getnext(),fastPointer=this.head.getnext(); while(fastPointer!=null&&fastPointer.getnext()!=null&&fastPointer.getnext().getnext()!=null){ slowPointer=slowPointer.getnext(); fastPointer=fastPointer.getnext().getnext(); } return slowPointer.getValue(); }
3.删除具有相同值的节点（重复节点）：
//删除具有相同值的节点 //基本原理是用第一个节点的值和第二个节点值比较，然后和第三个节点比较，以此类推。此时第一个节点为当前节点nodeCur，第二第三以及之后的节点为比较节点compareNode //一轮比较完毕后，第二个节点就变成nodeCur，之后那些节点就是compareNode //如果遇到有相同的值的节点，就将该节点的上个节点的next值为该节点的下个节点：lastNode.setNext(compareNode.getnext())，此时该节点就在链表里失去引用了，就相当于删除了。 //所以需要lastNode引用来保存当前比较节点的上一个节点 public void deleteDuplicateNode(){ Node nodeCur=head.getnext(); if(nodeCur==null) return; while(nodeCur.getnext()!=null){ Node lastNode=nodeCur; Node compareNode=lastNode.getnext(); while(compareNode!=null){ if(nodeCur.getValue().equals(compareNode.getValue())){ lastNode.setNext(compareNode.getnext()); compareNode=compareNode.getnext(); }else{ lastNode=compareNode; compareNode=compareNode.getnext(); } } nodeCur=nodeCur.getnext(); } }
写好之后可以测试一下：
public class Test { public static void main(String[] args) { MyLinkedTable m=new MyLinkedTable(); m.add("1"); m.add("2"); m.add("3"); m.add("4"); m.add("5"); m.add("6"); for(int i=1;i<=m.length();i++){ System.out.println(i+":"+m.get(i)); } System.out.println("length:"+m.length()); m.reverseTable(); for(int i=1;i<=m.length();i++){ System.out.println(i+":"+m.get(i)); } System.out.println("length:"+m.length()); m.delete(2); for(int i=1;i<=m.length();i++){ System.out.println(i+":"+m.get(i)); } System.out.println("length:"+m.length()); System.out.println(m.getMid()); } }
运行输出如下：
1:1
2:2
3:3
4:4
5:5
6:6
length:6
1:6
2:5
3:4
4:3
5:2
6:1
length:6
1:6
2:4
3:3
4:2
5:1
length:5
3
还有测试删除重复节点的：
public class Test2 { public static void main(String[] args) { MyLinkedTable m=new MyLinkedTable(); m.add("1"); m.add("2"); m.add("3"); m.add("2"); m.add("2"); m.add("6"); for(int i=1;i<=m.length();i++){ System.out.println(i+":"+m.get(i)); } System.out.println("length:"+m.length()); m.deleteDuplicateNode(); for(int i=1;i<=m.length();i++){ System.out.println(i+":"+m.get(i)); } System.out.println("length:"+m.length()); } }
运行输出：
1:1
2:2
3:3
4:2
5:2
6:6
length:6
1:1
2:2
3:3
4:6
length:4
以上就是用java实现单向无环链表的详细过程和解释，如果不妥之处，欢迎指出。