單向鏈表（單鏈表）的Java實現(xiàn)

T_Per_Lib 2014-04-23

展開全文

　　最近被問到鏈表，是一個朋友和我討論Java的時候說的。說實話，我學習編程的近一年時間里，學到的東西還是挺少的。語言是學了Java和C#，關于Web的學了一點Html+css+javascript。因為比較偏好，學習WinForm時比較認真，數(shù)據(jù)庫操作也自己有所研究。但鏈表這個東西我還真沒有學習和研究過，加上最近自己在看WPF，而課程也到了JSP了，比較緊。

　　但是我還是抽了一個晚上加半天的時間看了一下單向鏈表。并且使用Java試著寫了一個實例出來。沒有接觸過鏈表的朋友可以作為參考，希望大家多提寶貴意見。

　　當然，我們首先解釋一下什么是鏈表。就我所知，鏈表是一種數(shù)據(jù)結構，和數(shù)組同級。比如，Java中我們使用的ArrayList，其實現(xiàn)原理是數(shù)組。而LinkedList的實現(xiàn)原理就是鏈表了。我的老師說，鏈表在進行循環(huán)遍歷時效率不高，但是插入和刪除時優(yōu)勢明顯。那么他有著愈十年的編程經(jīng)驗，我是相信的。不過不知道他是否是說雙向鏈表，我們在此呢只對單向鏈表做一個了解。

　　鏈表（Chain本文所說鏈表均為單向鏈表，以下均簡稱單向鏈表）實際上是由節(jié)點（Node）組成的，一個鏈表擁有不定數(shù)量的節(jié)點。而向外暴露的只有一個頭節(jié)點（Head），我們對鏈表的所有操作，都是直接或者間接地通過其頭節(jié)點來進行的。

　　節(jié)點（Node）是由一個需要儲存的對象及對下一個節(jié)點的引用組成的。也就是說，節(jié)點擁有兩個成員：儲存的對象、對下一個節(jié)點的引用。

　　這樣說可能大家不是很明白，我貼一張圖大家可能更容易理解。

　　那么大家可能清除了，為什么說有了頭節(jié)點就可以操作所有節(jié)點。因為有著不斷的引用嘛！

　　那么在鏈表里的屬性大概就只有兩個了：頭節(jié)點和節(jié)點數(shù)量。當然，根據(jù)需要，我們通常需要更多的屬性。

　　簡單的鏈表可以寫為下面的樣子：

 1 package myChain;
 2 
 3 /**
 4  * （單向）鏈表
 5  * 
 6  * @author Johness
 7  */
 8 public class PersonChain {
 9     private PersonChainNode head; // 頭節(jié)點
10     private int size; // 鏈表的實體（即節(jié)點的數(shù)量）
11     private int modCount; // 鏈表被操作的次數(shù)（備用）
12 
13     /**
14      * 獲得鏈表中節(jié)點數(shù)量
15      * 
16      * @return 鏈表中節(jié)點數(shù)
17      */
18     public int getSize() {
19         return this.size;
20     }
21 
22     /**
23      * 添加節(jié)點的一般方法
24      * 
25      * @param p
26      *            添加到鏈表節(jié)點的對象 由于實現(xiàn)細節(jié)，作為唯一標識，同一個編號的Person只能添加一次
27      */
28     public void addNode(Person p) {
29         if (!contains(p.personNo)) { // 如果鏈表中沒有該對象，則準備添加
30             if (head != null) { // 如果有頭節(jié)點，則添加新節(jié)點作為頭節(jié)點
31                 head = new PersonChainNode((myChain.Person) p, head);
32                 size++;
33                 modCount++;
34             } else { // 如果沒有頭節(jié)點，則添加對象作為頭節(jié)點
35                 head = new PersonChainNode((myChain.Person) p, null);
36                 size++;
37                 modCount++;
38             }
39         }
40     }
41 }

　　以上的代碼就是一般鏈表的骨架了。擁有兩個重要屬性。

　　那么做為能添加到鏈表的節(jié)點又該長什么樣子呢？

　　我們可以寫作如下：

 1 package myChain;
 2 
 3 /**
 4  * （節(jié)點）實體，封裝了'人'這個對象和下一個實體的引用
 5  * 該實體將作為（單向）鏈表的節(jié)點
 6  * @author Johness
 7  */
 8 public class PersonChainNode {
 9     Person person;                            // 人
10     PersonChainNode nextNode;        // 該對象（'人'）保存的下一個對象的引用
11     
12     // 獲取當前實體對象（'人'）
13     public Person getPerson(){
14         return this.person;
15     }
16     
17     // 獲取下一個實體
18     public PersonChainNode getNextNode(){
19         return this.nextNode;
20     }
21     
22     // 構造方法
23     public PersonChainNode (Person p,PersonChainNode ep){
24         this.person = p;
25         this.nextNode = ep;
26     }
27 }

　　當然了，這只是個大概的樣子。

　　那么我最后在把層次梳理一下：鏈表是由不定數(shù)量的節(jié)點連接（通過相互之間的引用）起來的，由于這種關系，在鏈表里我們只定義了頭節(jié)點和節(jié)點數(shù)量。節(jié)點是由存儲的對象及對下一個“節(jié)點”的引用封裝而成。

　　在添加節(jié)點到鏈表中時，首先添加的節(jié)點后置后，新添加的節(jié)點作為頭節(jié)點引用前一個添加的節(jié)點。

　　廢話不多說，貼上我的例子，老師說我廢話多……

　?。ㄒ韵碌睦虞^為簡陋，大家不要笑話我哈）

 1 package myChain;
 2 
 3 /**
 4  * '人' 類
 5  * @author Johness
 6  * @version 1.0
 7  */
 8 public class Person {
 9     String name;        // 姓名
10     int age;                // 年齡
11     int personNo;     // 編號，用作唯一標識
12     
13     // 帶參構造方法
14     public Person(String name, int age, int personNo) {
15         this.name = name;
16         this.age = age;
17         this.personNo = personNo;
18     }
19 
20     // 獲取姓名
21     public String getName(){
22         return this.name;
23     }
24     
25     // 獲取年齡
26     public int getAge(){
27         return this.age;
28     }
29     
30     // 獲取編號
31     public int getPersonNo(){
32         return this.personNo;
33     }
34     
35     // 用于輸出的信息
36     public String toString(){
37         return "姓名：" + this.name + "\t年齡：" + this.age +"\t編號" + this.personNo;
38     }
39 }

 1 package myChain;
 2 
 3 /**
 4  * （節(jié)點）實體，封裝了'人'這個對象和下一個實體的引用
 5  * 該實體將作為（單向）鏈表的節(jié)點
 6  * @author Johness
 7  */
 8 public class PersonChainNode {
 9     Person person;                            // 人
10     PersonChainNode nextNode;        // 該對象（'人'）保存的下一個對象的引用
11     
12     // 獲取當前實體對象（'人'）
13     public Person getPerson(){
14         return this.person;
15     }
16     
17     // 獲取下一個實體
18     public PersonChainNode getNextEntity(){
19         return this.nextNode;
20     }
21     
22     // 構造方法
23     public PersonChainNode (Person p,PersonChainNode ep){
24         this.person = p;
25         this.nextNode = ep;
26     }
27     
28     // 構造方法
29     public PersonChainNode (Person p){
30         this.person = p;
31     }
32 }

  1 package myChain;
  2 
  3 /**
  4  * （單向）鏈表
  5  * 
  6  * @author Johness
  7  */
  8 public class PersonChain {
  9     private PersonChainNode head; // 頭節(jié)點
 10     private int size; // 鏈表的實體（即節(jié)點的數(shù)量）
 11     private int modCount; // 鏈表被操作的次數(shù)（備用）
 12 
 13     /**
 14      * 獲得鏈表中節(jié)點數(shù)量
 15      * 
 16      * @return 鏈表中節(jié)點數(shù)
 17      */
 18     public int getSize() {
 19         return this.size;
 20     }
 21 
 22     /**
 23      * 添加節(jié)點的一般方法
 24      * 
 25      * @param p
 26      *            添加到鏈表節(jié)點的對象 由于實現(xiàn)細節(jié)，作為唯一標識，同一個編號的Person只能添加一次
 27      */
 28     public void addNode(Person p) {
 29         if (!contains(p.personNo)) { // 如果鏈表中沒有該對象，則準備添加
 30             if (head != null) { // 如果有頭節(jié)點，則添加新節(jié)點作為頭節(jié)點
 31                 head = new PersonChainNode((myChain.Person) p, head);
 32                 size++;
 33                 modCount++;
 34             } else { // 如果沒有頭節(jié)點，則添加對象作為頭節(jié)點
 35                 head = new PersonChainNode((myChain.Person) p, null);
 36                 size++;
 37                 modCount++;
 38             }
 39         }
 40     }
 41 
 42     /**
 43      * 通過編號刪除對象
 44      * 
 45      * @param personNo
 46      *            要刪除對象的編號
 47      */
 48     public void deleteNode(int personNo) {
 49         if (size == 0) { // 如果當前鏈表節(jié)點數(shù)為零
 50             return;
 51         }
 52         if (size == 1) { 
 53             // 如果只有一個節(jié)點并且正是需要刪除的對象
 54             if (head.person.personNo == personNo) {
 55                 head = null;
 56                 size = 0;
 57             }
 58             return;
 59         }
 60         // 如果不存在該對象編號
 61         if (!contains(personNo)) {
 62             return;
 63         }
 64 
 65         // 較為復雜的刪除，定義整型保存被刪除的節(jié)點的索引
 66         //（刪除和索引都是不存在的，這里只是一個說法）
 67         int index = 0;
 68         // 循環(huán)遍歷，找到刪除節(jié)點的索引
 69         for (PersonChainNode p = head; p != null; p = p.nextNode) {
 70             if (!(p.person.personNo == personNo)) {
 71                 index++;
 72             } else {
 73                 break;
 74             }
 75         }
 76         // 如果刪除的是第一個節(jié)點（即頭節(jié)點）
 77         if (index == 0) {
 78             head = new PersonChainNode(head.nextNode.person,
 79                     head.nextNode.nextNode);    // 設置頭節(jié)點后一個節(jié)點為新的頭節(jié)點
 80             size--;                                            // 鏈表節(jié)點數(shù)減一
 81             modCount++;                                // 鏈表被操作次數(shù)加一
 82             return;
 83         }
 84         
 85         // 如果刪除的節(jié)點不是第一個節(jié)點
 86         // 循環(huán)遍歷，找到被刪除節(jié)點的前一個節(jié)點
 87         // 其索引下標用count保存
 88         int count = 0;
 89         for (PersonChainNode p = head; p != null; p = p.nextNode) {
 90             if (count == index - 1) {    // 如果找到了被刪除節(jié)點的前一個節(jié)點
 91                 if (index == size - 1) {    // 如果被刪除節(jié)點是最后一個節(jié)點
 92                     p.nextNode = null;    // 將被刪除節(jié)點的前一個節(jié)點的引用指向空引用
 93                 } else {                            // 如果被刪除節(jié)點不是最后一個節(jié)點
 94                     p.nextNode = p.nextNode.nextNode;    // 將被刪除節(jié)點前一個節(jié)點對其引用指向被刪除節(jié)點的下一個節(jié)點
 95                 }
 96                 size--;                // 減一數(shù)量
 97                 modCount++;    // 加一操作次數(shù)
 98                 return;
 99             }
100             count++;                // 沒有找到，索引加一
101         }
102     }
103 
104     /**
105      * 通過姓名查找對象
106      * 未實現(xiàn)
107      * @param name
108      *            對象姓名
109      * @return 對象數(shù)組，可能多個
110      */
111     public Person[] searchNodeByPersonName(String name) {
112         return null;
113     }
114 
115     /**
116      * 通過年齡查找對象
117      * 未實現(xiàn)
118      * @param age
119      *            對象年齡
120      * @return 對象數(shù)組，可能多個
121      */
122     public Person[] searchPersonByAge(int age) {
123         return null;
124     }
125 
126     /**
127      * 通過編號查找對象
128      * 由于編號是唯一標識，循環(huán)遍歷查找并返回即可
129      * @param personNo
130      *            對象編號
131      * @return 查找到的對象或者null
132      */
133     public Person searchNode(int personNo) {
134         Person p = null;
135         for (PersonChainNode pcn = head; pcn != null; pcn = pcn.nextNode) {
136             if (pcn.person.personNo == personNo) {
137                 p = pcn.person;
138             }
139         }
140         return p;
141     }
142 
143     /**
144      * 通過原對象修改及傳入值修改該對象屬性
145      * 
146      * @param personNo
147      *            要修改的對象編號
148      * @param value
149      *            通過傳入值的類型判斷修改 只能修改姓名或年齡
150      */
151     public void editNode(int personNo, Object value) {
152         // 通過作為唯一標識的編號查找到對象
153         Person target = searchNode(personNo);
154         if (target == null) {    // 如果對象為null
155             return;
156         }
157         if (value == null) {    // 如果傳入?yún)?shù)為null
158             return;
159         }
160         // 如果傳入?yún)?shù)為字符串類型
161         if (value.getClass() == java.lang.String.class) {
162             target.name = value.toString();
163             return;
164         }
165         try {
166             // 如果傳入?yún)?shù)為整型
167             target.age = Integer.parseInt(value.toString());
168             return;
169         } catch (Exception ex) {
170             // 如果傳入?yún)?shù)類型錯誤
171             return;
172         }
173     }
174 
175     /**
176      * 通過對象編號打印對象
177      * 
178      * @param personNo
179      *            對象編號
180      */
181     public void printNode(int personNo) {
182         Person target = searchNode(personNo);
183         if (target == null) {
184             return;
185         }
186         System.out.println(target.toString());
187     }
188 
189     /**
190      * 判斷指定對象是否存在鏈表中
191      * 
192      * @param personNo
193      *            對象編號
194      * @return true表示存在該對象，false表示不存在該對象
195      */
196     public boolean contains(int personNo) {
197         if (size != 0) {
198             for (PersonChainNode pcn = head; pcn != null; pcn = pcn.nextNode) {
199                 if (pcn.person.personNo == personNo) {
200                     return true;
201                 }
202             }
203         }
204         return false;
205     }
206 
207     // 排序方法
208 
209     /**
210      * 通過姓名排序
211      */
212     public void sortByPersonName() {
213     }
214 
215     /**
216      * 通過年齡排序
217      */
218     public void sortByPersonAge() {
219     }
220 
221     /**
222      * 默認排序，通過編號排序 
223      * 使用冒泡排序，增加了判斷以提高效率
224      */
225     public void sort() {
226         boolean jx = true;        // 冒泡排序的簡化方法
227         for (PersonChainNode pcn = head; pcn != null && jx; pcn = pcn.nextNode) {
228             jx = false;
229             for (PersonChainNode pc = head; pc != null && pc.nextNode != null; pc = pc.nextNode) {
230                 if (pc.person.personNo > pc.nextNode.person.personNo) {
231                     Person temp = pc.person;
232                     pc.person = pc.nextNode.person;
233                     pc.nextNode.person = temp;
234                     jx = true;
235                 }
236             }
237         }
238     }
239 
240     /**
241      * 打印整個鏈表
242      */
243     public void printAll() {
244         if (size != 0) {
245             for (PersonChainNode pcn = head; pcn != null; pcn = pcn.nextNode) {
246                 System.out.println(pcn.person.toString());
247             }
248         }
249     }
250 }