链表
在需要存储大量的元素时数组可能是最常用的数据结构，但是也存在一定的局限性：数组的大小是固定的，在数组的起点或者中间插入（移除元素）的成本很高，需要移动数组元素。
链表是一种动态的数据结构。存储有序的元素集合，链表的元素在内存中不是连续放置的。
每个链表元素是由一个元素本身的节点和一个指向下一个元素的引用（指针）组成。
链表在添加或者移除元素时不需要移动元素，需要使用指针。但是在访问任何位置的元素的时候，数组是直接可以访问的，而链表则是从头（表头）开始迭代列表直到找到需要的元素为止。
如下：
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="ie=edge">
<title>链表</title>
</head>
<body>
<script>
//创建列表
function LinkedList() {
//链表的一个项
let Node = function(element) {
this.element = element; //表示该元素本身的一个节点
this.next = null; //指向下一个元素的引用（指针）
}
let lenth = 0;
let head = null; //第一个节点的引用
// 向列表尾部添加一个项，有两种场景，1列表为空，2列表不为空
this.append = function(element) {
let node = new Node(element),
current;
if (head === null) {
head = node
} else {
current = head
//循环列表，直到找到最后一项
while (current.next) {
current = current.next
}
//找到最后一项,把next设置为node,形成连接
current.next = node;
}
length++;
}
//向列表指定位置插入元素
this.insert = function(position, element) {
if (position >= 0 && position <= length) {
let node = new Node(element),
current,
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
}
}
//从列表中特定位置删除一个项
this.removeAt = function(position) {
//检查越界值
if (position > -1 && position < length) { //这是要删除元素的位置，先验证它是否有效
/**
* previous：当前元素的前一个元素
* current：要删除的元素
*/
let current = head,
previous,
index = 0;
//移除第一项
if (position === 0) {
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;
}
}
//删除列表中一个项
this.remove = function(element) {
let index = this.indexof(element);
return this.removeAt(index)
}
//返回元素在列表中的索引
this.indexof = function(element) {
let current = head,
index = 0;
while (current) {
if (element === current.element) {
return index
}
index++;
current = current.next;
}
return -1;
}
//检查列表是否为空
this.isEmpty = function() {
return length === 0
}
//返回列表的元素个数
this.size = function() {
return size
}
//
this.getHead = function() {
return head
}
//因为列表中使用了Node类，就需要用重写继承于JavaScript对象默认的toString方法，让它只输出元素的值
this.toString = function() {
let current = head,
string = '';
while (current) {
string += current.element + (current.next ? 'n' : ' ');
current = current.next;
}
return string;
}
this.print = function() {}
}
let list = new LinkedList();
list.append(15)
</script>
</body>
</html>
双向链表
在双向链表中，链接时双向的，一个指下一项，一个指向上一项。
/**
* 双向链表
*/
function DoulyLinkedList() {
let Node = function(element) {
this.element = element;
this.next = null;
this.prev = null;
}
let length = 0;
let head = null;
let tail = null;
this.insert = function(position, element) {
if (position >= 0 && position <= length) {
let node = new Node(element),
current = head,
previous,
index = 0;
if (previous === 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
}
}
this.removeAt = function(position) {
if (position > -1 && position < length) {
let 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;
}
}
}