链表LinkedList的实现
所谓链表是由一组不必相连【不必相连:可以连续也可以不连续】的内存结构 【节点】,按特定的顺序链接在一起的抽象数据类型。
每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(可以称为指针)组成。
现实中也有不少链表的例子,例如火车一节一节的车厢,每节车厢之间都是相互连接的,我们就可以把每节车厢看做一个元素,车厢与车厢之间的连接就是指针。
LinkedList
类包括如下的这些方法:
append(element)
:向列表尾部添加一个新元素。removeAt(position)
:删除列表中指定位置的元素。insert(position, element)
:删除列表中指定位置的元素。indexOf(element)
:返回指定元素在列表中的位置。remove(element)
:删除指定元素。isEmpty()
:列表是否为空。size()
:列表的大小。
以append(element)
为例,向LinkedList
对象尾部添加一个元素时,可能存在两种情况:列表为空,添加是列表的第一个元素;列表不为空,则向其追加元素。
使用head
记录链表的第一个元素,当链表为空时,直接将元素赋值给head
。当不为空时,使用current
维护当前元素便于理解,然后一直遍历到链表的末尾,在末尾追加该元素,即将原链表最后一个元素的next
指向新元素。最后,维护length
的值。
其余的实现方式不再赘述,具体看实现细节。
const LinkedList = (function () {
let head = null,
length = 0
const Node = class {
constructor(element) {
this.element = element
this.next = null
}
}
class LinkedList {
//向列表尾部添加一个新元素
append(element) {
let node = new Node(element)
if (head === null) {
head = node
} else {
let current = head
while (current.next) {
current = current.next
}
current.next = node
}
length++
}
//删除列表中指定位置的元素
removeAt(position) {
if (position > -1 && position < length) {
let current = head
if (position === 0) {
head = current.next
} else {
let index = 0,
prev = null
while (index++ < position) {
prev = current
current = current.next
}
prev.next = current.next
}
length--
return current.element
}
return null
}
//向列表指定位置新增一个元素
insert(position, element) {
if (position > -1 && position < length) {
let current = head,
node = new Node(element)
if (position === 0) {
node.next = current
head = node
} else {
let index = 0,
prev = null
while (index++ < position) {
prev = current
current = current.next
}
prev.next = node
node.next = current
}
length++
return true
}
return false
}
//返回指定元素在列表中的位置
indexOf(element) {
let current = head,
index = -1
while (current) {
if (current.element === element) {
return index
}
current = current.next
index++
}
return -1
}
//删除指定元素
remove(element) {
const position = this.indexOf(element)
return this.removeAt(position)
}
//是否为空
isEmpty() {
return length === 0
}
//列表长度
size() {
return length
}
//第一个元素,便于外部迭代
getHead() {
return head
}
toString() {
let current = head,
str = ''
while (current) {
str += `element:${current.element} next: ${current.next ? `${current.next.element}\r\n` : 'null'}`
current = current.next
}
return str
}
}
return LinkedList
}())
const linkedList = new LinkedList()
linkedList.append('a')
linkedList.append('b')
linkedList.insert(1, 'c')
linkedList.append('hello wolrd')
linkedList.removeAt(2)
console.log(linkedList.toString());
//输出结果为
// element:a next: c
// element:c next: hello wolrd
// element:hello wolrd next: null
如果您觉得本文对您有用,欢迎捐赠或留言~
- 本博客所有文章除特别声明外,均可转载和分享,转载请注明出处!
- 本文地址:https://www.leevii.com/?p=1130