链表
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
单链表的概念：
单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(也称指针或链接)组成。下图展示了一个单链表的结构图：
单链表的特点：
每个元素除了由元素本身的节点还有指向下一个元素的指针构成从链表中添加或者删除元素不需要移动其他的元素
访问链表中间的一个元素，需要从表头开始迭代列表直到找到所需的元素
生活中单链表的案例：
生活中的单链表很典型也很常见。例如寻宝游戏，你有一条线索，这条线索是指向寻找下一条线索的地点的指针，你可以顺着这条链接去下一个地方，得到另一条指向下一处的线索，如果想得到列表中间的线索的唯一办法就是从起点(第一条线索)顺着列表寻找。另一个案例就是火车，还有其他的案例这里就不一一列举了。
单向链表的实现
- 初始化链表/节点
- 头部插入节点
- 搜索/遍历节点
- 删除节点
初始化链表中的节点
class LinkedListNode {
constructor(value, next = null) {
this.value = value;
this.next = next; // 初始化为null
}
}初始化单向链表
class LinkedList {
constructor() {
// 初始空指针
this.head = null;
}
}头部追加节点(append)
append(value) {
// 新建节点
const newNode = new LinkedListNode(value, this.head);
// 将值赋予head 为了下次新建
this.head = newNode;
}删除节点
delete(value) {
// 如果不存在节点 return null
if (!this.head) {
return null;
}
// 如果删除的是第一个节点
let deletedNode = null;
// 如果删除的第一个元素
while (this.head && this.head.value === value) {
deletedNode = this.head;
this.head = this.head.next;
}
// 非第一个节点,遍历查找
let currentNode = this.head;
if (currentNode !== null) {
while (currentNode.next) {
if (currentNode.next.value === value) {
deletedNode = currentNode.next;
currentNode.next = currentNode.next.next;
} else {
currentNode = currentNode.next;
}
}
}
return deletedNode;
}本文内容仅供个人学习、研究或参考使用，不构成任何形式的决策建议、专业指导或法律依据。未经授权，禁止任何单位或个人以商业售卖、虚假宣传、侵权传播等非学习研究目的使用本文内容。如需分享或转载，请保留原文来源信息，不得篡改、删减内容或侵犯相关权益。感谢您的理解与支持！