- 链表的概念
- 链表的实现
- 链表的多种形式
- LeeCode 题目
链表的概念
- 链表是有序的数据结构, 链表中的每个部分称为节点
- 可以在任意位置操作
- 可以从首、尾、中间进行数据存取
- 链表可以从首、尾、中间进行数据存取
- 链表的元素在内存中不必时连续的空间
- 优点:添加与删除不会导致其余元素位移
- 缺点: 无法根据索引快速定位元素
为什么不直接使用数组?
某些操作中链表的性能要比数组好
- 数组在内存中占用一段连续的空间
- 添加、移除会导致后续元素位移,(操作非末尾的数据时)性能开销大
小结:
- 获取、修改元素时, 数组效率高
- 添加、删除元素时, 链表效率高
链表的实现
要实现以下功能:
- 节点类: value、 next
- 链表类:
- addAtTail 尾部添加节点
- addAtHead 头部添加节点
- addAtIndex 指定位置添加节点
- get 获取节点
- removeAtIndex 删除指定节点
链表的实现
class LinkedNode {
constructor(value) {
this.value = value
this.next = null
}
}
class LinkedList {
constructor() {
this.count = 0
this.head = null
}
// 添加节点 尾
addAtTail (value) {
const node = new LinkedNode(value)
if (this.count === 0) {
this.head = node
} else {
let cur = this.head
while(cur.next != null) {
cur = cur.next
}
cur.next = node
}
this.count ++
}
// 添加节点 首
addAtHead (value) {
const node = new LinkedNode(value)
if (this.count === 0) {
this.head = node
} else {
node.next = this.head
this.head = node
}
this.count ++
}
// 根据索引 获取节点
get(index) {
if (this.count === 0 || index< 0 || index >= this.count) {
return
}
// 迭代链表, 找到对应节点
let current = this.head
for (let i = 0; i < index; i++) {
current = current.next
}
return current
}
// 根据索引 添加节点
addAtIndex(value, index) {
if (this.count ===0 || index >= this.count) {
return
}
// 如果 index <= 0 添加到头部
if (index <= 0) {
return this.addAtHead(value)
}
// 后面为正常区间处理
const prev = this.get(index -1)
const next = prev.next
const node = new LinkedNode(value)
prev.next = node
node.next = next
this.count++
}
// 删除
removeAtIndex (index) {
if (this.count === 0 || index < 0 || index >= this.count) {
return
}
if (index === 0) {
this.head = this.head.next
} else {
const prev = this.get(index -1)
prev.next = prev.next.next
}
this.count--
}
}
const l = new LinkedList();
链表的多种形式
常见的链表形式有:
循环链表(环形链表)
- 循环链表又称为环形链表, 指的是链表最后一个节点的 next 指向第一个节点, 形成首尾相连的循环结构, 称为循环列表
- 在实际使用中,环的结束点可以为链表的任意节点