服务器之家:专注于服务器技术及软件下载分享
分类导航

node.js|vue.js|jquery|angularjs|React|json|js教程|

服务器之家 - 编程语言 - JavaScript - js教程 - JavaScript数据结构之双向链表

JavaScript数据结构之双向链表

2022-02-13 17:19希魔王的塔罗牌 js教程

这篇文章主要为大家详细介绍了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

延伸 · 阅读

精彩推荐
  • js教程JavaScript实现消消乐的源代码

    JavaScript实现消消乐的源代码

    这篇文章主要介绍了JavaScript实现消消乐-源代码,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以...

    代码100分12182021-12-30
  • js教程详解uniapp的全局变量实现方式

    详解uniapp的全局变量实现方式

    这篇文章主要介绍了详解uniapp的全局变量实现方式,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下...

    茧君11012021-12-29
  • js教程微信小程序 接入腾讯地图的两种写法

    微信小程序 接入腾讯地图的两种写法

    这篇文章主要介绍了微信小程序 接入腾讯地图的两种写法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参...

    木早长泉8852021-12-30
  • js教程原生JavaScript实现幻灯片效果

    原生JavaScript实现幻灯片效果

    这篇文章主要为大家详细介绍了原生JavaScript实现幻灯片效果,文中安装步骤介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...

    清水拌墨茶4792022-01-21
  • js教程绘制微信小程序验证码功能的实例代码

    绘制微信小程序验证码功能的实例代码

    这篇文章主要介绍了绘制微信小程序验证码功能的实例代码,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参...

    WALL*E8852021-12-27
  • js教程原生js实现九宫格拖拽换位

    原生js实现九宫格拖拽换位

    这篇文章主要为大家详细介绍了原生js实现九宫格拖拽换位,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...

    _小木不是木_11992022-01-07
  • js教程JavaScript 防盗链的原理以及破解方法

    JavaScript 防盗链的原理以及破解方法

    这篇文章主要介绍了JavaScript 防盗链的原理以及破解方法,帮助大家更好的理解和使用JavaScript,感兴趣的朋友可以了解下...

    LuckyChou10352021-12-22
  • js教程js实现移动端轮播图滑动切换

    js实现移动端轮播图滑动切换

    这篇文章主要为大家详细介绍了js实现移动端轮播图滑动切换,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...

    浪漫前端11542021-12-15