一：單向鏈表基本介紹
鏈表是一種數據結構，和數組同級。比如，Java中我們使用的ArrayList，其實現原理是數組。而LinkedList的實現原理就是鏈表了。鏈表在進行循環遍歷時效率不高，但是插入和刪除時優勢明顯。下面對單向鏈表做一個介紹。
單向鏈表是一種線性表，實際上是由節點(Node)組成的，一個鏈表擁有不定數量的節點。其數據在內存中存儲是不連續的，它存儲的數據分散在內存中，每個結點只能也只有它能知道下一個結點的存儲位置。由N各節點(Node)組成單向鏈表，每一個Node記錄本Node的數據及下一個Node。向外暴露的只有一個頭節點(Head)，我們對鏈表的所有操作，都是直接或者間接地通過其頭節點來進行的。
?
上圖中最左邊的節點即為頭結點(Head)，但是添加節點的順序是從右向左的，添加的新節點會被作為新節點。最先添加的節點對下一節點的引用可以為空。引用是引用下一個節點而非下一個節點的對象。因為有著不斷的引用，所以頭節點就可以操作所有節點了。
下圖描述了單向鏈表存儲情況。存儲是分散的，每一個節點只要記錄下一節點，就把所有數據串了起來，形成了一個單向鏈表。
?
節點(Node)是由一個需要儲存的對象及對下一個節點的引用組成的。也就是說，節點擁有兩個成員：儲存的對象、對下一個節點的引用。下面圖是具體的說明：
二、單項鏈表的實現
/***@authorAdministrator*/
public classMyLink {
Node head= null; //頭節點
/*** 鏈表中的節點，data代表節點的值，next是指向下一個節點的引用
*
*@authorzjn
**/
classNode {
Node next= null;//節點的引用，指向下一個節點
int data;//節點的對象，即內容
public Node(intdata) {this.data =data;
}
}/*** 向鏈表中插入數據
*
*@paramd*/
public void addNode(intd) {
Node newNode= new Node(d);//實例化一個節點
if (head == null) {
head=newNode;return;
}
Node tmp=head;while (tmp.next != null) {
tmp=tmp.next;
}
tmp.next=newNode;
}/***
*@paramindex:刪除第index個節點
*@return
*/
public boolean deleteNode(intindex) {if (index < 1 || index >length()) {return false;
}if (index == 1) {
head=head.next;return true;
}int i = 1;
Node preNode=head;
Node curNode=preNode.next;while (curNode != null) {if (i ==index) {
preNode.next=curNode.next;return true;
}
preNode=curNode;
curNode=curNode.next;
i++;
}return false;
}/***
*@return返回節點長度*/
public intlength() {int length = 0;
Node tmp=head;while (tmp != null) {
length++;
tmp=tmp.next;
}returnlength;
}/*** 在不知道頭指針的情況下刪除指定節點
*
*@paramn
*@return
*/
public booleandeleteNode11(Node n) {if (n == null || n.next == null) {return false;
}int tmp =n.data;
n.data=n.next.data;
n.next.data=tmp;
n.next=n.next.next;
System.out.println("刪除成功！");return true;
}public voidprintList() {
Node tmp=head;while (tmp != null) {
System.out.println(tmp.data);
tmp=tmp.next;
}
}public static voidmain(String[] args) {
MyLink list= newMyLink();
list.addNode(5);
list.addNode(3);
list.addNode(1);
list.addNode(2);
list.addNode(55);
list.addNode(36);
System.out.println("linkLength:" +list.length());
System.out.println("head.data:" +list.head.data);
list.printList();
list.deleteNode(4);
System.out.println("After deleteNode(4):");
list.printList();
}
}
三、鏈表相關的常用操作實現方法
1. 鏈表反轉
/*** 鏈表反轉
*
*@paramhead
*@return
*/
publicNode ReverseIteratively(Node head) {
Node pReversedHead=head;
Node pNode=head;
Node pPrev= null;while (pNode != null) {
Node pNext=pNode.next;if (pNext == null) {
pReversedHead=pNode;
}
pNode.next=pPrev;
pPrev=pNode;
pNode=pNext;
}this.head =pReversedHead;return this.head;
}
2. 查找單鏈表的中間節點
采用快慢指針的方式查找單鏈表的中間節點，快指針一次走兩步，慢指針一次走一步，當快指針走完時，慢指針剛好到達中間節點。
/*** 查找單鏈表的中間節點
*
*@paramhead
*@return
*/
publicNode SearchMid(Node head) {
Node p= this.head, q = this.head;while (p != null && p.next != null && p.next.next != null) {
p=p.next.next;
q=q.next;
}
System.out.println("Mid:" +q.data);returnq;
}
3. 查找倒數第k個元素
采用兩個指針P1,P2，P1先前移K步，然后P1、P2同時移動，當p1移動到尾部時，P2所指位置的元素即倒數第k個元素 。
/*** 查找倒數 第k個元素
*
*@paramhead
*@paramk
*@return
*/
public Node findElem(Node head, intk) {if (k < 1 || k > this.length()) {return null;
}
Node p1=head;
Node p2=head;for (int i = 0; i < k; i++)//前移k步
p1 =p1.next;while (p1 != null) {
p1=p1.next;
p2=p2.next;
}returnp2;
}
4. 對鏈表進行排序
/*** 排序
*
*@return
*/
publicNode orderList() {
Node nextNode= null;int tmp = 0;
Node curNode=head;while (curNode.next != null) {
nextNode=curNode.next;while (nextNode != null) {if (curNode.data >nextNode.data) {
tmp=curNode.data;
curNode.data=nextNode.data;
nextNode.data=tmp;
}
nextNode=nextNode.next;
}
curNode=curNode.next;
}returnhead;
}
5. 刪除鏈表中的重復節點
/*** 刪除重復節點*/
public voiddeleteDuplecate(Node head) {
Node p=head;while (p != null) {
Node q=p;while (q.next != null) {if (p.data ==q.next.data) {
q.next=q.next.next;
}elseq=q.next;
}
p=p.next;
}
}
6. 從尾到頭輸出單鏈表，采用遞歸方式實現
/*** 從尾到頭輸出單鏈表，采用遞歸方式實現
*
*@parampListHead*/
public voidprintListReversely(Node pListHead) {if (pListHead != null) {
printListReversely(pListHead.next);
System.out.println("printListReversely:" +pListHead.data);
}
}
7. 判斷鏈表是否有環，有環情況下找出環的入口節點
/*** 判斷鏈表是否有環，單向鏈表有環時，尾節點相同
*
*@paramhead
*@return
*/
public booleanIsLoop(Node head) {
Node fast= head, slow =head;if (fast == null) {return false;
}while (fast != null && fast.next != null) {
fast=fast.next.next;
slow=slow.next;if (fast ==slow) {
System.out.println("該鏈表有環");return true;
}
}return !(fast == null || fast.next == null);
}/*** 找出鏈表環的入口
*
*@paramhead
*@return
*/
publicNode FindLoopPort(Node head) {
Node fast= head, slow =head;while (fast != null && fast.next != null) {
slow=slow.next;
fast=fast.next.next;if (slow ==fast)break;
}if (fast == null || fast.next == null)return null;
slow=head;while (slow !=fast) {
slow=slow.next;
fast=fast.next;
}returnslow;
}
轉載自：https://blog.csdn.net/jianyuerensheng/article/details/51200274
)
![[譯]Java 垃圾回收介紹](http://pic.xiahunao.cn/[譯]Java 垃圾回收介紹)
