链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个 元素由一个存储元素本身的节点和一个指向下一个元素的引用(也称指针或链接)组成。下图展示了链表的结构:
相对于传统的数组，链表的一个好处在于，添加或移除元素的时候不需要移动其他元素。然而，链表需要使用指针，因此实现链表时需要额外注意。 数组的另一个细节是可以直接访问任何位置的任何元素，而要想访问链表中间的一个元素，需要从起点(表头)开始迭代列表直到找到所需的元素。
// 链表节点
class Node {
constructor(element) {
this.element = element;
this.next = null;
}
}
// 链表
class LinkedList {
constructor() {
this.head = null;
this.length = 0; // length 同数组 length 与下标关系
}
// 追加元素
append(element) {
let node = new Node(element);
let current = null; // 指针？
if (this.head === null) {
this.head = node;
} else {
current = this.head;
while (current.next) {
current = current.next;
}
current.next = node;
}
this.length++;
}
// 任意位置插入元素
insert (position, element) {
if (position >= 0 && position <= this.length) {
let node = new Node(element);
let current = this.head;
let previous = null;
let index = 0;
if (position === 0) {
this.head = node;
} else {
while (index++ < position) {
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
}
this.length++;
return true
}
return false
}
// 移除指定位置元素
removeAt(position) {
if (position > -1 && position < length) {
let current = this.head;
let previous = null;
let index = 0;
if (position === 0) {
this.head = current.next;
} else {
while(index++ < position) {
previous = current;
current = current.next;
}
previous.next = current.next;
}
this.length--;
return current.element;
}
return null
}
// 寻找元素下标
findIndex(element) {
let current = this.head;
let index = -1;
while (current) {
if (element === current.element) {
return index + 1;
}
index++;
current = current.next;
}
return -1;
}
// 删除指定文档
remove(element) {
let index = this.findIndex(element);
return removeAt(index);
}
isEmpty() {
return !this.length;
}
size() {
return this.length;
}
// 输出字符串
toString() {
let current = this.head;
let string = ‘‘;
while (current) {
string += ` ${current.element}`;
current = current.next;
}
return string;
}
}
var ll = new LinkedList();
console.log(ll);
ll.append(2);
ll.append(6);
ll.append(24);
ll.append(152);
ll.insert(3, 18);
console.log(ll);
console.log(ll.findIndex(24));
class Node {
constructor(element) {
this.element = element;
this.prev = null;
this.next = null;
}
}
// 双向链表
class DoubleLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
// 任意位置插入元素
insert(position, element) {
if (position >= 0 && position <= ehis.length) {
let node = new Node(element);
let current = this.head;
let previous = null;
this.index = 0;
// 首位
if (position === 0) {
if (!head) {
this.head = node;
this.tail = node;
} else {
node.next = current;
this.head = node;
current.prev = node;
}
} else if (position === this.length) { // 末尾
current = this.tail;
current.next = node;
node.prev = current;
this.tail = node;
} else { // 中间
while(index++ < position) {
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
current.prev = node;
node.prev = previous;
}
this.length++;
return true;
}
return false;
}
// 移除指定位置元素
removeAt(position) {
if (position > -1 && position < this.length) {
let current = this.head;
let previous = null;
let index = 0;
// 首位
if (position === 0) {
this.head = this.head.next
this.head.prev = null
if (this.length === 1) {
this.tail = null
}
} else if (position === this.length - 1) { // 末位
this.tail = this.tail.prev
this.tail.next = null
} else { // 中位
while (index++ < position) {
previous = current
current = current.next
}
previous.next = current.next
current.next.prev = previous
}
this.length--;
return current.element;
} else {
return null;
}
}
// 其他方法
}
具体代码实现就不写了，下图是示意图
原文：https://www.cnblogs.com/cc-freiheit/p/10591992.html