前言
链表是一种数据结构。在链表中有几个重要的概念：
一个链表对象的结构可能是这样的：
const linkedList = { head: { value: 'A', next: { value: 'B', next: null } } }
这是一个单项链表
| 关键字 | 描述 |
| node | 节点 |
| head | 头节点，第一个节点 |
| tail | 尾节点，最后一个节点 |
| prev | 一般指代存储了上一个节点的引用 |
| next | 一般指代存储了下一个节点的引用 |
| current | 一般指代链表的当前节点 |
| value | 当前节点的值 |
单向链表与双向链表：
- 单向链表：节点上会有一个next属性指向下一个节点
- 双向链表：节点上会有一个next属性指向下一个节点，同时有一个属性prev指向上一个节点
链表类
// 定义链表节点类型 interface LinkedListNode { value: number; next: LinkedListNode | null; } // 定义链表类 class LinkedList { // 表示头节点 private head: LinkedListNode | null = null; // 表示尾节点 private tail: LinkedListNode | null = null; // 用来表示链表的长度 private len: number = 0; /** * @method add * @description 添加链表元素，添加到链表末尾位置 * @param n number */ add(n: number) { // 生成链表节点 const node: LinkedListNode = { value: n, next: null, }; // head节点特殊处理 if (this.head === null) { this.head = node; } // 获取当前tail节点 const tailNode = this.tail; // 当前tail节点存在，则将next指针，指向node if (tailNode) { tailNode.next = node; } // 更新tail节点的指向 this.tail = node; // 注意，这里链表长度单独计算的，长度+1 this.len++; } /** * @method map * @description 遍历链表所有的元素 - 从头到尾 * @returns number[] 链表所有节点的值 */ map(): number[] { // 存储 let res: number[] = []; // 初始指向head节点 let currentNode = this.head; // 当前currentNode节点存在，进入循环 while (currentNode) { // 当前节点的值 res.push(currentNode.value); // 将当前节点的指针，指向 currentNode = currentNode.next; } // 返回结果 return res; } /** * @description 返回链表的长度 */ get length() { return this.len; } }
当前链表类，定义的是一个单向链表，可以在这个基础上，思考下双向链表是如何实现的。
创建链表对象
通过链表类，创建一个链表对象，并执行链表节点添加
// 实例化创建链表对象 const linkedList = new LinkedList(); // 依次添加元素 linkedList.add(1); linkedList.add(2); linkedList.add(3); linkedList.add(4); linkedList.add(5); // 遍历链表对象 console.log(linkedList.map()); // [1, 2, 3, 4, 5]
小课堂
通过该篇文章我们了解了链表以及单向和双向链表，还有链表类的定义，遍历链表元素。在下一篇文章中我们来研究下如何反转链表
