文本主要內(nèi)容：
一、鏈表結(jié)構(gòu)：
概念：
鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是基于指針實(shí)現(xiàn)的。我們把一個(gè)數(shù)據(jù)元素和一個(gè)指針稱為結(jié)點(diǎn)。
數(shù)據(jù)域：存數(shù)數(shù)據(jù)元素信息的域。
指針域：存儲(chǔ)直接后繼位置的域。
鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用指針把相互直接關(guān)聯(lián)的結(jié)點(diǎn)（即直接前驅(qū)結(jié)點(diǎn)或直接后繼結(jié)點(diǎn)）鏈接起來。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表稱為鏈表。
鏈表類型：
根據(jù)鏈表的構(gòu)造方式的不同可以分為：
二、單鏈表：
概念：
鏈表的每個(gè)結(jié)點(diǎn)中只包含一個(gè)指針域，叫做單鏈表（即構(gòu)成鏈表的每個(gè)結(jié)點(diǎn)只有一個(gè)指向直接后繼結(jié)點(diǎn)的指針）
單鏈表中每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)：
1、頭指針和頭結(jié)點(diǎn)：
單鏈表有帶頭結(jié)點(diǎn)結(jié)構(gòu)和不帶頭結(jié)點(diǎn)結(jié)構(gòu)兩種。
“鏈表中第一個(gè)結(jié)點(diǎn)的存儲(chǔ)位置叫做頭指針”，如果鏈表有頭結(jié)點(diǎn)，那么頭指針就是指向頭結(jié)點(diǎn)的指針。
頭指針?biāo)傅牟淮娣艛?shù)據(jù)元素的第一個(gè)結(jié)點(diǎn)稱作頭結(jié)點(diǎn)（頭結(jié)點(diǎn)指向首元結(jié)點(diǎn)）。頭結(jié)點(diǎn)的數(shù)據(jù)域一般不放數(shù)據(jù)（當(dāng)然有些情況下也可存放鏈表的長(zhǎng)度、用做監(jiān)視哨等）
存放第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)稱作第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)，或稱首元結(jié)點(diǎn)。
如下圖所示：
不帶頭結(jié)點(diǎn)的單鏈表如下：
帶頭結(jié)點(diǎn)的單鏈表如下圖：
關(guān)于頭指針和頭結(jié)點(diǎn)的概念區(qū)分，可以參考如下博客：
http://blog.csdn.net/hitwhylz/article/details/12305021
2、不帶頭結(jié)點(diǎn)的單鏈表的插入操作：
上圖中，是不帶頭結(jié)點(diǎn)的單鏈表的插入操作。如果我們?cè)诜堑谝粋€(gè)結(jié)點(diǎn)前進(jìn)行插入操作，只需要a(i-1)的指針域指向s，然后將s的指針域指向a(i)就行了；如果我們?cè)诘谝粋€(gè)結(jié)點(diǎn)前進(jìn)行插入操作，頭指針head就要等于新插入結(jié)點(diǎn)s，這和在非第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)前插入結(jié)點(diǎn)時(shí)的情況不同。另外，還有一些不同情況需要考慮。
因此，算法對(duì)這兩種情況就要分別設(shè)計(jì)實(shí)現(xiàn)方法。
3、帶頭結(jié)點(diǎn)的單鏈表的插入操作：（操作統(tǒng)一，推薦）
上圖中，如果采用帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)，算法實(shí)現(xiàn)時(shí)，p指向頭結(jié)點(diǎn)，改變的是p指針的next指針的值（改變頭結(jié)點(diǎn)的指針域），而頭指針head的值不變。
因此，算法實(shí)現(xiàn)方法比較簡(jiǎn)單，其操作與對(duì)其它結(jié)點(diǎn)的操作統(tǒng)一。
問題1：頭結(jié)點(diǎn)的好處：
頭結(jié)點(diǎn)即在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)的數(shù)據(jù)域中不存儲(chǔ)線性表的數(shù)據(jù)元素，其作用是為了對(duì)鏈表進(jìn)行操作時(shí)，可以對(duì)空表、非空表的情況以及對(duì)首元結(jié)點(diǎn)進(jìn)行統(tǒng)一處理，編程更方便。
問題2：如何表示空表：
無頭結(jié)點(diǎn)時(shí)，當(dāng)頭指針的值為空時(shí)表示空表； 有頭結(jié)點(diǎn)時(shí)，當(dāng)頭結(jié)點(diǎn)的指針域?yàn)榭諘r(shí)表示空表。
如下圖所示：
問題3：頭結(jié)點(diǎn)的數(shù)據(jù)域內(nèi)裝的是什么？
頭結(jié)點(diǎn)的數(shù)據(jù)域可以為空，也可存放線性表長(zhǎng)度等附加信息，但此結(jié)點(diǎn)不能計(jì)入鏈表長(zhǎng)度值。
三、單項(xiàng)鏈表的代碼實(shí)現(xiàn)：
1、結(jié)點(diǎn)類：
單鏈表是由一個(gè)一個(gè)結(jié)點(diǎn)組成的，因此，要設(shè)計(jì)單鏈表類，必須先設(shè)計(jì)結(jié)點(diǎn)類。結(jié)點(diǎn)類的成員變量有兩個(gè)：一個(gè)是數(shù)據(jù)元素，另一個(gè)是表示下一個(gè)結(jié)點(diǎn)的對(duì)象引用（即指針）。
步驟如下：
（1）頭結(jié)點(diǎn)的構(gòu)造（設(shè)置指針域即可）
（2）非頭結(jié)點(diǎn)的構(gòu)造
（3）獲得當(dāng)前結(jié)點(diǎn)的指針域
（4）獲得當(dāng)前結(jié)點(diǎn)數(shù)據(jù)域的值
（5）設(shè)置當(dāng)前結(jié)點(diǎn)的指針域
（6）設(shè)置當(dāng)前結(jié)點(diǎn)數(shù)據(jù)域的值
注：類似于get和set方法，成員變量是數(shù)據(jù)域和指針域。
代碼實(shí)現(xiàn)：
(1)List.java:（鏈表本身也是線性表，只不過物理存儲(chǔ)上不連續(xù)）
//線性表接口public interface List { //獲得線性表長(zhǎng)度 public int size(); //判斷線性表是否為空 public boolean isEmpty(); //插入元素 public void insert(int index, Object obj) throws Exception; //刪除元素 public void delete(int index) throws Exception; //獲取指定位置的元素 public Object get(int index) throws Exception;}(2)Node.java:結(jié)點(diǎn)類
//結(jié)點(diǎn)類public class Node { Object element; //數(shù)據(jù)域 Node next; //指針域 //頭結(jié)點(diǎn)的構(gòu)造方法 public Node(Node nextval) { this.next = nextval; } //非頭結(jié)點(diǎn)的構(gòu)造方法 public Node(Object obj, Node nextval) { this.element = obj; this.next = nextval; } //獲得當(dāng)前結(jié)點(diǎn)的指針域 public Node getNext() { return this.next; } //獲得當(dāng)前結(jié)點(diǎn)數(shù)據(jù)域的值 public Object getElement() { return this.element; } //設(shè)置當(dāng)前結(jié)點(diǎn)的指針域 public void setNext(Node nextval) { this.next = nextval; } //設(shè)置當(dāng)前結(jié)點(diǎn)數(shù)據(jù)域的值 public void setElement(Object obj) { this.element = obj; } public String toString() { return this.element.toString(); }}2、單鏈表類：
單鏈表類的成員變量至少要有兩個(gè)：一個(gè)是頭指針，另一個(gè)是單鏈表中的數(shù)據(jù)元素個(gè)數(shù)。但是，如果再增加一個(gè)表示單鏈表當(dāng)前結(jié)點(diǎn)位置的成員變量，則有些成員函數(shù)的設(shè)計(jì)將更加方便。
代碼實(shí)現(xiàn)：
(3)LinkList.java:單向鏈表類(核心代碼)
1 //單向鏈表類 2 public class LinkList implements List { 3 4 Node head; //頭指針 5 Node current;//當(dāng)前結(jié)點(diǎn)對(duì)象 6 int size;//結(jié)點(diǎn)個(gè)數(shù) 7 8 //初始化一個(gè)空鏈表 9 public LinkList()10 {11 //初始化頭結(jié)點(diǎn)，讓頭指針指向頭結(jié)點(diǎn)。并且讓當(dāng)前結(jié)點(diǎn)對(duì)象等于頭結(jié)點(diǎn)。12 this.head = current = new Node(null);13 this.size =0;//單向鏈表，初始長(zhǎng)度為零。14 }15 16 //定位函數(shù)，實(shí)現(xiàn)當(dāng)前操作對(duì)象的前一個(gè)結(jié)點(diǎn)，也就是讓當(dāng)前結(jié)點(diǎn)對(duì)象定位到要操作結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)。17 //比如我們要在a2這個(gè)節(jié)點(diǎn)之前進(jìn)行插入操作，那就先要把當(dāng)前節(jié)點(diǎn)對(duì)象定位到a1這個(gè)節(jié)點(diǎn)，然后修改a1節(jié)點(diǎn)的指針域18 public void index(int index) throws Exception19 {20 if(index <-1 || index > size -1)21 {22 throw new Exception("參數(shù)錯(cuò)誤！"); 23 }24 //說明在頭結(jié)點(diǎn)之后操作。25 if(index==-1) //因?yàn)榈谝粋€(gè)數(shù)據(jù)元素結(jié)點(diǎn)的下標(biāo)是0，那么頭結(jié)點(diǎn)的下標(biāo)自然就是-1了。26 return;27 current = head.next;28 int j=0;//循環(huán)變量29 while(current != null&&j<index)30 {31 current = current.next;32 j++;33 }34 35 } 36 37 @Override38 public void delete(int index) throws Exception {39 // TODO Auto-generated method stub40 //判斷鏈表是否為空41 if(isEmpty())42 {43 throw new Exception("鏈表為空，無法刪除！");44 }45 if(index <0 ||index >size)46 {47 throw new Exception("參數(shù)錯(cuò)誤！");48 }49 index(index-1);//定位到要操作結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)對(duì)象。50 current.setNext(current.next.next);51 size--;52 }53 54 @Override55 public Object get(int index) throws Exception {56 // TODO Auto-generated method stub57 if(index <-1 || index >size-1)58 {59 throw new Exception("參數(shù)非法！");60 }61 index(index);62 63 return current.getElement();64 }65 66 @Override67 public void insert(int index, Object obj) throws Exception {68 // TODO Auto-generated method stub69 if(index <0 ||index >size)70 {71 throw new Exception("參數(shù)錯(cuò)誤！");72 }73 index(index-1);//定位到要操作結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)對(duì)象。74 current.setNext(new Node(obj,current.next));75 size++;76 }77 78 @Override79 public boolean isEmpty() {80 // TODO Auto-generated method stub81 return size==0;82 }83 84 @Override85 public int size() {86 // TODO Auto-generated method stub87 return this.size;88 }89 90 91 }3、測(cè)試類：（單鏈表的應(yīng)用）
使用單鏈表建立一個(gè)線性表，依次輸入十個(gè)0-99之間的隨機(jī)數(shù)，刪除第5個(gè)元素，打印輸出該線性表。
(4)Test.java:
1 public class Test { 2 3 public static void main(String[] args) throws Exception { 4 // TODO Auto-generated method stub 5 LinkList list = new LinkList(); 6 for (int i = 0; i < 10; i++) { 7 int temp = ((int) (Math.random() * 100)) % 100; 8 list.insert(i, temp); 9 System.out.PRint(temp + " ");10 }11 12 list.delete(4);13 System.out.println("/n------刪除第五個(gè)元素之后-------");14 for (int i = 0; i < list.size; i++) {15 System.out.print(list.get(i) + " ");16 }17 }18 19 }運(yùn)行效果：
四、開發(fā)可用的鏈表：
對(duì)于鏈表實(shí)現(xiàn)，Node類是整個(gè)操作的關(guān)鍵，但是首先來研究一下之前程序的問題：Node是一個(gè)單獨(dú)的類，那么這樣的類是可以被用戶直接使用的，但是這個(gè)類由用戶直接去使用，沒有任何的意義，即：Node這個(gè)類有用，但是不能讓用戶去用，只能讓LinkList類去調(diào)用，內(nèi)部類Node中完成。
于是，我們需要把Node類定義為內(nèi)部類，并且在Node類中去完成addNode和delNote等操作。使用內(nèi)部類的最大好處是可以和外部類進(jìn)行私有操作的互相訪問。
注：內(nèi)部類訪問的特點(diǎn)是：內(nèi)部類可以直接訪問外部類的成員，包括私有；外部類要訪問內(nèi)部類的成員，必須先創(chuàng)建對(duì)象。
1、增加數(shù)據(jù)：
代碼實(shí)現(xiàn)：
（1）LinkList.java:（核心代碼）
1 public class LinkList { 2 private Node root; //定義一個(gè)根節(jié)點(diǎn) 3 4 //方法：增加節(jié)點(diǎn) 5 public boolean add(String data) { 6 7 if (data == null) { // 如果添加的是一個(gè)空數(shù)據(jù)，那增加失敗 8 return false; 9 }10 11 // 將數(shù)據(jù)封裝為節(jié)點(diǎn)，目的：節(jié)點(diǎn)有next可以處理關(guān)系12 Node newNode = new Node(data);13 // 鏈表的關(guān)鍵就在于根節(jié)點(diǎn)14 if (root == null) { //如果根節(jié)點(diǎn)是空的，那么新添加的節(jié)點(diǎn)就是根節(jié)點(diǎn)。(第一次調(diào)用add方法時(shí)，根節(jié)點(diǎn)當(dāng)然是空的了)15 root = newNode;16 } else {17 root.addNode(newNode);18 19 }20 21 return true;22 23 }24 25 26 //定義一個(gè)節(jié)點(diǎn)內(nèi)部類（假設(shè)要保存的數(shù)據(jù)類型是字符串）27 //比較好的做法是，將Node定義為內(nèi)部類，在這里面去完成增刪、等功能，然后由LinkList去調(diào)用增、刪的功能28 class Node {29 private String data;30 private Node next; //next表示：下一個(gè)節(jié)點(diǎn)對(duì)象（單鏈表中）31 32 public Node(String data) {33 this.data = data;34 }35 36 public void addNode(Node newNode) {37 38 //下面這段用到了遞歸，需要反復(fù)理解39 if (this.next == null) { // 遞歸的出口：如果當(dāng)前節(jié)點(diǎn)之后沒有節(jié)點(diǎn)，說明我可以在這個(gè)節(jié)點(diǎn)后面添加新節(jié)點(diǎn)40 this.next = newNode; //添加新節(jié)點(diǎn)41 } else {42 this.next.addNode(newNode); //向下繼續(xù)判斷，直到當(dāng)前節(jié)點(diǎn)之后沒有節(jié)點(diǎn)為止43 44 }45 }46 }47 }代碼解釋：
14行：如果我們第一次調(diào)用add方法，那根結(jié)點(diǎn)肯定是空的，此時(shí)add的是根節(jié)點(diǎn)。
當(dāng)繼續(xù)調(diào)用add方法時(shí)，此時(shí)是往根節(jié)點(diǎn)后面添加數(shù)據(jù)，需要用到遞歸（42行），這個(gè)遞歸需要在內(nèi)部類中去完成。遞歸這段代碼需要去反復(fù)理解。
（2）LinkListDemo.java:
public class LinkListDemo { public static void main(String[] args) { LinkList list = new LinkList(); boolean flag = list.add("haha"); System.out.println(flag); }}運(yùn)行效果：
2、增加多個(gè)數(shù)據(jù)：
上面的操作是每次增加了一個(gè)對(duì)象，那么如果現(xiàn)在要求增加多個(gè)對(duì)象呢，例如：增加對(duì)象數(shù)組。可以采用循環(huán)數(shù)組的方式，每次都調(diào)用add()方法。
在上面的（1）LinkList.java中加入如下代碼：
1 //方法：增加一組數(shù)據(jù)2 public boolean addAll(String data[]) { // 一組數(shù)據(jù)3 for (int x = 0 ; x < data.length ; x ++) {4 if (!this.add(data[x])) { // 只要有一次添加不成功，那就是添加失敗5 return false ;6 }7 }8 return true ;9 }3、統(tǒng)計(jì)數(shù)據(jù)個(gè)數(shù)：
在一個(gè)鏈表之中，會(huì)保存多個(gè)數(shù)據(jù)（每一個(gè)數(shù)據(jù)都被封裝為Node類對(duì)象），那么要想取得這些保存元素的個(gè)數(shù)，可以增加一個(gè)size()方法完成。
具體做法如下：
在上面的（1）LinkList.java中增加一個(gè)統(tǒng)計(jì)的屬性count：
private int size ; // 統(tǒng)計(jì)個(gè)數(shù)
當(dāng)用戶每一次調(diào)用add()方法增加新數(shù)據(jù)的時(shí)候應(yīng)該做出統(tǒng)計(jì)：（下方第18行代碼）
1 //添加節(jié)點(diǎn) 2 public boolean add(String data) { 3 4 if (data == null) { // 如果添加的是一個(gè)空數(shù)據(jù)，那增加失敗 5 return false; 6 } 7 8 // 將數(shù)據(jù)封裝為節(jié)點(diǎn)，目的：節(jié)點(diǎn)有next可以處理關(guān)系 9 Node newNode = new Node(data);10 // 鏈表的關(guān)鍵就在于根節(jié)點(diǎn)11 if (root == null) { //如果根節(jié)點(diǎn)是空的，那么新添加的節(jié)點(diǎn)就是根節(jié)點(diǎn)。(第一次調(diào)用add方法時(shí)，根節(jié)點(diǎn)當(dāng)然是空的了)12 root = newNode;13 } else {14 root.addNode(newNode);15 16 }17 18 this.size++;19 return true;20 21 }而size()方法就是簡(jiǎn)單的將count這個(gè)變量的內(nèi)容返回：
//獲取數(shù)據(jù)的長(zhǎng)度 public int size() { return this.size; }4、判斷是否是空鏈表：
所謂的空鏈表指的是鏈表之中不保存任何的數(shù)據(jù)，實(shí)際上這個(gè)null可以通過兩種方式判斷：一種判斷鏈表的根節(jié)點(diǎn)是否為null，另外一個(gè)是判斷保存元素的個(gè)數(shù)是否為0。
在LinkList.java中添加如下代碼：
//判斷是否為空鏈表 public boolean isEmpty() { return this.size == 0; }5、查找數(shù)據(jù)是否存在：
現(xiàn)在如果要想查詢某個(gè)數(shù)據(jù)是否存在，那么基本的操作原理：逐個(gè)盤查，盤查的具體實(shí)現(xiàn)還是應(yīng)該交給Node類去處理，但是在盤查之前必須有一個(gè)前提：有數(shù)據(jù)存在。
在LinkList.java中添加查詢的操作：
1 //查詢數(shù)據(jù)是否存在2 public boolean contains(String data) { // 查找數(shù)據(jù)3 // 根節(jié)點(diǎn)沒有數(shù)據(jù)，查找的也沒有數(shù)據(jù)4 if (this.root == null || data == null) {5 return false; // 不需要進(jìn)行查找了6 }7 return this.root.containsNode(data); // 交給Node類處理8 }緊接著，在Node類之中，完成具體的查詢，查詢的流程： 判斷當(dāng)前節(jié)點(diǎn)的內(nèi)容是否滿足于查詢內(nèi)容，如果滿足返回true； 如果當(dāng)前節(jié)點(diǎn)的內(nèi)容不滿足，則向后繼續(xù)查，如果已經(jīng)沒有后續(xù)節(jié)點(diǎn)了，則返回false。
代碼實(shí)現(xiàn)：
1 //判斷節(jié)點(diǎn)是否存在 2 public boolean containsNode(String data) { // 查找數(shù)據(jù) 3 if (data.equals(this.data)) { // 與當(dāng)前節(jié)點(diǎn)數(shù)據(jù)吻合 4 return true; 5 } else { // 與當(dāng)前節(jié)點(diǎn)數(shù)據(jù)不吻合 6 if (this.next != null) { // 還有下一個(gè)節(jié)點(diǎn) 7 return this.next.containsNode(data); 8 } else { // 沒有后續(xù)節(jié)點(diǎn) 9 return false; // 查找不到10 }11 }12 }6、刪除數(shù)據(jù)：
在LinkList.java中加入如下代碼：
1 //方法：刪除數(shù)據(jù) 2 public boolean remove(String data) { //要?jiǎng)h除的節(jié)點(diǎn)，假設(shè)每個(gè)節(jié)點(diǎn)的data都不一樣 3 4 if (!this.contains(data)) { //要?jiǎng)h除的數(shù)據(jù)不存在 5 return false; 6 } 7 8 if (root != null) { 9 if (root.data.equals(data)) { //說明根節(jié)點(diǎn)就是需要?jiǎng)h除的節(jié)點(diǎn)10 root = root.next; //讓根節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)成為根節(jié)點(diǎn)，自然就把根節(jié)點(diǎn)頂?shù)袅寺铮ú幌駭?shù)組那樣，要將后面的數(shù)據(jù)在內(nèi)存中整體挪一位）11 } else { //否則12 root.removeNode(data);13 }14 }15 size--;16 return true;17 18 }注意第2代碼中，我們是假設(shè)刪除的這個(gè)String字符串是唯一的，不然就沒法刪除了。
刪除時(shí)，我們需要從根節(jié)點(diǎn)開始判斷，如果根節(jié)點(diǎn)是需要?jiǎng)h除的節(jié)點(diǎn)，那就直接刪除，此時(shí)下一個(gè)節(jié)點(diǎn)變成了根節(jié)點(diǎn)。
然后，在Node類中做節(jié)點(diǎn)的刪除：
//刪除節(jié)點(diǎn) public void removeNode(String data) { if (this.next != null) { if (this.next.data.equals(data)) { this.next = this.next.next; } else { this.next.removeNode(data); } } }7、輸出所有節(jié)點(diǎn)：
在LinkList.java中加入如下代碼：
1 //輸出所有節(jié)點(diǎn)2 public void print() {3 if (root != null) {4 System.out.print(root.data);5 root.printNode();6 System.out.println();7 }8 }然后，在Node類中做節(jié)點(diǎn)的輸出：
1 //輸出所有節(jié)點(diǎn)2 public void printNode() {3 if (this.next != null) {4 System.out.print("-->" + this.next.data);5 this.next.printNode();6 }7 }8、取出全部數(shù)據(jù)：
對(duì)于鏈表的這種數(shù)據(jù)結(jié)構(gòu)，最為關(guān)鍵的是兩個(gè)操作：刪除、取得全部數(shù)據(jù)。
在LinkList類之中需要定義一個(gè)操作數(shù)組的腳標(biāo)：
private int foot = 0; // 操作返回?cái)?shù)組的腳標(biāo)
在LinkList類中定義返回?cái)?shù)組，必須以屬性的形式出現(xiàn)，只有這樣，Node類才可以訪問這個(gè)數(shù)組并進(jìn)行操作：
private String [] retData ; // 返回?cái)?shù)組
在LinkList類之中增加toArray()的方法：
1 //方法：獲取全部數(shù)據(jù) 2 public String[] toArray() { 3 if (this.size == 0) { 4 return null; // 沒有數(shù)據(jù) 5 } 6 this.foot = 0; // 清零 7 this.retData = new String[this.size]; // 開辟數(shù)組大小 8 this.root.toArrayNode(); 9 return this.retData;10 }修改Node類的操作，增加toArrayNode()方法：
1 //獲取全部數(shù)據(jù)2 public void toArrayNode() {3 LinkList.this.retData[LinkList.this.foot++] = this.data;4 if (this.next != null) {5 this.next.toArrayNode();6 }7 }不過，按照以上的方式進(jìn)行開發(fā)，每一次調(diào)用toArray()方法，都要重復(fù)的進(jìn)行數(shù)據(jù)的遍歷，如果在數(shù)據(jù)沒有修改的情況下，這種做法是一種非常差的做法，最好的做法是增加一個(gè)修改標(biāo)記，如果發(fā)現(xiàn)數(shù)據(jù)增加了或刪除的話，表示要重新遍歷數(shù)據(jù)。
private boolean changeFlag = true ; // changeFlag == true：數(shù)據(jù)被更改了，則需要重新遍歷// changeFlag == false：數(shù)據(jù)沒有更改，不需要重新遍歷
然后，我們修改LinkList類中的toArray()方法：（其他代碼保持不變）
//方法：獲取全部數(shù)據(jù) public String[] toArray() { if (this.size == 0) { return null; // 沒有數(shù)據(jù) } this.foot = 0; // 清零 if (this.changeFlag == true) { // 內(nèi)容被修改了，需要重新取 this.retData = new String[this.size]; // 開辟數(shù)組大小 this.root.toArrayNode(); } return this.retData; }9、根據(jù)索引位置取得數(shù)據(jù)：
在一個(gè)鏈表之中會(huì)有多個(gè)節(jié)點(diǎn)保存數(shù)據(jù)，現(xiàn)在要求可以取得指定節(jié)點(diǎn)位置上的數(shù)據(jù)。但是在進(jìn)行這一操作的過程之中，有一個(gè)小問題：如果要取得數(shù)據(jù)的索引超過了數(shù)據(jù)的保存?zhèn)€數(shù)，那么是無法取得的。
在LinkList類之中，增加一個(gè)get()方法：
1 //方法：根據(jù)索引取得數(shù)據(jù)2 public String get(int index) {3 if (index > this.size) { // 超過個(gè)數(shù)4 return null; // 返回null5 }6 this.foot = 0; // 操作foot來定義腳標(biāo)7 return this.root.getNode(index);8 }在Node類之中配置getNode()方法：
1 //根據(jù)索引位置獲取數(shù)據(jù)2 public String getNode(int index) {3 if (LinkList.this.foot++ == index) { // 當(dāng)前索引為查找數(shù)值4 return this.data;5 } else {6 return this.next.getNode(index);7 }8 }10、清空鏈表：
所有的鏈表被root拽著，這個(gè)時(shí)候如果root為null，那么后面的數(shù)據(jù)都會(huì)斷開，就表示都成了垃圾：
//清空鏈表 public void clear() { this.root = null; this.size = 0; }總結(jié)：
上面的10條方法中，LinkList的完整代碼如下：
1 /** 2 * Created by smyhvae on 2015/8/27. 3 */ 4 5 public class LinkList { 6 7 private int size; 8 private Node root; //定義一個(gè)根節(jié)點(diǎn) 9 10 private int foot = 0; // 操作返回?cái)?shù)組的腳標(biāo) 11 private String[] retData; // 返回?cái)?shù)組 12 private boolean changeFlag = true; 13 // changeFlag == true：數(shù)據(jù)被更改了，則需要重新遍歷 14 // changeFlag == false：數(shù)據(jù)沒有更改，不需要重新遍歷 15 16 17 //添加數(shù)據(jù) 18 public boolean add(String data) { 19 20 if (data == null) { // 如果添加的是一個(gè)空數(shù)據(jù)，那增加失敗 21 return false; 22 } 23 24 // 將數(shù)據(jù)封裝為節(jié)點(diǎn)，目的：節(jié)點(diǎn)有next可以處理關(guān)系 25 Node newNode = new Node(data); 26 // 鏈表的關(guān)鍵就在于根節(jié)點(diǎn) 27 if (root == null) { //如果根節(jié)點(diǎn)是空的，那么新添加的節(jié)點(diǎn)就是根節(jié)點(diǎn)。(第一次調(diào)用add方法時(shí)，根節(jié)點(diǎn)當(dāng)然是空的了) 28 root = newNode; 29 } else { 30 root.addNode(newNode); 31 32 } 33 34 this.size++; 35 return true; 36 37 } 38 39 40 //方法：增加一組數(shù)據(jù) 41 public boolean addAll(String data[]) { // 一組數(shù)據(jù) 42 for (int x = 0; x < data.length; x++) { 43 if (!this.add(data[x])) { // 只要有一次添加不成功，那就是添加失敗 44 return false; 45 } 46 } 47 return true; 48 } 49 50 //方法：刪除數(shù)據(jù) 51 public boolean remove(String data) { //要?jiǎng)h除的節(jié)點(diǎn)，假設(shè)每個(gè)節(jié)點(diǎn)的data都不一樣 52 53 if (!this.contains(data)) { //要?jiǎng)h除的數(shù)據(jù)不存在 54 return false; 55 } 56 57 if (root != null) { 58 if (root.data.equals(data)) { //說明根節(jié)點(diǎn)就是需要?jiǎng)h除的節(jié)點(diǎn) 59 root = root.next; //讓根節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)成為根節(jié)點(diǎn)，自然就把根節(jié)點(diǎn)頂?shù)袅寺铮ú幌駭?shù)組那樣，要將后面的數(shù)據(jù)在內(nèi)存中整體挪一位） 60 } else { //否則 61 root.removeNode(data); 62 } 63 } 64 size--; 65 return true; 66 67 } 68 69 //輸出所有節(jié)點(diǎn) 70 public void print() { 71 if (root != null) { 72 System.out.print(root.data); 73 root.printNode(); 74 System.out.println(); 75 } 76 } 77 78 79 //方法：獲取全部數(shù)據(jù) 80 public String[] toArray() { 81 if (this.size == 0) { 82 return null; // 沒有數(shù)據(jù) 83 } 84 this.foot = 0; // 清零 85 this.retData = new String[this.size]; // 開辟數(shù)組大小 86 this.root.toArrayNode(); 87 return this.retData; 88 } 89 90 91 //獲取數(shù)據(jù)的長(zhǎng)度 92 public int size() { 93 return this.size; 94 } 95 96 //判斷是否為空鏈表 97 public boolean isEmpty() { 98 return this.size == 0; 99 }100 101 //清空鏈表102 public void clear() {103 this.root = null;104 this.size = 0;105 }106 107 108 //查詢數(shù)據(jù)是否存在109 public boolean contains(String data) { // 查找數(shù)據(jù)110 // 根節(jié)點(diǎn)沒有數(shù)據(jù)，查找的也沒有數(shù)據(jù)111 if (this.root == null || data == null) {112 return false; // 不需要進(jìn)行查找了113 }114 return this.root.containsNode(data); // 交給Node類處理115 }116 117 118 //方法：根據(jù)索引取得數(shù)據(jù)119 public String get(int index) {120 if (index > this.size) { // 超過個(gè)數(shù)121 return null; // 返回null122 }123 this.foot = 0; // 操作foot來定義腳標(biāo)124 return this.root.getNode(index);125 }126 127 128 //定義一個(gè)節(jié)點(diǎn)內(nèi)部類（假設(shè)要保存的數(shù)據(jù)類型是字符串）129 //比較好的做法是，將Node定義為內(nèi)部類，在這里面去完成增刪、等功能，然后由LinkList去調(diào)用增、刪的功能130 class Node {131 private String data;132 private Node next; //next表示：下一個(gè)節(jié)點(diǎn)對(duì)象（單鏈表中）133 134 public Node(String data) {135 this.data = data;136 }137 138 //添加節(jié)點(diǎn)139 public void addNode(Node newNode) {140 141 //下面這段用到了遞歸，需要反復(fù)理解142 if (this.next == null) { // 遞歸的出口：如果當(dāng)前節(jié)點(diǎn)之后沒有節(jié)點(diǎn)，說明我可以在這個(gè)節(jié)點(diǎn)后面添加新節(jié)點(diǎn)143 this.next = newNode; //添加新節(jié)點(diǎn)144 } else {145 this.next.addNode(newNode); //向下繼續(xù)判斷，直到當(dāng)前節(jié)點(diǎn)之后沒有節(jié)點(diǎn)為止146 147 }148 }149 150 151 //判斷節(jié)點(diǎn)是否存在152 public boolean containsNode(String data) { // 查找數(shù)據(jù)153 if (data.equals(this.data)) { // 與當(dāng)前節(jié)點(diǎn)數(shù)據(jù)吻合154 return true;155 } else { // 與當(dāng)前節(jié)點(diǎn)數(shù)據(jù)不吻合156 if (this.next != null) { // 還有下一個(gè)節(jié)點(diǎn)157 return this.next.containsNode(data);158 } else { // 沒有后續(xù)節(jié)點(diǎn)159 return false; // 查找不到160 }161 }162 }163 164 165 //刪除節(jié)點(diǎn)166 public void removeNode(String data) {167 if (this.next != null) {168 if (this.next.data.equals(data)) {169 this.next = this.next.next;170 } else {171 this.next.removeNode(data);172 }173 }174 175 }176 177 //輸出所有節(jié)點(diǎn)178 public void printNode() {179 if (this.next != null) {180 System.out.print("-->" + this.next.data);181 this.next.printNode();182 }183 }184 185 //獲取全部數(shù)據(jù)186 public void toArrayNode() {187 LinkList.this.retData[LinkList.this.foot++] = this.data;188 if (this.next != null) {189 this.next.toArrayNode();190 }191 }192 193 194 //根據(jù)索引位置獲取數(shù)據(jù)195 public String getNode(int index) {196 if (LinkList.this.foot++ == index) { // 當(dāng)前索引為查找數(shù)值197 return this.data;198 } else {199 return this.next.getNode(index);200 }201 }202 203 204 }205 }四、單鏈表的效率分析：
在單鏈表的任何位置上插入數(shù)據(jù)元素的概率相等時(shí)，在單鏈表中插入一個(gè)數(shù)據(jù)元素時(shí)比較數(shù)據(jù)元素的平均次數(shù)為：
刪除單鏈表的一個(gè)數(shù)據(jù)元素時(shí)比較數(shù)據(jù)元素的平均次數(shù)為：
因此，單鏈表插入和刪除操作的時(shí)間復(fù)雜度均為O（n）。另外，單鏈表讀取數(shù)據(jù)元素操作的時(shí)間復(fù)雜度也為O（n）。
2、順序表和單鏈表的比較：
順序表：
優(yōu)點(diǎn)：主要優(yōu)點(diǎn)是支持隨機(jī)讀取，以及內(nèi)存空間利用效率高；
缺點(diǎn)：主要缺點(diǎn)是需要預(yù)先給出數(shù)組的最大數(shù)據(jù)元素個(gè)數(shù)，而這通常很難準(zhǔn)確作到。當(dāng)實(shí)際的數(shù)據(jù)元素個(gè)數(shù)超過了預(yù)先給出的個(gè)數(shù)，會(huì)發(fā)生異常。另外，順序表插入和刪除操作時(shí)需要移動(dòng)較多的數(shù)據(jù)元素。
單鏈表：
優(yōu)點(diǎn)：主要優(yōu)點(diǎn)是不需要預(yù)先給出數(shù)據(jù)元素的最大個(gè)數(shù)。另外，單鏈表插入和刪除操作時(shí)不需要移動(dòng)數(shù)據(jù)元素；
缺點(diǎn)：主要缺點(diǎn)是每個(gè)結(jié)點(diǎn)中要有一個(gè)指針，因此單鏈表的空間利用率略低于順序表的。另外，單鏈表不支持隨機(jī)讀取，單鏈表取數(shù)據(jù)元素操作的時(shí)間復(fù)雜度為O（n）；而順序表支持隨機(jī)讀取，順序表取數(shù)據(jù)元素操作的時(shí)間復(fù)雜度為O（1）。
新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
