数据结构学习二(基于JavaScript)----链表
链表是物理存储单元上的非连续的、非顺序的存储结构,由一系列节点组成。(本文提到的链表,均指单链表)。
关于链表的几个重要概念
1、节点
节点包含两部分,一部分是存储数据元素的数据域,一部分是存储指向下一个节点的指针。
var Node = function(data){
this.data = data;
this.next = null;
}
var node1 = new Node(3);
var node2 = new Node(5);
var node3 = new Node(7);
node1.next = node2;
node2.next = node3;
console.log(node1.next.data);//5
2、首尾节点
链表中的第一个节点是首节点,最后一个节点是尾节点。
3、有头链表和无头链表。
无头链表是指第一个节点即有数据域,又有指针域。
有头链表是指第一个节点只有指针域没有数据域。
链表的实现
// 定义链表类
function LinkList(){
// 定义节点
var Node = function(data){
this.data = data;
this.next = data;
}
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++;
return true;
}
// 插入
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);
//插入到第一个
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++;
curr_node = curr_node.next;
}
//当循环结束时
var next_node = curr_node.next;
curr_node.next = new_node;
new_node.next = next_node;
}
}
length++;
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++;
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--;
del_node.next = null;
return del_node.data;
}
}
//删除首节点
this.remove_head = function(){
// this.remove(0);
if(length==0){
return null;
}else if(length==1){
length = 0;
head = null;
tail = null;
return head.data;
}else{
var del_node = head;
head = head.next;
length--;
return del_node.data;
}
}
//删除尾节点
this.remove_tail = function(){
// this.remove(length-1);
if(length==0){
return null;
}else if(length==1){
var del_node = head;
head = null;
tail = null;
length = 0;
return del_node.data;
}else{
var del_index = 1;
var curr_node = head;
var pre_node = null;
while(del_index<length){
del_index++;
pre_node = curr_node;
curr_node = curr_node.next;
}
pre_node.next = null;
tail = pre_node;
length--;
return curr_node.data;
}
}
//获取指定位置的节点
this.get = function(index){
if(index<0||index>=length){
return null;
}else{
var curr_node = head;
var node_index = 0;
while(node_index<index){
node_index++;
curr_node = curr_node.next;
}
return curr_node.data;
}
}
//链表长度
this.length = function(){
return length;
}
//返回首节点
this.head = function(){
return head.data;
}
//返回尾节点
this.tail = function(){
return tail.data;
}
//打印链表
this.print = function(){
var curr_node = head;
while(curr_node){
console.log(curr_node.data);
curr_node = curr_node.next;
}
}
}
var link = new LinkList();
link.append(1);
link.append(3);
link.append(5);
// link.print();// 1 3 5 undefined
link.get(2);
链表的方法
append 添加一个元素
insert 在指定位置插入一个元素
remove 删除指定位置的节点
remove_head 删除首节点
remove_tail 删除尾节点
indexOf 返回指定元素的索引
get 返回指定位置的元素
head 返回首节点
tail 返回尾节点
length 返回链表长度
isEmpty 判断链表是否为空
clear 清空
print 打印整个链表
几个重要方法的实现思路
1、 insert 方法
append只能在链表的末尾添加元素,而insert可以在指定位置插入一个元素。
需要转入参数index,指定插入的位置。
该方法的关键是找到索引为index-1的节点,只有找到这个节点,才能将新的节点插入到链表中。
如果index==length 可以直接使用append方法
如果index>length或者index<0 ,索引错误,返回null
如果index == 0,创建新的节点new_node,这个新节点索引是0,因此是链表的首节点,让new_node.next = head,head = new_node.
如果index>0且index<length,同样创建新节点new_node ,变量curr_node指定head,insert_index=1,表示new_node 应该插入的位置,使用一个while循环,循环条件是
insert_index<index,在循环体内,insert_index加1,curr_node = curr_node.next,当循环结束时,curr_node就是new_node 的上一个节点,让new_node 指向curr_node
的下一个节点,而curr_node 指向new_node。
2、 remove 方法
找到index-1的节点,这个节点的next指向了要删除的节点
如果index<0或者index>=length,索引错误,返回null,
如果index==0,要删除的是首节点,del_node = head,head = head,next,返回del_node.
如果index>0,且index<length,使用while循环,找到要删除的位置。del_index表示要删除的节点索引,pre_node 表示被删除节点的上一个节点,
curr_node 表示被删除节点,while循环的条件是del_index<index,循环体内del_index+1,pre_node指点curr_node,curr_node指向自己的下一个几点。
3、 get 方法
传入参数 index
如果index<0或者index>=length,返回null。
index在0和length之间,用while循环找到索引位置元素,node_index从0开始,
curr_node指向head,while循环条件是node_index<index,循环内node_index+1,curr_node指向下一个节点。循环结束,curr_node就是索引为index的节点
基于链表实现栈和队列
1、栈的实现
//基于链表实现栈
function Stack(){
var linkList = new LinkList();
// 从栈顶添加元素
this.push = function(item){
linkList.append(item)
}
// 弹出栈顶元素
this.pop = function(){
return linkList.remove_tail();
}
// 返回栈顶元素
this.top = function(){
return linkList.tail();
}
//返回栈的大小
this.size = function(){
return linkList.length();
}
}
var s = new Stack();
s.push("a")
s.push("b")
s.push("c")
s.push("d")
// console.log(s.size());//4
console.log(s.pop());//'d'
console.log(s.top());//'c'
console.log(s.size());//3
2、队列的实现
function Queue(){
var 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();
}
}
var q = new Queue();
q.enqueue("q");
q.enqueue("w");
q.enqueue("e");
// console.log(q.head());//q
// console.log(q.tail());//e
// q.dequeue();
// console.log(q.head());//w ‘q’出队列了
链表的常见面试题
使用迭代和递归两种方式实现链表的翻转。
创建上下文环境
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;
}
}
1、迭代翻转
迭代翻转的思路
假设链表中间的某个节点为curr_node,它的前一个节点是pre_node,后一个节点是next_node.只考虑在curr_node这个节点上翻转。
curr_node.next = pre_node;
遍历链表,每完成一个节点的翻转,都让curr_node = next_node,找到下一个需要翻转的节点。同时pre_node和next_node也随着curr_node一起向后滑动。
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,指向翻转前链表的最后一个节点
return pre_node;
}
console.log(reverse_iter(node1));
// Node {
// data: 5,
// next: Node { data: 4, next: Node { data: 3, next: [Object] } } }
console.log(reverse_iter(node1));//Node { data: 1, next: null }
2、递归翻转
递归的思想在于“甩锅”,你做不到的事情,让别人去做,等别人做完了,你在别人的基础上继续做。
“甩锅” 分4步:
- 明确函数功能。reverse_digui(head)完成的功能是,从head开始翻转链表,函数返回值是翻转后的头节点。
- 进行递归调用。var new_head = reserver_digui(head.next)
- 计算结果 第二步中 已经完成了从head.next开始翻转链表,现在,只需要把head连接到新链表上就可以了,新链表的尾节点
是head.next,执行head.next.next = head,这样,head就成了新链表的的尾节点。 - 找到递归的终止条件。
function reserver_digui(head){
if(!head){
return null;
}
if(head.next==null){
return head;
}
var new_head = reserver_digui(head.next);
head.next.next = head;
head.next = null;
return new_head;
}
print(reserver_digui(node1)) //5 4 3 2 1