链表数据结构
链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称指针或链接）组成。下
head -> value | next -> value | next -> value | next -> undefined
相对于传统的数组，链表的一个好处在于，添加或移除元素的时候不需要移动其他元素。然而，链表需要使用指针，因此实现链表时需要额外注意, 想要访问链表中的一个元素, 需要从起点(表头) 开始迭代链表直到找到所需的元素, 现实生活中: 比如火车类似链表的结构
- 创建链表
理解了什么是链表, 开始实现我们的数据结构
// 骨架
function defaultEquals(a, b) {
return a === b;
}
class LinkedList {
constructor(equalsFn = defaultEquals) {
this.count = 0; // 存储链表中的元素数量
// 数据结构是动态的，我们还需要将第一个元素的引用保存下来。我们可以用一个叫作head 的元素保存引用
this.head = undefined;
// 要比较链表中的元素是否相等，我们需要使用一个内部调用的函数，名为 equalsFn
this.equalsFn = equalsFn;
}
}
要表示链表中的第一个以及其他元素, 需要一个助手类, 叫做 Node
// Node类表示我们想要添加到链表中的项。
class Node {
constructor(element) {
// 该属性表示要加入链表元素的值；以及一个 next 属性，该属性是指向链表中下一个元素的指针
this.element = element;
this.next = undefined;
}
}
-
链表类的方法
-
push(element):向链表尾部添加一个新元素 -
insert(element, position):向链表特定位置插入一个新元素 -
getElementAt():返回链表中特定位置的元素, 如果链表中不存在这样的元素, 返回 undefined -
remove(element):从链表中移除一个元素 -
indexOf(element):返回元素在链表中的索引, 如果链表中没有该元素返回 -1. -
removeAt(position):从链表的特定位置移除一个元素 -
isEmpty():链表长度大于 0 返回 false -
size():返回链表的长度 -
toString():返回整个链表的字符串, 由于列表项使用了 Node 类，就需要重写继承自 JavaScript 对象默认的 toString 方法，让其只输出元素的值。
-
-
实现链表类的
push方法- 链表最后一个节点的下一个元素始终是 undefined 或 null
- 链表为空, 添加的是第一个元素, 链表不为空, 向其追加元素
空链表push
非空链表
class LinkedList {
constructor(equalsFn = defaultEquals) {
this.count = 0; // 存储链表中的元素数量
// 数据结构是动态的，我们还需要将第一个元素的引用保存下来。我们可以用一个叫作head 的元素保存引用
this.head = undefined;
// 要比较链表中的元素是否相等，我们需要使用一个内部调用的函数，名为 equalsFn
this.equalsFn = equalsFn;
}
/**
* 两种情景: 1. 链表为空, 添加的是第一个元素, 链表不为空, 向其追加元素
*/
push(element) {
// 创建 Node 项
const node = new Node(element);
let current;
// 1. 如果 head 为 undefined 或者 null , 链表添加第一个元素
if (this.head == null) {
this.head = node;
// 2. 不为空的链表尾部添加元素, 首先找到最后一个元素
} else {
current = this.head; // 只有第一个元素的引用
while (current.next != null) {
current = current.next;
}
// current.next 为 null 或者 undefined, 到达链表尾部了
current.next = node;
}
this.count++;
}
}
-
实现链表类的
removeAt方法- 要得到需要移除的元素的 index（位置），校验 index 有效性
-
移除第一个元素 & 移除第一个元素之外的元素
移除第一个
移除链表
class LinkedList {
constructor(equalsFn = defaultEquals) {
this.count = 0; // 存储链表中的元素数量
// 数据结构是动态的，我们还需要将第一个元素的引用保存下来。我们可以用一个叫作head 的元素保存引用
this.head = undefined;
// 要比较链表中的元素是否相等，我们需要使用一个内部调用的函数，名为 equalsFn
this.equalsFn = equalsFn;
}
removeAt(index) {
if (index >= 0 && index < this.count) {
// current 变量创建一个对链表中第一个元素的引用
let current = this.head;
// 移除第一项, 让 head 指向第二个元素
if (index === 0) {
this.head = current.next;
} else {
// 移除链表最后一个或者中间某一元素, 迭代链表的节点
let previous;
for (let i = 0; i < index; i++) {
previous = current;
// current 变量总是为对所循环列表的当前元素的引用
current = current.next;
}
// 要从链表中移除当前元素，要做的就是将 previous.next 和 current.next 链接起来
previous.next = current.next;
}
this.count--;
return current.element;
}
return undefined;
}
}
-
循环迭代链表直到目标位置
- remove 方法中, 迭代整个链表直到我们的目标索引 index, 很常用, 我们重构, 先实现
getElementAt方法
- remove 方法中, 迭代整个链表直到我们的目标索引 index, 很常用, 我们重构, 先实现
class LinkedList {
constructor(equalsFn = defaultEquals) {
this.count = 0; // 存储链表中的元素数量
// 数据结构是动态的，我们还需要将第一个元素的引用保存下来。我们可以用一个叫作head 的元素保存引用
this.head = undefined;
// 要比较链表中的元素是否相等，我们需要使用一个内部调用的函数，名为 equalsFn
this.equalsFn = equalsFn;
}
// 返回链表中特定位置的元素
getElementAt(index) {
// 要对传入的 index 参数进行合法性验证
if (index >= 0 && index <= this.count) {
// 要初始化 node 变量，该变量会从链表的第一个元素 head 开始迭代整个链表
let current = this.head;
for (let i = 0; i < index && current != null; i++) {
current = current.next;
}
return current;
}
return undefined;
}
}
- 在任意位置插入元素
insert-
在第一个位置添加 & 其它位置添加
添加
添加其他位置
-
class LinkedList {
constructor(equalsFn = defaultEquals) {
this.count = 0; // 存储链表中的元素数量
// 数据结构是动态的，我们还需要将第一个元素的引用保存下来。我们可以用一个叫作head 的元素保存引用
this.head = undefined;
// 要比较链表中的元素是否相等，我们需要使用一个内部调用的函数，名为 equalsFn
this.equalsFn = equalsFn;
}
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 previours = this.getElementAt(index - 1);
const current = previours.next;
node.next = current;
previours.next = node;
}
this.count++;
return true;
}
return false;
}
}
- 实现其他所有方法
- indexOf size isEmpty 等方法, 以及完整方法
class LinkedList {
constructor(equalsFn = defaultEquals) {
this.count = 0; // 存储链表中的元素数量
// 数据结构是动态的，我们还需要将第一个元素的引用保存下来。我们可以用一个叫作head 的元素保存引用
this.head = undefined;
// 要比较链表中的元素是否相等，我们需要使用一个内部调用的函数，名为 equalsFn
this.equalsFn = equalsFn;
}
/**
* 两种情景: 1. 链表为空, 添加的是第一个元素, 链表不为空, 向其追加元素
*/
push(element) {
// 创建 Node 项
const node = new Node(element);
let current;
// 1. 如果 head 为 undefined 或者 null , 链表添加第一个元素
if (this.head == null) {
this.head = node;
// 2. 不为空的链表尾部添加元素, 首先找到最后一个元素
} else {
current = this.head; // 只有第一个元素的引用
while (current.next != null) {
current = current.next;
}
// current.next 为 null 或者 undefined, 到达链表尾部了
current.next = node;
}
this.count++;
}
removeAt(index) {
if (index >= 0 && index < this.count) {
// current 变量创建一个对链表中第一个元素的引用
let current = this.head;
// 移除第一项, 让 head 指向第二个元素
if (index === 0) {
this.head = current.next;
} else {
const previous = this.getElementAt(index - 1);
current = previous.next;
// 要从链表中移除当前元素，要做的就是将 previous.next 和 current.next 链接起来
previous.next = current.next;
}
this.count--;
return current.element;
}
return undefined;
}
remove(element) {
const index = this.indexOf(element);
return this.removeAt(index);
}
getElementAt(index) {
// 要对传入的 index 参数进行合法性验证
if (index >= 0 && index <= this.count) {
// 要初始化 node 变量，该变量会从链表的第一个元素 head 开始迭代整个链表
let current = this.head;
for (let i = 0; i < index && current != null; i++) {
current = current.next;
}
return current;
}
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 previours = this.getElementAt(index - 1);
const current = previours.next;
node.next = current;
previours.next = node;
}
this.count++;
return true;
}
return false;
}
// 接受元素的值, 返回元素的位置
indexOf(element) {
let current = this.head;
for (let i = 0; i < this.count && current != null; i++) {
// current 节点的元素和目标元素是否相等
if (this.equalsFn(element, current.element)) {
return i;
}
current = current.next; // {5}
}
return -1;
}
size() {
return this.count;
}
isEmpty() {
return this.size() === 0;
}
getHead() {
return this.head;
}
toString() {
// 如果链表为空（head 为 null 或 undefined），我们就返回一个空字符串
if (this.head == null) {
return "";
}
// 链表第一个元素的值来初始化方法最后返回的字符串
let objString = `${this.head.element}`;
let current = this.head.next; // {3}
for (let i = 1; i < this.size() && current != null; i++) {
objString = `${objString},${current.element}`;
current = current.next;
}
return objString;
}
}
双向链表
在链表中，一个节点只有链向下一个节点的链接；而在双向链表中，链接是双向的：一个链向下一个元素，另一个链向前一个元素
双向链表
- 先实现
DoublyLinkedList类所需的表懂开始
class DoubleNode extends Node {
constructor(element, next, prev) {
super(element, next);
this.prev = prev;
}
}
// 是一种特殊的 LinkedList 类
class DoublyLinkedList extends LinkedList {
constructor(equalsFn = defaultEquals) {
super(equalsFn);
// 保存对链表最后一个元素的引用
this.tail = undefined;
}
}
双向链表提供了两种迭代的方法：从头到尾，或者从尾到头, 我们也可以访问一个特定节点的下一个或前一个元素。为了实现这种行为，还需要追踪每个节点的前一个节点, 添加
this.prev
- 在任意位置插入新元素
链表只要控制一个 next 指针，而双向链表则要同时控制 next 和 prev（previous，前一个）这两个指针, 重写 insert 方法
class DoublyLinkedList extends LinkedList {
constructor(equalsFn = defaultEquals) {
super(equalsFn);
// 保存对链表最后一个元素的引用
this.tail = undefined;
}
insert(element, index) {
if (index >= 0 && index <= this.count) {
const node = new DoubleNode(element);
let current = this.head;
// 在双向链表的第一个位置（起点）插入一个新元素
if (index === 0) {
// 如果双向链表为空, 把 head 和 tail 都指向这个新节点
if (this.head == null) {
this.head = node;
this.tail = node;
} else {
// 如果不为空，current 变量将是对双向链表中第一个元素的引用
node.next = this.head;
current.prev = node;
this.head = node;
}
// 双向链表最后添加一个新元素
} else if (index === this.count) {
// current 变量将引用最后一个元素
current = this.tail;
// 然后开始建立链接，current.next 指针（指向 undefined）将指向 node
current.next = node;
// node.prev 将引用 current
node.prev = current;
// 将由指向 current 变为指向 node
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;
}
}
链表插入第一个元素
链表插入最后的元素
链表中间插入元素
- 任意位置移除元素
双向链表中移除元素跟链表非常类似。唯一的区别就是，还需要设置前一个位置的指针
class DoublyLinkedList extends LinkedList {
constructor(equalsFn = defaultEquals) {
super(equalsFn);
// 保存对链表最后一个元素的引用
this.tail = undefined;
}
insert(element, index) {
if (index >= 0 && index <= this.count) {
const node = new DoubleNode(element);
let current = this.head;
// 在双向链表的第一个位置（起点）插入一个新元素
if (index === 0) {
// 如果双向链表为空, 把 head 和 tail 都指向这个新节点
if (this.head == null) {
this.head = node;
this.tail = node;
} else {
// 如果不为空，current 变量将是对双向链表中第一个元素的引用
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) {
// current 变量是对双向链表中第一个元素的引用
let current = this.head;
// 移除第一个元素, current 就是我们希望移除的
if (index === 0) {
// 是改变 head 的引用，将其从 current 改为下一个元素
this.head = current.next;
// 如果只有一项, 更新 tail
if (this.count === 1) {
this.tail = undefined;
} else {
// 把 head.prev 的引用改为 undefined, 因为 head 也指向双向链表中新的第一个元素
this.head.prev = undefined;
}
// 最后一个位置移除元素
} else if (index === this.count - 1) {
// 已经有了对最后一个元素的引用（tail）
current = this.tail;
// 把 tail 的引用更新为双向链表中倒数第二个元素
this.tail = current.prev;
// 既然 tail 指向了倒数第二个元素，我们就只需要把 next 指针更新为 undefined;
this.tail.next = undefined;
// 从双向链表中间移除一个元素
} else {
// current 变量所引用的就是要移除的元素
current = this.getElementAt(index);
// 过更新 previous.next 和 current.next.prev 的引用
const previous = current.prev;
previous.next = current.next;
current.next.prev = previous;
}
this.count++;
return current.element;
}
return undefined;
}
}
移除第一个元素
移除最后一个元素
移除中间的元素
循环链表
循环链表可以像链表一样只有单向引用，也可以像双向链表一样有双向引用, 循环链表和链表之间唯一的区别在于，最后一个元素指向下一个元素的指针（tail.next）不是引用 undefined，而是指向第一个元素(head)
循环链表
// 扩展 LinkedList
class CircularLinkedList extends LinkedList {
constructor(equalsFn = defaultEquals) {
super(equalsFn);
}
}
- 在任意位置插入新元素
向循环链表中插入元素的逻辑和向普通链表中插入元素的逻辑是一样的。不同之处在于我们需要将循环链表尾部节点的 next 引用指向头部节点
// 扩展 LinkedList
class CircularLinkedList extends LinkedList {
constructor(equalsFn = defaultEquals) {
super(equalsFn);
}
insert(element, index) {
if (index >= 0 && index < this.count) {
const 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 指向现在的 head 引用的节点（current 变量）
node.next = current;
current = this.getElementAt(this.size());
// 将头部元素更新为新元素
this.head = node;
// 再将最后一个节点（current）指向新的头部节点
current.next = this.head;
}
} else {
const previous = this.getElementAt(index - 1);
node.next = previous.next;
previous.next = node;
}
this.count++;
return true;
}
return false;
}
}
循环列表第一种
中间插入
- 在任意位置移除元素
从循环链表中移除元素，我们只需要考虑第二种情况，也就是修改循环链表的 head 元素
class CircularLinkedList extends LinkedList {
constructor(equalsFn = defaultEquals) {
super(equalsFn);
}
removeAt(index) {
if (index >= 0 && index <= this.count) {
let current = this.head;
if (index === 0) {
// 从只有一个元素的循环链表中移除一个元素
if (this.size() === 1) {
this.head = undefined;
// 是从一个非空循环链表中移除第一个元素
} else {
// 保存现在的 head 元素的引用，它将从循环链表中移除
const removed = this.head;
// 需要获得循环链表最后一个元素的引用
current = this.getElementAt(this.size());
// 更新 head element，将其指向第二个元素
this.head = this.head.next;
// 将最后一个 element（current.next）指向新的 head
current.next = this.head;
// 更新 current 变量的引用
current = removed;
}
} else {
// 不需要修改循环链表最后一个元素
const previous = this.getElementAt(index - 1);
current = previous.next;
previous.next = current.next;
}
this.count--;
return current.element; // {6}
}
return undefined;
}
}
移除链表中的元素
有序链表
有序链表是指保持元素有序的链表结构。除了使用排序算法之外，我们还可以将元素插入到正确的位置来保证链表的有序性。
const Compare = {
LESS_THAN: -1,
BIGGER_THAN: 1,
};
function defaultCompare(a, b) {
if (a === b) {
// {1}
return 0;
}
return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN; // {2}
}
class SortedLinkedList extends LinkedList {
// 需要一个用来比较元素的函数
constructor(equalsFn = defaultEquals, compareFn = defaultCompare) {
super(equalsFn);
this.compareFn = compareFn;
}
// 我们不想允许在任何位置插入元素，我们要给 index 参数设置一个默认值
insert(element, index = 0) {
// 如果有序链表为空，我们可以直接调用 LinkedList 的 insert 方法并传入 0 作为 index
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;
}
}
链表还需要多多练习, 增加理解
网友评论