链表数据结构
链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个元素由一个存储本身的节点和一个指向下一个元素的引用（指针）组成。下图展示了一个链表的结构：
NeatReader-1547536785071.png
相对于传统的数组，链表的一个好处在于，添加或移除元素的时候不需要移动其他元素。然而，链表需要使用指针，因此实现链表时需要额外注意。数组的另一个细节是可以直接访问任何位置的任何元素，而想要访问链表中间的一个元素，需要从起点开始迭代列表直到找到所需的元素。
链表的js实现
单向链表
单向链表只元素间只存在单向引用的链表。上面的图表示的就是单向链表的结构。
function LinkedList() {
let Node = function (element) {
this.element = element
this.next = null
}
let length = 0
let head = null
this.append = function (element) { // 向链表尾部加一个元素
let node = new Node(element)
let current
if (head === null) {
head = node
} else {
current = head
while (current.next) {
current = current.next
}
current.next = node
}
length++
}
this.removeAt = function (position) { // 移除指定位置的元素
if (position > -1 && position < length) {
let current = head
previous,
index = 0
if (position === 0) {
head = current.next
} else {
while (index++ < position) {
previous = current
current = current.next
}
previous.next = current.next
}
length--
return current.element
} else {
return null
}
}
this.insert = function (position, element) { // 在任意位置插入元素
if (position >= 0 && position <= length) {
let node = new Node(element),
current = head,
previous,
index = 0
if (position === 0) {
node.next = current
head = node
} else {
while (index++ < position) {
previous = current
current = current.next
}
node.next = current
previous.next = node
}
length++
return true
} else {
return false
}
}
this.toString = function () {
let current = head,
string = ''
while (current) {
string += current.element + (current.next ? ',' : '')
current = current.next
}
return string
}
this.indexOf = function (element) {
let current = head,
index = 0
while (current) {
if (element === current.element) {
return index
}
index++
current = current.next
}
return -1
}
this.remove = function (element) {
let index = this.indexOf(element)
return this.removeAt(index)
}
this.isEmpty = function () {
return length === 0
}
this.size = function () {
return length
}
this.getHead = function () {
return head
}
}
双向链表
双向链表只一个节点包含上节点和下节点的引用。因此称为双向的。如下图:
NeatReader-1547537580674.png
function DoubleLinkedList() {
let Node = function (element) {
this.element = element
this.next = null
this.prev = null
}
let length = 0
let head = null
let tail = null
this.append = function (element) {
let node = new Node(element),
current
if (head === null) {
head = node
tail = node
} else {
current = tail
current.next = node
node.prev = current
tail = node
}
length++
}
this.insert = function (position, element) {
if (position >= 0 && position <= length) {
let node = new Node(element),
current = head,
previous,
index = 0
if (position === 0) {
if (!head) {
head = node
tail = node
} else {
node.next = current
current.prev = node
head = node
}
} else if (position === length) {
current = tail
current.next = node
node.prev = current
tail = node
} else {
while (index++ < position) {
previous = current
current = current.next
}
node.next = current
previous.next = node
current.prev = node
node.prev = previous
}
length++
return true
} else {
return false
}
}
this.removeAt = function (position) {
if (position > -1 && position < length) {
let current = head,
previous,
index = 0
if (position === 0) {
head = current.next
if (length === 1) {
tail = null
} else {
head.prev = null
}
} else if (position === length - 1) {
current = tail
tail = current.prev
tail.next = null
} else {
while (index++ < position) {
previous = current
current = current.next
}
previous.next = current.next
current.next.prev = previous
}
length--
return current.element
} else {
return null
}
}
// 其他方法实现和单向链表一样
}
循环链表
循环链表指链表的尾部链表的头部之间存在引用，因此形成了一个循环。如下图:
单向循环链表
NeatReader-1547537771149.png
双向循环链表
NeatReader-1547537822210.png
下面是单向循环链表的实现，双向循环链表的实现大同小异。
unction CircularLinkedList() {
const Node = function (element) {
this.element = element
this.next = null
}
let head = null
let length = 0
this.append = function (element) {
let node = new Node(element)
let current
if (head === null) {
head = node
} else {
current = head
while (current.next !== head) {
current = current.next
}
current.next = node
node.next = head
length++
}
}
this.removeAt = function (position) {
if (position > -1 && position < length) {
let current = head,
previous,
index = 0
if (position === 0) {
while (current.next !== head) {
current = current.next
}
head = head.next
current.next = head
} else {
while (index++ < position) {
previous = current
current = current.next
}
previous.next = current.next
}
length--
return current.element
} else {
return null
}
}
this.insert = function (position, element) {
if (position >= 0 && position <= length) {
let node = new Node(element),
current = head,
previous,
index = 0
if (position === 0) {
node.next = current
while (current.next !== head) {
current = current.next
}
head = node
current.next = head
} else {
while (index++ < position) {
previous = current
current = current.next
}
previous.next = node
node.next = current
if (node.next === null) {
node.next = head
}
}
length++
return true
} else {
return false
}
}
// 其他方法实现和单向链表一样
}
总结
链表对比数组主要有以下有优缺点：
- 数组添加或者移除元素需要移动其他的元素，而链表不用，链表只需要改动相邻的元素即可。
- 数组可以直接访问指定位置的元素，而链表则需要从表头开始迭代直至找到指定位置的元素。
网友评论