链表
链表数据结构
链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称指针或链接）组成。
function defaultEquals(a, b) {
return a === b;
}
class Node {
constructor(element) {
this.element = element;
this.next = undefined;
}
}
class LinkedList {
constructor(equalsFn = defaultEquals) {
this.count = 0;
this.head = undefined;
this.equalsFn = equalsFn;
}
// 向链尾部添加元素
push(element) {
const node = new Node(element);
let current;
if (this.head == null) {
this.head = node;
} else {
current = this.head;
while (current.next != null) {
current = current.next; // 获取最后一项
}
current.next = node;
}
this.count++;
}
// 从链表中移除元素
removeAt(index) {
if (index >= 0 && index < this.count) {
let current = this.head;
if (index == 0) {
this.head = current.next;
} else {
let previous;
for (let i = 0; i < index; i++) {
previous = current;
current = current.next;
}
previous.next = current.next;
}
this.count--;
return current.element;
}
return undefined;
}
// 循环迭代链表直到目标位置
getElementAt(index) {
if (index >= 0 && index <= this.count) {
let node = this.head;
for (let i = 0; i < index && node != null; i++) {
node = node.next;
}
return node;
}
return undefined;
}
// 在任意位置插入元素
insert(element, index) {
if (index >= 0 && index <= this.count) {
const node = new Node(element);
if (index === 0) {
const current = this.head;
node.next = current;
this.head = node;
} else {
const previous = this.getElementAt(index - 1);
const current = previous.next;
node.next = current;
previous.next = node;
}
this.count++;
return true;
}
return false;
}
// indexOf 返回一个元素的位置
indexOf(element) {
let current = this.head;
for (let i = 0; i < this.count && current != null; i++) {
if (this.equalsFn(element, current.element)) {
return i;
}
current = current.next;
}
return -1;
}
// 从链表中移除元素
remove(element) {
const index = this.indexOf(element);
return this.removeAt(index);
}
size() {
return this.count;
}
isEmpty() {
return this.size() === 0;
}
getHead() {
return this.head;
}
toString() {
if (this.head == null) {
return '';
}
let objString = `${this.head.element}`;
let current = this.head.next;
for (let i = 1; i < this.size() && current != null; i++) {
objString = `${objString},${current.element}`;
current = current.next;
}
return objString;
}
}
双向链表
在双向链表中，链接是双向的：一个链向下一个元素，另一个链向前一个元素
class DoublyNode extends Node {
constructor(element, next, prev) {
super(element, next);
this.prev = prev;
}
}
class DoublyLinkedList extends LinkedList {
constructor(equalsFn = defaultEquals) {
super(equalsFn);
this.tail = undefined;
}
// 向任意位置插入一个新元素
insert(element, index) {
if (index >= 0 && index <= this.count) {
const node = new DoublyNode(element);
let current = this.head;
if (index === 0) { // 开头
if (this.head == null) { // 新增的
this.head = node;
this.tail = node;
} else { // 替换头
node.next = this.head;
current.prev = node;
this.head = node;
}
} else if (index === this.count) { // 最后一项 新增的
current = this.tail;
current.next = node;
node.prev = current;
this.tail = node;
} else { // 中间
const previous = this.getElementAt(index - 1);
current = previous.next;
node.next = current;
previous.next = node;
current.prev = node;
node.prev = previous;
}
this.count++;
return true;
}
return false;
}
// 从任意位置移除元素
removeAt(index) {
if (index >= 0 && index <= this.count) {
let current = this.head;
if (index === 0) { // 第一个
this.head = current.next;
if (this.count === 1) {
this.tail = undefined;
} else {
this.head.prev = undefined;
}
} else if (index === this.count - 1) { // 最后一个
current = this.tail;
this.tail = current.prev;
this.tail.next = undefined;
} else { // 中间项
current = this.getElementAt(index);
const previous = current.prev;
previous.next = current.next;
current.next.prev = previous;
}
this.count--;
return current.element;
}
return undefined;
}
}
循环链表
循环链表可以像链表一样只有单向引用，也可以像双向链表一样有双向引用。循环链表和链表之间唯一的区别在于，最后一个元素指向下一个元素的指针（tail.next）不是引用undefined，而是指向第一个元素（head）
class CircularLinkedList extends LinkedList {
constructor(equalsFn = defaultEquals) {
super(equalsFn);
}
insert(element, index) {
if (index >= 0 && index <= this.count) {
cosnt node = new Node(element);
let current = this.head;
if (index === 0) {
if (this.head == null) {
this.head = node;
node.next = this.head;
} else {
node.next = current;
current = this.getElementAt(this.size());
this.head = node;
current.next = this.head;
}
} else {
const previous = this.getElementAt(index - 1);
node.next = previous.next;
previous.next = node;
}
this.count++;
return true;
}
return false;
}
removeAt(index) {
if (index >= 0 && index <= this.count) {
let current = this.head;
if (index === 0) {
if (this.size() === 1) {
this.head = undefined;
} else {
const removed = this.head;
current = this.getElementAt(this.size());
this.head = this.head.next;
current.next = this.head;
current = removed;
}
} else {
const previous = this.getElementAt(index - 1);
current = previous.next;
previous.next = current.next;
}
this.count--;
return current.element;
}
return undefined;
}
}
有序链表
有序链表是指保持元素有序的链表结构。除了使用排序算法之外，还可以将元素插入到正确的位置来保证链表的有序性。
const Compare = {
LESS_THAN: -1,
BIGGER_THAN: 1,
};
function defaultCompare(a, b) {
if (a === b) return 0;
return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}
class SortedLinkedList extends LinkedList {
constructor(equalsFn = defaultEquals, compareFn = defaultCompare) {
super(equalsFn);
this.compareFn = compareFn;
}
insert(element, index = 0) {
if (this.isEmpty()) {
return super.insert(element, 0);
}
const pos = this.getIndexNextSortedElement(element);
return super.insert(element, pos);
}
getIndexNextSortedElement(element) {
let current = this.head;
let i = 0;
for (; i < this.size() && current; i++) {
const comp = this.compareFn(element, current.element);
if (comp === Compare.LESS_THAN) {
return i;
}
current = current.next;
}
return i;
}
}
StackLinkedList类
可以使用 LinkedList 类及其变种作为内部的数据结构来创建其他数据结构，例如栈、 队列和双向队列
class StackLinkedList {
constructor() {
this.items = new DoublyLinkedList();
}
push(item) {
this.items.push(item);
}
pop() {
if (this.isEmpty()) {
return undefined;
}
return this.items.removeAt(this.size() - 1);
}
peek() {
if (this.isEmpty()) {
return undefined;
}
return this.items.getElementAt(this.size() - 1).element;
}
isEmpty() {
return this.items.isEmpty();
}
size() {
return this.items.size();
}
clear() {
this.items.clear();
}
toString() {
return this.items.toString();
}
}
