單向鏈表在遍歷時只能從頭到尾或者從尾遍歷到頭；所以單向鏈表可以輕松到達下一節點，但是回到上一個節點是很困難的
而雙向鏈表既可以從頭遍歷到尾, 又可以從尾遍歷到頭，鏈表的相聯是雙向的，一個節點既有向前連接的引用，也有向后連接的引用
但是正因如此，雙向鏈表在插入或者刪除某個節點時，需要處理四個節點的引用，并且所占用內存空間也更大一些
雙向鏈表實現
JavaScript 代碼實現雙向鏈表
|
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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
|
// 創建雙向鏈表的構造函數function DoublyLinkedList() { // 創建節點構造函數 function Node(element) { this.element = element this.next = null this.prev = null // 新添加的 } // 定義屬性 this.length = 0 this.head = null this.tail = null // 新添加的 // 定義相關操作方法 // 在尾部追加數據 DoublyLinkedList.prototype.append = function (element) { // 1.根據元素創建節點 var newNode = new Node(element) // 2.判斷列表是否為空列表 if (this.head == null) { this.head = newNode this.tail = newNode } else { this.tail.next = newNode newNode.prev = this.tail this.tail = newNode } // 3.length+1 this.length++ } // 在任意位置插入數據 DoublyLinkedList.prototype.insert = function (position, element) { // 1.判斷越界的問題 if (position < 0 || position > this.length) return false // 2.創建新的節點 var newNode = new Node(element) // 3.判斷插入的位置 if (position === 0) { // 在第一個位置插入數據 // 判斷鏈表是否為空 if (this.head == null) { this.head = newNode this.tail = newNode } else { this.head.prev = newNode newNode.next = this.head this.head = newNode } } else if (position === this.length) { // 插入到最后的情況 // 思考: 這種情況是否需要判斷鏈表為空的情況呢? 答案是不需要, 為什么? this.tail.next = newNode newNode.prev = this.tail this.tail = newNode } else { // 在中間位置插入數據 // 定義屬性 var index = 0 var current = this.head var previous = null // 查找正確的位置 while (index++ < position) { previous = current current = current.next } // 交換節點的指向順序 newNode.next = current newNode.prev = previous current.prev = newNode previous.next = newNode } // 4.length+1 this.length++ return true } // 根據位置刪除對應的元素 DoublyLinkedList.prototype.removeAt = function (position) { // 1.判斷越界的問題 if (position < 0 || position >= this.length) return null // 2.判斷移除的位置 var current = this.head if (position === 0) { if (this.length == 1) { this.head = null this.tail = null } else { this.head = this.head.next this.head.prev = null } } else if (position === this.length -1) { current = this.tail this.tail = this.tail.prev this.tail.next = null } else { var index = 0 var previous = null while (index++ < position) { previous = current current = current.next } previous.next = current.next current.next.prev = previous } // 3.length-1 this.length-- return current.element } // 根據元素獲取在鏈表中的位置 DoublyLinkedList.prototype.indexOf = function (element) { // 1.定義變量保存信息 var current = this.head var index = 0 // 2.查找正確的信息 while (current) { if (current.element === element) { return index } index++ current = current.next } // 3.來到這個位置, 說明沒有找到, 則返回-1 return -1 } // 根據元素刪除 DoublyLinkedList.prototype.remove = function (element) { var index = this.indexOf(element) return this.removeAt(index) } // 判斷是否為空 DoublyLinkedList.prototype.isEmpty = function () { return this.length === 0 } // 獲取鏈表長度 DoublyLinkedList.prototype.size = function () { return this.length } // 獲取第一個元素 DoublyLinkedList.prototype.getHead = function () { return this.head.element } // 獲取最后一個元素 DoublyLinkedList.prototype.getTail = function () { return this.tail.element } // 遍歷方法的實現 // 正向遍歷的方法 DoublyLinkedList.prototype.forwardString = function () { var current = this.head var forwardStr = "" while (current) { forwardStr += "," + current.element current = current.next } return forwardStr.slice(1) } // 反向遍歷的方法 DoublyLinkedList.prototype.reverseString = function () { var current = this.tail var reverseStr = "" while (current) { reverseStr += "," + current.element current = current.prev } return reverseStr.slice(1) } // 實現toString方法 DoublyLinkedList.prototype.toString = function () { return this.forwardString() }} |
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持服務器之家。
原文鏈接：https://blog.csdn.net/Nozomi0609/article/details/114385562
