一、基础
1、定义
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
2、相关概念
一个完整的链表需要由以下几个部分组成：
- 头指针：一个普通的指针，它的特点是永远指向链表第一个结点的位置。
- 结点：节点包含三类：头结点、首元节点和其它节点。
(1)头结点(非必须)：一个不存任何数据的空节点，通常作为链表的第一个节点。
(2)首元结点：链表中第一个存有数据的节点称为首元结点。
(3)其它结点：链表中的其它结点。
3、结点包含内容
链表中每个节点包含两个部分：
- 数据域：存储数据元素本身。
- 指针域：指向直接后续元素的指针。
二、链表分类及相关操作
链表存在很多种类，下面重点讲述单向链表、双向链表的结点结构，以及其对应的CURD(添加、更改、查找、删除)。
1、 单向链表
对于单链表的相应编程，我们均按照默认头指针指向首元结点这样的结构进行代码实现。
（1）结点结构
结点作为链表的重要组成部分，其结构可用如下代码表示：
function ListNode(val, next) {
this.val = val;
this.next = next === undefined ? null : next;
}- 1.
- 2.
- 3.
- 4.
扩展：如何根据一个数组创建链表。
function createLinkedList(arr) {
const head = new ListNode(arr[0]);
let current = head;
for (let i = 1; i < arr.length; i++) {
const node = new ListNode(arr[i]);
current.next = node;
current = current.next;
}
return head;
}- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
（2）遍历(查找)
在链表中查找指定数据元素，其思路是从表头依次遍历表中节点，用被查找元素与各结点中存储的数据元素进行对比，直到对比成功或遍历至链表最末端的null。
// 查找
function selectVal(head, val) {
let current = head;
// 判断是否为null
while (current) {
// 判断是否对比成功
if (current.val === val) {
return current;
}
current = current.next;
}
return null;
}- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
（3）添加
向链表中添加元素，根据添加位置不同，可分为3中情况:
- 插入到链表的头部。
- 插入到链表中间的某个位置。
- 插入到链表的最末端，作为链表中最后一个数据元素。
插入思想
- 将新结点的next指针指向插入位置后的结点。
- 将插入位置前结点的next指针指向插入结点。
function insertVal(head, val, add) {
const newNode = new ListNode(add);
// 查找插入节点
const currentNode = selectVal(head, val);
if (!currentNode) {
return null;
}
// 1. 将新结点的next指针指向插入位置后的节点
newNode.next = currentNode.next;
// 2. 将插入位置前节点的next指针指向插入节点
currentNode.next = newNode;
return head;
}- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
（4）删除
删除的元素的时候要注意链表的结构，注意有没有空值的头结点，有头结点的时候删除的时候就不需要判断删除的是不是第一个值，否则需要进行判断。
function delVal(head, val) {
// 当一个结点也不存在时，直接返回空
if (!head) {
return null;
}
// 如果删除的是第一个节点，直接将head指向第二个节点
if (head.val === val) {
head = head.next;
return head;
}
// 如果删除的不是第一个节点
let current = head;
// 找到待删除元素的前一个值
while (current.next && current.next.val !== val) {
current = current.next;
}
if (current.next) {
// 将删除结点的前一个结点的next值直接指向删除结点的下一个节点
current.next = current.next.next;
}
return head;
}- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
- 19.
- 20.
- 21.
- 22.
（5）更改
更新链表中的元素，只需要通过遍历找到存储此元素的节点，对节点中的数据域做更改操作即可。
function updateVal(head, val, newVal) {
let current = head;
while (current) {
if (current.val === val) {
current.val = newVal;
return head;
}
current = current.next;
}
return null;
}- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
2、 双向链表
单链表只有一个方向，从头结点到尾结点，双向链表指各个节点之间的逻辑关系是双向的，其结点结构和链表结构如下所示：
结点结构：
链表结构：
（1）结点结构
双向链表的节点结构相比于单向链表，多了一个prev属性，如下所示：
function ListNode(val, prev, next) {
this.val = val;
this.prev = prev === undefined ? null : prev;
this.next = next === undefined ? null : next;
}- 1.
- 2.
- 3.
- 4.
- 5.
（2）遍历(查找)
双向链表的查找和单向链表的查找类似，都是遍历链表。
function selectVal(head, val) {
let current = head;
while (current) {
if (current.val === val) {
return current;
}
current = current.next;
}
return null;
}- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
（3）添加
在某个节点后插入结点，其思想是：
- 找到该插入结点。
- 将新结点的next指针指向插入位置后的结点。
- 将新结点的prev指针指向插入位置的结点。
- 将插入节点的next指针指向新结点。
/**
* 插入(在某个节点后插入)
*/
function insertVal(head, val, add) {
const newNode = new ListNode(add);
// 查找插入节点
const currentNode = selectVal(head, val);
if (!currentNode) {
return null;
}
// 1. 将新结点的next指针指向插入位置后的结点
newNode.next = currentNode.next;
// 2. 将新结点的prev指针指向插入位置的结点
newNode.prev = currentNode;
// 3. 将插入节点的next指针指向新结点
currentNode.next = newNode;
return head;
}- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
（4）删除
双链表删除结点时，只需要遍历链表找到要删除的链表，然后将该链表从表中摘除即可。
(注：针对头指针直线的结点需要做特殊处理，否则head永远指向的是原始的第一个节点)。
/**
* 删除
*
* 双链表删除结点时，只需要遍历链表找到要删除的链表，然后将该链表从表中摘除即可
*/
function delVal(head, val) {
let current = head;
while (current) {
if (current.val === val) {
if (current.next) {
current.next.prev = current.prev;
}
if (current.prev) {
current.prev.next = current.next;
} else {
// 针对头指针直线的结点需要做特殊处理，否则head永远指向的是原始的第一个节点
head = current.next;
}
return head;
}
current = current.next;
}
return null;
}- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
- 19.
- 20.
- 21.
- 22.
- 23.
- 24.
（5）更改
更新链表中的元素，只需要通过遍历找到存储此元素的节点，对节点中的数据域做更改操作即可。
/**
* 更新
*
* 更新链表中的元素，只需要通过遍历找到存储此元素的节点，对节点中的数据域做更改操作即可
*/
function updateVal(head, val, newVal) {
let current = head;
while (current) {
if (current.val === val) {
current.val = newVal;
return head;
}
current = current.next;
}
return null;
}- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.