# 一、单链表
单链表结构:
function List () {
// 节点
let Node = function (element) {
this.element = element
this.next = null
}
// 初始头节点为 null
let head = null
// 链表长度
let length = 0
// 操作
this.getList = function() {return head}
this.search = function(list, element) {}
this.append = function(element) {}
this.insert = function(position, element) {}
this.remove = function(element){}
this.isEmpty = function(){}
this.size = function(){}
}
# 1. 追加节点:
**确定解题的数据结构:**单链表
确定解题思路: 初始化一个节点(待追加节点),遍历到链尾,在尾节点后插入该节点
画图实现:
确定边界条件: 当链表为 null
,直接将 head
指向待插入节点,不需要遍历
代码实现:
function append (element) {
let node = new Node(element),
p = head
if (!head){
head = node
} else {
while (p.next) {
p = p.next
}
p.next = node
}
length += 1
}
// 测试
let list = new List()
for(let i = 0; i < 5; i+=1) {
list.append(i)
}
# 2. 查找:
**确定解题的数据结构:**单链表
确定解题思路: 遍历单链表,判断节点值是否等于待查找值,相等则返回 true
,否则继续遍历下一个节点,直到遍历完整个链表还未找到,则返回 false
确定边界条件: 当链表为 null
,可直接返回 false
代码实现:
// 判断链表中是否存在某节点
function search(element) {
let p = head
if (!p) return false
while(p) {
if (p.element === element) return true
p = p.next
}
return false
}
// 测试
list.search(4) // true
list.search(11) // false
# 3. 在 position 位置插入:
**确定解题的数据结构:**单链表
确定解题思路: 初始化一个节点(待插入节点 node
),遍历到 position
前一个位置节点,在该节点后插入 node
画图实现:
确定边界条件:
- 当
position
为0
时,直接将插入节点node.next
指向head
,head
指向node
即可,不需要遍历 - 当待插入位置
position < 0
或超出链表长度position > length
,都是有问题的,不可插入,此时直接返回null
,插入失败
代码实现:
// 插入 position 的后继节点
function insert (position, element) {
// 创建插入节点
let node = new createNode(element)
if (position >= 0 && position <= length) {
let prev = head,
curr = head,
index = 0
if(position === 0) {
node.next = head
head = node
} else {
while(index < position) {
prev = curr
curr = curr.next
index ++
}
prev.next = node
node.next = curr
}
length += 1
} else {
return null
}
}
// 测试
list.insert(10)
# 4. 删除:
**确定解题的数据结构:**单链表
确定解题思路: 遍历单链表,找到待删除节点,删除
画图实现:
确定边界条件: 当链表为 null
,直接返回
代码实现:
// 删除值为 element 节点
function remove (element) {
let p = head, prev = head
if(!head) return
while(p) {
if(p.element === element) {
p = p.next
prev.next = p
} else {
prev = p
p = p.next
}
}
}
# 5. 复杂度分析:
查找:从头节点开始查找,时间复杂度为 O(n)
插入或删除:在某一节点后插入或删除一个节点(后继节点)的时间复杂度为 O(1)
# 二、双链表
顾名思义,单链表只有一个方向,从头节点到尾节点,那么双链表就有两个方向,从尾节点到头节点:
function DoublyLinkedList() {
let Node = function(element) {
this.element = element
// 前驱指针
this.prev = null
// 后继指针
this.next = null
}
// 初始头节点为 null
let head = null
// 新增尾节点
let tail = null
// 链表长度
let length = 0
// 操作
this.search = function(element) {}
this.insert = function(position, element) {}
this.removeAt = function(position){}
this.isEmpty = function(){ return length === 0 }
this.size = function(){ return length }
}
# 1. 在 position 位置插入节点:
确定解题的数据结构: 双链表
确定解题思路: 初始化一个节点(待插入节点 node
),遍历链表到 position
前一个位置节点,在该节点位置后插入 node
画图实现:
确定边界条件:
当待插入位置 position < 0
或超出链表长度 position > length
,都是有问题的,不可插入,此时直接返回 null
,插入失败
代码实现:
// 插入 position 的后继节点
function insert (position, element) {
// 创建插入节点
let node = new Node(element)
if (position >= 0 && position < length) {
let prev = head,
curr = head,
index = 0
if(position === 0) {
// 在第一个位置添加
if(!head) { // 注意这里与单链表不同
head = node
tail = node
} else {
// 双向
node.next = head
head.prev = node
// head 指向新的头节点
head = node
}
} else if(position === length) {
// 插入到尾节点
curr = tial
curr.next = node
node.prev = curr
// tail 指向新的尾节点
tail = node
} else {
while(index < position) {
prev = curr
curr = curr.next
index ++
}
// 插入到 prev 后,curr 前
prev.next = node
node.next = curr
curr.prev = node
node.prev = prev
}
length += 1
return true
} else {
return false
}
}
// 测试
list.insert(10)
# 2. 删除:
确定解题的数据结构: 双链表
确定解题思路: 遍历双链表,找到待删除节点,删除
画图实现:
确定边界条件: 当链表为 null
,直接返回
代码实现:
// 删除 position 位置的节点
function removeAt (position) {
if (position >= 0 && position < length && length > 0) {
let prev = head,
curr = head,
index = 0
if(position === 0) {
// 移除头节点
if(length === 1) { // 仅有一个节点
head = null
tail = null
} else {
head = head.next
head.prev = null
}
} else if(position === length-1) {
// 移除尾节点
curr = tial
tail = curr.prev
tail.next = null
} else {
while(index < position) {
prev = curr
curr = curr.next
index ++
}
// 移除curr
prev.next = curr.next
curr.next.prev = prev
}
length -= 1
return curr.element
} else {
return null
}
}
# 3. 查找:
双链表的查找和单链表类似,都是遍历链表,找到返回 true
,找不到返回 false
。
# 4. 复杂度分析:
查找:查找前驱节点或后继节点时间复杂度为 O(1),其它节点仍为 O(n)
插入或删除:插入或删除前驱节点或后继节点的时间复杂度都为 O(1)
# 三、循环单链表
循环单链表是一种特殊的单链表,它和单链表的唯一区别是:单链表的尾节点指向的是 NULL,而循环单链表的尾节点指向的是头节点,这就形成了一个首尾相连的环:
既然有循环单链表,当然也有循环双链表,循环双链表和双链表不同的是:
- 循环双链表的
tail.next
(tail
的后继指针) 为null
,循环双链表的tail.next
为head
- 循环双链表的
head.prev
(head
的前驱指针) 为null
,循环双链表的head.prev
为tail
这里以循环单列表为例
function CircularLinkedList() {
let Node = function(element) {
this.element = element
// 后继指针
this.next = null
}
// 初始头节点为 null
let head = null
// 链表长度
let length = 0
// 操作
this.search = function(element) {}
this.insert = function(positon, element) {}
this.removeAt = function(position){}
this.isEmpty = function(){ return length === 0 }
this.size = function(){ return length }
}
# 1. 在 positon 后插入:
确定解题的数据结构: 循环单链表
确定解题思路: 初始化一个节点(待插入节点 node
),遍历到 position
前一个位置节点,在该节点后插入 node
画图实现:
确定边界条件:
- 当
position
为0
时,需要遍历到尾节点,然后在尾节点后插入节点 , 并将head
指向 - 当待插入位置
position < 0
或超出链表长度position > length
,都是有问题的,不可插入,此时直接返回null
,插入失败
代码实现:
// 插入 position 的后继节点
function insert (position, element) {
// 创建插入节点
let node = new createNode(element)
if (position >= 0 && position <= length) {
let prev = head,
curr = head,
index = 0
if(position === 0) {
// 与单链表插入不同的
while(index < length) {
prev = curr
curr = curr.next
index ++
}
prev.next = node
node.next = curr
head = node
} else {
while(index < position) {
prev = curr
curr = curr.next
index ++
}
prev.next = node
node.next = curr
}
length += 1
} else {
return null
}
}
// 测试
list.insert(10)
# 2. 查找:
和单链表类似,唯一不同的是:循环单链表的循环结束条件为 index++ < length
// 判断链表中是否存在某节点
function search(element) {
if (!head) return false
let p = head, index = 0
// 和单链表的不同所在
while(index++ < length) {
if (p.element === element) return true
p = p.next
}
return false
}
// 测试
list.search(4) // true
list.search(11) // false
# 3. 删除:
和单链表类似,唯一不同的是:循环单链表的循环结束条件为 index++ < length
// 删除值为 element 节点
function remove (element) {
let p = head, prev = head, index = 0
// 空链表
if(!head || ) return
// 仅有一个节点且element一致
if(length === 1 && head.element === element){
head = null
length--
return
}
while(index++ < length) {
if(p.element === element) {
p = p.next
prev.next = p
length --
} else {
prev = p
p = p.next
}
}
}
# 4. 复杂度分析
查找:循环链表从任一节点开始查找目标节点,时间复杂度为 O(n)
插入或删除:它和单链表一样,后继节点插入及删除的时间复杂度为 O(1)