链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。
单向链表
每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（指针）组成
比如火车，每节车皮都是列表的元素，车皮间的连接就是指针
好处：添加和移除元素的时候不需要移动其他元素
坏处：想要访问链表中的一个元素，需要从起点开始迭代列表直到找到所需的元素
创建链表
下面是简易的创建链表，扩展见后面
function LinkedList() {
/* 创建一个辅助类，表示要加入列表的项 */
var Node = function(element) {
this.element = element; //添加到列表的值
this.next = null; //指向列表中下一个节点项的指针
};
var length = 0; //列表项的数量
var head = null; //第一个节点的引用
this.append = function(element) {};
this.insert = function(position, element) {};
this.removeAt = function(position) {};
this.remove = function(element) {};
this.indexOf = function(element) {};
this.isEmpty = function() {};
this.size = function() {};
this.toString = function() {};
this.print = function() {};
}
.append(element)向链表尾部追加元素
有两种场景：列表为空，添加的是第一个元素；列表不为空，向其后追加元素
this.append = function(element) {
var node = new Node(element),
current;
//列表中的第一个节点
if (head === null) {
head = node;
} else {
//从表头开始循环列表，直到找到最后一项，并赋值给current
current = head;
while(current.next) {
current = current.next;
}
//让current的next指针指向想要添加的节点
current.next = node;
}
length++; //更新列表的长度
};
.removeAt(position)从列表的指定位置移除一项
有两种场景： 移除第一个元素；移除第一个以外的任一元素
this.removeAt = function(position) {
//检查越界值
if (position > -1 && position < length) {
var current = head,
previous,
index = 0;
if (position === 0) {
//将head与current的下一项连接起来，跳过current，从而移除它
head = current.next; //移除第一项
} else {
while(index++ < position) {
previous = current; //要删除的元素的前一个元素
current = current.next; //要删除的元素
}
//将previous的指针与current的下一项连接起来，跳过current，从而移除它
previous.next = current.next;
}
length--;
return current.element;
} else {
return null;
}
};
.insert(position, element)在任意位置插入一个元素
先创建一个node元素，将node的指针（.next）指向current，然后将previous.next的值设为node
this.insert = function(position, element) {
if (position >= 0 && position <= length) {
var node = new Node(element),
current = head,
previous,
index = 0;
//在第一个位置添加
if (position === 0) {
node.next = current;
head = node;
} else {
while (index++ < position) {
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
}
length++;
return true;
} else {
return false;
}
};
.toString()将LinkedList对象转换成一个字符串
从起点开始，循环访问列表中的每一个元素，将得到的内容拼接成字符串
this.toString = function() {
var current = head,
string = "";
while (current) {
string = current.element;
current = current.next;
}
return string;
};
.indexOf(element)返回元素在列表中的位置
this.indexOf = function(element) {
var current = head,
index = 0;
while (current) {
if (element === current.element) {
return index;
}
index++;
current = current.next;
}
return -1;
};
.remove(element)从列表中移除一项
传入元素的值，调用indexOf()找到它的位置，调用removeAt()删除
this.remove = function(element) {
var index = this.indexOf(element);
return this.removeAt(index);
};
其他方法
this.isEmpty = function() {
return length === 0;
};
this.size = function() {
return length;
};
this.getHead = function() {
return head;
}
this.print = function() {
console.log(this.toString());
};
双向链表
好处：单向列表迭代列表时错过了要找的元素，就需要回到列表起点，重新迭代，而双向链表不需要
创建链表
function LinkedList() {
/* 创建一个辅助类，表示要加入列表的项 */
var Node = function(element) {
this.element = element; //添加到列表的值
this.next = null; //指向列表中下一个节点项的指针
this.prev = null; //指向列表中上一个节点项的指针
};
var length = 0; //列表项的数量
var head = null; //第一个节点的引用
var tail = null; //最后一个节点的引用
this.append = function(element) {};
this.insert = function(position, element) {};
this.removeAt = function(position) {};
this.remove = function(element) {};
this.indexOf = function(element) {};
this.isEmpty = function() {};
this.size = function() {};
this.toString = function() {};
this.print = function() {};
}
在任意位置插入一个新的元素
this.insert = function(position, element) {
if (position >= 0 && position <= length) {
var node = new Node(element),
current = head,
previous = null,
index = 0;
//在第一个位置添加
if (position === 0) {
if (!head) { //如果列表为空
head = node;
tail = node;
} else { //如果列表不为空
node.next = current;
current.prev = node;
head = node;
}
//在最后添加
} else if (position === length) {
current = tail;
current.next = node;
node.prev = current;
tail = node;
//在中间插入元素
} else {
while (index++ < position) {
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
current.prev = node;
node.prev = previous;
}
length++;
return true;
} else {
return false;
}
};
- 当在列表的第一个位置插入新元素：
- 如果列表为空，将head和tail指向这个新节点；
- 如果不为空，把node.next指向current（此时是对第一个元素的引用），同时current.prev指向node，并将node赋值给head
- 当在列表的最后插入新元素：
- current此时应引用tail，然后current.next指向node，node.prev指向current，同时将node赋值给tial
- 当在列表中间插入新元素：
- 先迭代列表，直到到达要找的位置
- 将node.next指向current，previous.next指向node
- 同时将current.prev指向node，node.prev指向previous
从任意位置移除元素
this.removeAt = function(position) {
//检查越界值
if (position > -1 && position < length) {
var current = head,
previous,
index = 0;
//移除第一个元素
if (position === 0) {
head = current.next;
if (length === 1) {
tail = null;
} else {
head.prev = null;
}
//移除最后一个元素
} else if (position === length -1) {
current = tail;
tail = current.prev;
tail.next = null;
//从中间移除一个元素
} else {
while (index++ < position) {
previous = current;
current = current.next;
}
previous.next = current.next;
current.next.prev = previous;
}
length--;
return current.element;
} else {
return null;
}
};
- 当移除第一个元素时：
- 将current.next复制给head，跳过current
- 然后将current.next.prev引用改为null（即head.prev = null）
- 如果列表只有一个元素，可以直接将tail设为null
- 当移除最后一个元素时：
- current此时应引用tail
- 将tail的引用更新为列表中倒数第二个元素（即tail = current.prev）
- 然后将tail的next指针设为null，以删除current
- 当从列表中间移除元素时：
- 通过更新previous.next和current.next.prev的引用，在列表中跳过它