链表主要分为3类：单向链表、双向链表和循环链表
链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。单向链表只能从从一个方向由一个节点指向节点的下一个节点。
链表中的元素在内存中不必是连续的空间
相对于数组来说，链表的插入和删除操作速度更快，因为其只需要修改 操作节点 的前后节点的指针即可。不必像数组一样逐个去遍历。但在取下标值的数据时很慢，由于其要根据引用逐个进行查找。
双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。
双链表 既可以向前查询也可以向后查询。也就是可以从头到尾遍历，也可以从尾到头遍历
循环链表，顾名思义，就是链表首尾相连。
循环链表可以用来解决约瑟夫环问题。
function LinkedList() {
function Node(data) {
this.data = data;
this.next = null;
}
// 链表属性
this.head = null;
this.length = 0;
// 末尾添加元素
LinkedList.prototype.append = function(data) {
var newNode = new Node(data);
if (this.length === 0) {
this.head = newNode;
} else {
var current = this.head; // 从head开始，逐个查询其节点数据是否存在
while (current.next) {
current = current.next;
}
current.next = newNode;
}
this.length += 1;
};
// 转换为字符串
LinkedList.prototype.toString = function() {
var tempString = "";
var current = this.head;
while (current && current.data) {
tempString += ` ${current.data} `;
current = current.next || null;
}
return tempString;
};
// 插入元素
LinkedList.prototype.insert = function(position, data) {
var newNode = new Node(data);
// 越界判断
if (position < 0 || position > this.length) {
throw new Error("Error: out of bounds");
return;
}
if (position === 0) {
newNode.next = this.head; // 将新数据项的指针，指向头部
this.head = newNode; // 指定新数据项为头部
} else {
var previous = null;
var current = this.head;
var index = 0;
while (index++ < position) {
previous = current;
current = current.next;
}
newNode.next = current;
previous.next = newNode;
this.length += 1;
}
};
// 获取指定index的数据
LinkedList.prototype.get = function(position) {
// 越界判断
if (position < 0 || position >= this.length) {
throw new Error("Error: out of bounds");
return;
}
let index = 0;
let current = this.head;
while (index++ < position) {
current = current.next;
}
return current.data;
};
// 获取指定数据的下标
LinkedList.prototype.indexOf = function(data) {
var current = this.head;
for (var i = 0; i < this.length; i++) {
if (current.data === data) {
return i;
}
current = current.next;
}
return -1;
};
// 修改指定位置元素
LinkedList.prototype.update = function(position, data) {
// 越界判断
if (position < 0 || position >= this.length) {
throw new Error("Error: out of bounds");
return;
}
let index = 0;
let current = this.head;
while (index++ < position) {
current = current.next;
}
current.data = data;
};
// 移除指定位置的元素
LinkedList.prototype.removeAt = function(position) {
// 越界判断
if (position < 0 || position >= this.length) {
throw new Error("Error: out of bounds");
return;
}
var current = this.head;
if (position === 0) {
this.head = current.next;
} else {
var previous = null;
var index = 0;
while (index++ < position) {
previous = current;
current = current.next;
}
previous.next = current.next || null;
}
return current.data;
};
// 移除指定元素
LinkedList.prototype.remove = function(data) {
var position = this.indexOf(data);
this.removeAt(position);
};
LinkedList.prototype.isEmpty = function() {
return !!this.length;
};
LinkedList.prototype.size = function() {
return this.length;
};
}
var linkedList = new LinkedList();
linkedList.append("a");
linkedList.append("b");
linkedList.append("c");
linkedList.insert(1, "a++");
linkedList.update(0, "aaa");
// linkedList.removeAt(3)
linkedList.remove("b");
// linkedList.removeAt(linkedList.length -1)
// console.log(linkedList.indexOf('kerwin'))
// console.log(linkedList.get(1));
console.log(linkedList.toString());function DoublyLinkedList() {
// 属性
this.head = null;
this.tail = null;
this.length = 0;
function Node(data) {
this.data = data;
this.next = null;
this.prev = null;
}
DoublyLinkedList.prototype.append = function(data) {
var newNode = new Node(data);
if (!this.length) {
this.head = newNode;
this.tail = newNode;
this.length += 1;
return;
}
this.tail.next = newNode;
newNode.prev = this.tail;
this.tail = newNode;
this.length += 1;
};
DoublyLinkedList.prototype.backwardString = function() {
var current = this.head;
var resultStr = "";
while (current) {
resultStr += current.data + " ";
current = current.next;
}
return resultStr;
};
DoublyLinkedList.prototype.forwardString = function() {
var current = this.tail;
var resultStr = "";
while (current) {
resultStr += current.data + " ";
current = current.prev;
}
return resultStr;
};
DoublyLinkedList.prototype.insert = function(position, data) {
// 越界判断
if (position < 0 || position > this.length) return;
var newNode = new Node(data);
if (!this.length) {
this.head = newNode;
this.tail = newNode;
this.length += 1;
return;
}
if (position === 0) {
this.head.prev = newNode; // 将当前head移至第二个位置，并将prev指针指向新心结
newNode.next = this.head; // 绑定新节点的next指针
this.head = newNode; // 生成新的头节点
} else if (position === this.length) {
this.tail.next = newNode; // 末尾节点next指针指向新节点
newNode.prev = this.tail; // 新节点的prev指针指向上一个节点
this.tail = newNode; // 生成新的尾节点
} else {
var current = this.head;
for (var i = 0; i < position; i++) {
current = current.next;
}
newNode.next = current; // 新节点的next指针
newNode.prev = current.prev; // 新节点的prev指针
current.prev.next = newNode; // 修改当前节点的上一个节点next指针
current.prev = newNode; // 修改当前节点的prev指针
}
this.length += 1;
};
DoublyLinkedList.prototype.get = function(position) {
let current = this._getCurrent(position);
return current.data;
};
DoublyLinkedList.prototype.indexOf = function(data) {
var current = this.head;
for (let i = 0; i < this.length; i++) {
if (current.data === data) {
return i;
}
current = current.next;
}
return -1;
};
DoublyLinkedList.prototype._getCurrent = function(position) {
if (position < 0 || position >= this.length) return null;
// 判断从头 or 从尾开始遍历
if (position < this.length / 2) {
current = this.head;
for (let i = 0; i < position; i++) {
current = current.next;
}
} else {
current = this.tail;
for (let i = this.length - 1; i > position; i--) {
current = current.prev;
}
}
return current;
};
DoublyLinkedList.prototype.update = function(position, data) {
let current = this._getCurrent(position);
current.data = data;
};
DoublyLinkedList.prototype.removeAt = function(position) {
if (position < 0 || position >= this.length) return;
var current = this.head;
if (this.length === 1) {
this.head = null;
this.tail = null;
return;
}
if (position === 0) {
var temp = this.head.next;
temp.prev = null;
this.head = temp;
} else if (position === this.length - 1) {
current = this.tail;
var temp = this.tail.prev;
temp.next = null;
this.tail = temp;
} else {
current = this._getCurrent(position);
var prev = current.prev;
var next = current.next;
prev.next = next;
next.prev = prev;
}
this.length -= 1;
return current.data;
};
DoublyLinkedList.prototype.remove = function(data) {
var index = this.indexOf(data);
return this.removeAt(index);
};
DoublyLinkedList.prototype.isEmpty = function() {
return !!this.length;
};
DoublyLinkedList.prototype.size = function() {
return this.length;
};
DoublyLinkedList.prototype.getHead = function() {
return this.head.data;
};
DoublyLinkedList.prototype.getTail = function() {
return this.tail.data;
};
}
var list = new DoublyLinkedList();
list.append("kerwin");
list.append("bob");
list.insert(0, 0);
list.insert(1, 1);
list.insert(3, 3);
// console.log(list.removeAt(4));
// console.log(list.remove("kerwin"));
console.log(list.backwardString());
console.log(list.get(2));
console.log(list.indexOf("kerwin"));
list.update(1, "ddd");
console.log(list.backwardString());