最近被問到鏈表，是一個朋友和我討論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é)點的引用。
這樣說可能大家不是很明白，我貼一張圖大家可能更容易理解。
Java單鏈表基本操作的實現(xiàn)關鍵代碼如下所示：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
|
package com.tyxh.link; //節(jié)點類 public class Node { protected Node next; //指針域 protected int data;//數(shù)據(jù)域 public Node( int data) { this. data = data; } //顯示此節(jié)點 public void display() { System. out.print( data + " "); } } package com.tyxh.link; //單鏈表 public class LinkList { public Node first; // 定義一個頭結點 private int pos = 0;// 節(jié)點的位置 public LinkList() { this. first = null; } // 插入一個頭節(jié)點 public void addFirstNode( int data) { Node node = new Node(data); node. next = first; first = node; } // 刪除一個頭結點,并返回頭結點 public Node deleteFirstNode() { Node tempNode = first; first = tempNode. next; return tempNode; } // 在任意位置插入節(jié)點 在index的后面插入 public void add(int index, int data) { Node node = new Node(data); Node current = first; Node previous = first; while ( pos != index) { previous = current; current = current. next; pos++; } node. next = current; previous. next = node; pos = 0; } // 刪除任意位置的節(jié)點 public Node deleteByPos( int index) { Node current = first; Node previous = first; while ( pos != index) { pos++; previous = current; current = current. next; } if(current == first) { first = first. next; } else { pos = 0; previous. next = current. next; } return current; } // 根據(jù)節(jié)點的data刪除節(jié)點(僅僅刪除第一個) public Node deleteByData( int data) { Node current = first; Node previous = first; //記住上一個節(jié)點 while (current. data != data) { if (current. next == null) { return null; } previous = current; current = current. next; } if(current == first) { first = first. next; } else { previous. next = current. next; } return current; } // 顯示出所有的節(jié)點信息 public void displayAllNodes() { Node current = first; while (current != null) { current.display(); current = current. next; } System. out.println(); } // 根據(jù)位置查找節(jié)點信息 public Node findByPos( int index) { Node current = first; if ( pos != index) { current = current. next; pos++; } return current; } // 根據(jù)數(shù)據(jù)查找節(jié)點信息 public Node findByData( int data) { Node current = first; while (current. data != data) { if (current. next == null) return null; current = current. next; } return current; } } package com.tyxh.link; //測試類 public class TestLinkList { public static void main(String[] args) { LinkList linkList = new LinkList(); linkList.addFirstNode(20); linkList.addFirstNode(21); linkList.addFirstNode(19); //19,21,20 linkList.add(1, 22); //19,22,21,20 linkList.add(2, 23); //19,22,23,21,20 linkList.add(3, 99); //19,22,23,99,21,20 linkList.displayAllNodes(); // Node node = linkList.deleteFirstNode(); // System.out.println("node : " + node.data); // linkList.displayAllNodes(); // node = linkList.deleteByPos(2); // System.out.println("node : " + node.data); // linkList.displayAllNodes(); // linkList.deleteFirstNode(); Node node = linkList.deleteByData(19); // Node node = linkList.deleteByPos(0); System. out.println( "node : " + node. data); linkList.displayAllNodes(); Node node1 = linkList.findByPos(0); System. out.println( "node1: " + node1. data); Node node2 = linkList.findByData(22); System. out.println( "node2: " + node2. data); } } |
以上所述是小編給大家介紹的Java單鏈表基本操作的實現(xiàn)，希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會及時回復大家的。在此也非常感謝大家對服務器之家網(wǎng)站的支持！
原文鏈接：http://blog.csdn.net/tayanxunhua/article/details/11100097/
