链表和数组一样，都是用于储存一系列的元素（数据）的数据结构，但是链表和数组的实现机制完全不同，下面我们就来学习一下另外一种非常常见的用于储存数据的线性结构：链表，
要储存多个元素，数组（列表）可能是做常用的数据结构，我们之前说过，几乎每一种编程语言都会默认实现数组结构，尽管数组的操作很灵活通过下标访问元素效率很高，但是数组也有很多缺点比如数组的创建通常是需要申请一段连续的内存空间（一整块内存）并且大小是固定的（大多数编程语言都是固定的）所以如果当前数组不能满足容量需求的时候，则需要进行扩容操作（通常操作是审申请一个更大的数组，比如2倍，然后将原数组中的元素复制过去）而且数组开头或者中间位置插入数据的成本很高，需要进行大量元素的位移，尽管我们已经学习过js的array类方法可以帮我们做这些事，但是背后的原理依然是这样的，
知道数组的优缺点之后那接下来就该轮到我们链表出场了，要储存一组元素另一个选择就是链表，但是不同于数组，链表中的元素在内存中不必是连续的空间，链表的每个元素由元素本身和一个指向下一个元素的引用（有些语言称为指针或连接）组成，可能你现在还不太理解，没关系下面我们会有相关的实现
相对于数组，链表有一些优点，内存空间不是必须连续的，这样就可以充分利用计算机的内存，实现灵活的内存动态管理，链表不必在创建的时候就确定大小，并且大小可以无限延申下去，链表在插入和删除数据的时候，时间复杂度可以达到O(1)，相对于数组效率要高很多。但是链表不支持通过下标去访问元素，只能通过链表中每个元素中的指针来遍历访问，这一点倒是不如数组，链表中访问任何一个位置的元素时，都需要从头开始访问，（无法跳过第一个元素访问任何一个元素）
什么是链表呢，其实上面我们已经简单的提过了链表的结构，这里我们更加详细的进行分析，链表类似于火车：有一个火车头，火车头会链接一个节点，节点上有乘客（类似于数据），并且这个节点会连接下一个节点，以此类推
链表结构的实现
js中原生没有提供链表结构，下面我们就来自己实现一下链表结构，内部使用对象最为载体
// 简单的链表结构实现
class LinkedList {
// 构造方法
constructor() {
// 链表头部指针
this.head = null;
// 创建新节点(内部类,仅供内部方法使用)
this._createNode = class {
constructor(data) {
this.data = data;
this.next = null;
}
};
}
// get 内部使用遍历来获取链表长度，并返回
get length() {
let current = this.head;
// 如果header为null则退出返回0
if (!current) return 0;
let index = 0;
while (current.next) {
current = current.next;
index++;
}
return index;
}
// 向链表尾部添加,接收一个参数：被添加的元素
append(element) {
// 创建新节点
let newNode = new this._createNode(element);
if (!this.head) {
// 如果添加是是第一个节点,直接将 head 指针指向此节点
this.head = newNode;
} else {
// 如果添加的不是第一个节点
let current = this.head;
// 依次循环直到,到达链表末尾
while (current.next) {
// 首次进入循环的时候,next方法是第一个元素的next (因为head指向的就是第一个元素)
// 然后将 current 重新赋值,指向下一个的 next,然后重新进入循环,直到 next为 null
current = current.next;
}
// 退出循环后
// 将最后一个元素的next 指向新节点
current.next = newNode;
}
}
// 在链表指定位置添加元素,，接受两个参数，第一个是位置，第二个是要添加的元素
insert(position, element) {
// 越界判断
if (position < 0 || position > this.length) return false;
// 创建元素
let newNode = new this._createNode(element);
// 如果是0则直接向头部添加
if (position === 0) {
newNode.next = this.head;
this.head = newNode;
} else if (position === this.length) {
// 如果要插入的位置正好是 链表的末尾就直接调用底部插入方法
return this.append(element);
} else {
// 获取头部
let current = this.head;
// 遍历到指定的位置
for (let i = 0; i <= position - 2; i++) {
current = current.next;
}
// 新节点的 next 指向现在的下一个 元素
newNode.next = current.next;
// 中断原先结构,替换为新节点
current.next = newNode;
}
}
// 获取对应位置的元素
get(position) {
// 越界判断
if (position < 0 || position > this.length) return false;
// 获取头部
let current = this.head;
// 遍历到指定位置
for (let i = 0; i <= position - 1; i++) {
current = current.next;
}
return current;
}
// 返回元素在链表中的位置,如果没有返回 -1
// 接受一个参数
indexOf(element) {
// 获取头部
let current = this.head;
// 预先设定 下标值
let index = 0;
// 进入循环
while (current.next) {
// 循环中判断
if (element === current.data) {
// 如果是则直接return 退出函数
return index;
}
// 如果不是则重新赋值
current = current.next;
// 下标+1
index += 1;
}
// 没有找到返回 -1
return -1;
}
// 更新某个位置的元素
update(position, element) {
// 越界判断
if (position < 0 || position > this.length) return false;
// 获取头部
let current = this.head;
// 遍历到指定位置
for (let i = 0; i <= position - 1; i++) {
current = current.next;
}
// 直接更新
current.data = element;
}
// 从链表的特定位置移除一项
removeAt(position) {
// 越界判断
if (position < 0 || position > this.length) return false;
// 获取头部
let current = this.head;
// 如果是0
if (position === 0) {
// 直接移除第一项
this.head = this.head.next;
} else {
// 遍历到指定位置
for (let i = 0; i <= position - 2; i++) {
current = current.next;
}
// 移除
current.next = current.next.next;
}
}
// 从链表中移除指定项
remove(element) {
return this.removeAt(this.indexOf(element));
}
// 链表是否为空
isEmpty() {
// 直接判断header
if (this.head) {
return false;
} else {
return true;
}
}
// 查看链表元素个数
size() {
// 直接返回 链表长度
return this.length;
}
// 输出字符串
toString() {
// 获取头部
let current = this.head;
// 预定义字符串
let listString = "";
// 循环 链表
while (current) {
listString += " => " + current.data;
current = current.next;
}
// 返回字符串
return listString.slice(4);
}
}
let cs = new LinkedList();
cs.append("小红");
cs.append("小绿");
cs.append("小黑");
// console.log(cs.length)
// console.log(cs.toString())
// cs.insert(1,"成功")
// console.log(cs.toString())
// cs.update(4,"成功更新")
console.log(cs.toString());
// console.log(cs.get(4))
cs.remove("小绿");
console.log(cs.toString());
通过上面的代码我们就简单的实现了一个链表结构
双向链表
之前我们实现的链表其实可以称之为单向链表，另外还有一种常见的链表结构我们称之为双向链表，那什么是双向链表呢它和单向链表有什么不同呢？下面我们就来认识一下双向链表
首先回顾一下单项链表，单向链表只能从头遍历到尾，也就是链表相连的过程是单向的，实现原理是上一个链表节点中有一个指向下一个链表节点的引用，也就是每个节点只包含一个向下的引用，这个特性就会带来一个明显的问题，我们可以轻松的到达下一个节点，但是如果想要回到上一个节点是很困难的，而在实际开发中，经常会遇到需要回到上一个节点的情况，举个例子：假设一个文本编辑器使用链表结构来储存内容，每一行用一个String对象存储在链表中的一个节点上，当编辑器用户向下移动光标的时候链表直接操作到下一个节点即可，但是当用户将光标向上移动呢？这个时候就需要回到上一个节点，如果是单向链表我们可能需要重新从first开始，依次遍历到想要的节点上
下面是一张双向链表的结构示意图，通过此图我们就可以清楚的看到双向链表的结构以及它和单向链表的区别，之前单向链表中每个几点都只包含两个东西：数据和向下的指针，但是在双向链表的每个节点中多出了一样东西即向上的指针，也就是说我们可以通过此指针来访问上一个节点，这样就解决了上述问题，每个节点既可以访问下一个节点也可以访问上一个节点
总结双向链表的特点：双向链表可以使用一个head和一个tail分别指向头部和尾部的节点，每个节点都由三部分组成：前一个节点的指针(prev)，保存的元素(item)，后一个节点的指针(next)。双向链表的第一个节点的prev是null，双向链表的最后一个节点的next是null
那我们就来具体看一下双向链表具体如何实现
// 双向链表结构实现
class DoublyLinkedList {
// 构造方法
constructor() {
// 链表头部指针
this.head = null;
// 链表尾部指针
this.tail = null;
// 创建新节点(内部类,仅供内部方法使用)
this._createNode = class {
constructor(data) {
this.data = data;
// 指针默认为 null
this.prev = null;
this.next = null;
}
};
}
// get 内部使用遍历来获取链表长度，并返回
get length() {
let current = this.head;
if (!current) return 0;
let index = 0;
while (current.next) {
current = current.next;
index++;
}
return index;
}
// 向链表尾部添加,接收一个参数,被添加的元素
append(element) {
// 创建新节点
let newNode = new this._createNode(element);
// 如果当前链表为空
if (!this.head && !this.tail) {
this.head = newNode;
this.tail = newNode;
} else {
// 如果添加的不是第一个节点
let current = this.tail;
current.next = newNode;
newNode.prev = current;
this.tail = newNode;
}
}
// 向链表特定位置添加元素
insert(position, element) {
// 越界判断
if (position < 0 || position > this.length) return false;
// 创建元素
let newNode = new this._createNode(element);
// 0 代表头部
if (position === 0) {
newNode.next = this.head;
this.head = newNode;
} else if (position === this.length) {
// 如果要插入的位置正好是 链表的末尾就直接调用底部插入方法
return this.append(element)
} else {
// 中间插入
// 获取头部
let current = this.head;
for (let i = 0; i <= position - 2; i++) {
current = current.next;
}
// 新节点的 next 指向现在的下一个 元素
newNode.next = current.next;
// 中断原先结构,替换为新节点
current.next = newNode;
}
}
// 获取对应位置的元素
get(position) {
// 越界判断
if (position < 0 || position > this.length) return false;
let current = this.head;
for (let i = 0; i <= position - 1; i++) {
current = current.next;
}
return current;
}
// 返回元素在链表中的位置,如果没有返回 -1
indexOf(element) {
let current = this.head;
let index = 0;
while (current.next) {
if (element === current.data) {
return index;
}
current = current.next;
index += 1;
}
return -1;
}
// 更新某个位置的元素
update(position, element) {
if (position < 0 || position > this.length) return false;
let current = this.head;
for (let i = 0; i <= position - 1; i++) {
current = current.next;
}
current.data = element;
}
// 从链表的特定位置移除一项
removeAt(position) {
if (position < 0 || position > this.length) return false;
let current = this.head;
if (position === 0) {
this.head = this.head.next;
} else {
for (let i = 0; i <= position - 2; i++) {
current = current.next;
}
current.next = current.next.next;
}
}
// 从链表中移除指定项
remove(element) {
return this.removeAt(this.indexOf(element));
}
// 链表是否为空
isEmpty() {
if (this.head && this.tail) {
return false;
} else {
return true;
}
}
// 查看链表元素个数
size() {
return this.length;
}
// 输出字符串
toString() {
let current = this.head;
let listString = "";
while (current) {
listString += " => " + current.data;
current = current.next;
}
return listString.slice(4);
}
}
let cs = new DoublyLinkedList();
cs.append("第一")
cs.append("第二")
cs.append("第三")
cs.append("第四")
cs.append("第五")
cs.insert(4,"插入1")
console.log(cs.toString())
console.log(cs.head.data)
console.log(cs.tail.data)
