正文

JavaScript数据结构之双向链表

︶ㄣ速达网 メ
米米素材网V管理员 / 阅读
0720

这篇文章主要为大家详细介绍了JavaScript数据结构之双向链表，文中示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下

单向链表在遍历时只能从头到尾或者从尾遍历到头；所以单向链表可以轻松到达下一节点，但是回到上一个节点是很困难的

而双向链表既可以从头遍历到尾, 又可以从尾遍历到头，链表的相联是双向的，一个节点既有向前连接的引用，也有向后连接的引用

但是正因如此，双向链表在插入或者删除某个节点时，需要处理四个节点的引用，并且所占用内存空间也更大一些

JavaScript数据结构之双向链表

双向链表实现

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