- 链表是物理存储上非连续的、非顺序的存储结构，由一系列结点构成。
- 无头链表是指第一个结点既有数据域，又有指针域，第一个结点既是首节点又是头节点
- 有头链表是指第一个节点只有指针域，而没有数据域
链表的方法
- append 添加一个新的元素
- insert 在指定位置插入一个元素
- remove 删除指定位置的结点
- remove_head 删除首节点
- remove_tail 删除尾结点
- indexOf 返回指定元素的索引
- get 返回指定索引位置的元素
- head 返回首节点
- tail 返回尾结点
- length 返回链表长度
- isEmpty 判断链表是否为空
- clear 清空链表
- print 打印整个链表
结点
- 结点包含两部分，一部分是存储数据的数据域，一部分是存储指向下一个结点的指针域。
var Node = function(data) {
this.data = data
this.next = null
}
链表的实现
function LinkList() {
// 定义节点
var Node = function(data) {
this.data = data
this.next = null
}
var length = 0 // 长度
var head = null // 头节点
var tail = null // 尾结点
// 添加结点
this.append = function(data) {
// 创建节点
var new_node = new Node(data)
if(head == null) {
head = new_node
tail = new_node
} else {
tail.next = new_node
tail = new_node
}
length += 1;
return true
}
// 打印节点
this.print = function() {
var curr_node = head
while(curr_node) {
console.log(curr_node.data)
curr_node = curr_node.next
}
}
this.insert = function(index, data) {
if(index < 0 && index > length) {
return false
} else if(index === length) {
return this.append(data)
} else {
var new_node = new Node(data)
// new_node变成新的头节点
if(index == 0) {
new_node.next = head
head = new_node
} else {
var insert_index = 1
var curr_node = head
while(insert_index < index){
insert_index += 1
curr_node = curr_node.next
}
// 当循环结束的时候
var next_node = curr_node.next
curr_node.next = new_node
new_node.next = next_node
}
length += 1
return true
}
}
// 移除节点
this.remove = function(index) {
if(index < 0 || index >= length) {
return null
} else {
var del_node = null
if(index == 0) {
del_node = head
head = head.next
} else {
var del_index = 0
var pre_node = null // 被删除节点的前一个节点
var curr_node = head // 要被删除的节点
while(del_index < index) {
del_index += 1
pre_node = curr_node
curr_node = curr_node.next
}
del_node = curr_node
// 被删除节点的前一个节点指向被删除节点的后一个节点
pre_node.next = curr_node.next
// 如果被删除的节点是尾结点
if(curr_node.next == null) {
tail = pre_node
}
}
length -= 1
del_node.next = null
return del_node.data
}
}
// 返回指定位置节点的值
this.get = function(index) {
if(index < 0 || index >= length) {
return null
}
var node_index = 0
var curr_node = head
while(node_index < index) {
node_index += 1
curr_node = curr_node.next
}
return curr_node.data
}
}
- 翻转链表
var Node = function(data) {
this.data = data
this.next = null
}
var node1 = new Node(1)
var node2 = new Node(2)
var node3 = new Node(3)
var node4 = new Node(4)
var node5 = new Node(5)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
function print(node) {
var curr_node = node
while(curr_node) {
console.log(curr_node.data)
curr_node = curr_node.next
}
}
function reverse_iter(head) {
if(!head) {
return null
}
var pre_node = null // 前一个节点
var curr_node = head // 当前要翻转的节点
while(curr_node) {
var next_node = curr_node.next // 下一个节点
curr_node.next = pre_node // 对当前节点进行翻转
pre_node = curr_node // pre_node 向后滑动
curr_node = next_node // curr_node 向后滑动
}
// 最后要返回 pre_node 当循环结束时, pre_node 指向翻转前链表的最后一个节点
return pre_node
}
print(reverse_iter(node1))
function reverse_digui(head) {
// 如果head 为null
if(!head) {
return null
}
if(head.next == null) {
return head
}
// 从下一个节点开始进行翻转
var new_head = reverse_digui(head.next)
head.next.next = head // 把当前节点连接到新链表上
head.next = null
return new_head
}
print(reverse_digui(node1))
网友评论