链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
- 创建链表
//有头链表 第一个节点只有指针域
//无头链表 第一个节点既有数据域又有指针域
//实现一个无头链表
function LinkList() {
let Node = function(data) {
this.next = null //指针
this.data = data //数据
}
let length = 0 //长度
let head = null //头节点
let tail = null //尾节点
//添加
this.append = function(data) {
const node = new Node(data)
//如果链表为空
if (head === null) {
head = node
tail = head //是第一个又是最后一个
} else {
tail.next = node //尾节点指向新创建的节点
tail = node //tail指向最后一个节点
}
length++
return true
}
//打印
this.print = function() {
let current_node = head
let printText = ''
while (current_node) {
printText += current_node.data.toString() + '-->'
current_node = current_node.next
}
printText += 'null'
return printText
}
//插入
this.insert = function(index, data) {
if (index < 0 || index > length) return false
let insert_node = new Node(data)
if (head === null) {
head = insert_node
tail = insert_node
length++
return true
}
//index为0 是首节点
if (index === 0) {
insert_node.next = head
head = insert_node
} else if (index === length) {
tail.next = insert_node
tail = insert_node
} else {
let current_node = head
let current_index = 1
while (current_index < index) {
current_node = current_node.next
current_index++
}
insert_node.next = current_node.next
current_node.next = insert_node
if (insert_node.next === null) {
tail = insert_node
}
}
length++
return true
}
//移除
this.remove = function(index) {
if (index < 0 || index >= length) return false
let remove_node = null
if (index === 0) {
remove_node = head
head = head.next
} else {
let current_index = 0
let current_node = head //当前节点 要被删除的节点
let prev_node = head //上一个节点
while (current_index < index) {
prev_node = current_node
current_node = current_node.next
current_index++
}
remove_node = current_node
prev_node.next = current_node.next
if (current_node.next === null) {
tail = prev_node
}
}
length--
return remove_node.data
}
//删除首节点
this.remove_head = function() {
return this.remove(0)
}
//删除尾节点
this.remove_tail = function() {
return this.remove(length - 1)
}
// 获取指定索引的内容
this.get = function(index) {
if (index < 0 || index >= length) return false
let current_index = 0
let current_node = head
while (current_index < index) {
current_node = current_node.next
current_index++
}
return current_node.data
}
//根据数据获取指定索引，多个相同数据只返回第一个的索引
this.indexOf = function(data) {
if (!data) return -1
let index = -1
let current_node = head
while (index < length - 1) {
index++
if (current_node.data === data) {
return index
}
current_node = current_node.next
}
return -1
}
//返回首节点
this.head = function() {
return head.data
}
//返回尾节点
this.tail = function() {
return tail.data
}
//返回链表长度
this.length = function() {
return length
}
//链表是否为空
this.isEmpty = function() {
return head === null
}
//清空链表
this.clear = function() {
head = null
tail = null
length = 0
}
}
const link = new LinkList()
link.append(1)
link.append(6)
link.append(3)
link.insert(2, 8)
link.print()
link.insert(1, 5)
link.print()
link.insert(5, 9)
link.print()
link.insert(0, 0)
link.print()
link.remove(3)
link.print()
link.remove(5)
link.print()
//console.log(link.get(3)) //8
console.log(link.indexOf(5))
- 用链表实现栈
function Stack() {
const link = new LinkList()
//压入栈中
this.push = function(item) {
link.append(item)
}
//弹出栈顶元素
this.pop = function() {
return link.remove_tail()
}
//获取栈的长度
this.size = function() {
return link.length()
}
//获取栈顶元素
this.top = function() {
return link.tail()
}
//清空栈
this.clear = function() {
return link.clear()
}
//栈是否为空
this.isEmpty = function() {
return link.isEmpty()
}
}
- 用链表实现队列
function Queue() {
const link = new LinkList()
//加入队列
this.enqueue = function(item) {
link.append(item)
}
//移除队列
this.dequeue = function() {
return link.remove_head()
}
//获取队首
this.head = function() {
return link.head()
}
//获取队尾
this.tail = function() {
return link.tail()
}
//获取队列长度
this.size = function() {
return link.length()
}
//获取队列是否为空
this.isEmpty = function() {
return link.isEmpty()
}
//清空队列
this.clear = function() {
return link.clear()
}
}
- 翻转链表
// 迭代翻转
function reverse_iter(head) {
let current_node = head
let prev_node = null
while (current_node) {
let next_node = current_node.next
current_node.next = prev_node
prev_node = current_node
current_node = next_node
}
}
// 递归翻转
function reverse_digui(head) {
if (!head) {
return null
}
if (head.next === null) {
return head
}
let new_head = reverse_digui(head.next)
head.next.next = head
head.next = null
return new_head
}
- 合并两个有序链表
var Node = function(data) {
this.data = data
this.next = null
}
var node1 = new Node(1)
var node2 = new Node(4)
var node3 = new Node(9)
var node4 = new Node(2)
var node5 = new Node(5)
var node6 = new Node(6)
var node7 = new Node(10)
node1.next = node2
node2.next = node3
node4.next = node5
node5.next = node6
node6.next = node7
function merge_link(head1, head2) {
if (head1 === null) {
return head2
} else if (head2 === null) {
return head1
}
let cur1 = head1
let cur2 = head2
let merge_head = null
let merge_tail = null
while (cur1 && cur2) {
//数据进行比较取得最小值
let min_data = null
if (cur1.data <= cur2.data) {
min_data = cur1.data
cur1 = cur1.next
} else {
min_data = cur2.data
cur2 = cur2.next
}
if (merge_head == null) {
merge_head = new Node(min_data)
merge_tail = merge_head
} else {
let new_node = new Node(min_data)
merge_tail.next = new_node
merge_tail = new_node
}
}
//可能其中一个链表还有剩下的值
let result_node = null
if (cur1) {
result_node = cur1
}
if (cur2) {
result_node = cur2
}
while (result_node) {
let n_node = new Node(result_node.data)
merge_tail.next = result_node
merge_tail = result_node
result_node = result_node.next
}
return merge_head
}
print(merge_link(node1, node4))
function print (node) {
var curr_node = node
while (curr_node) {
console.log(curr_node.data, 33)
curr_node = curr_node.next
}
}
//查找链表中指定位置的值
function link_find(index, head) {
let curr_node = head
let current_index = 0
while (current_index < index) {
curr_node = curr_node.next
current_index++
}
return curr_node.data
}
//查找链表的中值
function link_middle(head) {
let current_node = head
let current_index = 0
while (current_node) {
current_node = current_node.next
current_index++
}
console.log(current_index, link_find(Math.floor(current_index / 2), head))
}
link_middle(node1)
