李俊才
CSDN：jcLee95
邮箱：291148484@163.com

专题目录：https://blog.csdn.net/qq_28550263/article/details/115718216

1. 链表的概念

链表是一种物理存储单元上非连续、非顺序的存储结构，它由一系列结点组成，其特点在于结点可以在运行时动态生成。

链表的存储结构特点

链表的每个结点包括两个部分：

• 一个是存储数据元素的数据域；
• 存储下一个结点地址的指针域。

链表可以用任意一组存储单元来存储其中额数据结构，其存储单元可以是不连续的。

单链表
链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起构成单链表。单链表即单向链表，单向指的是其指针域所存储的信息只能为一个方向。具体来说，单链表中的每个存储单元中，除了需要存储每个单元的数据外，还必须附带储存其直接后继存储单元的地址信息。如图所示：

双向链表
它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。

循环链表
循环的最后一个结点指向头结点从而形成一个环。可想而知，从循环链表中的任何一个结点出发都能找到任何其他结点。

循环单链表
尾元结点的后继指针指向表中的首元结点。其特点为：

• 其每个结点都处于一个循环链中，可以从任何一个位置开始，按照后继方向遍历整个链表。
• 其在合并与分裂时，若非必须从链表头节点开始，可直接在链表指针处进行合并，时间复杂度可达O(1)。

循环双链表
其每个结点包含两个指针指向直接前驱和直接后继，可以在两个方向上遍历某个结点之后以及之前的元素。循环双链表的特点为：

• 每个几点处于2个链中：1为后继方向的循环链链，2为前驱方向的循环链。
• 从某个结点出发进到直接前驱或者直接后继节点，时间复杂度均为O(1)。
• 查找第i个节点、删除第i个节点、在第i个节点处插入，都需要区分时哪一个方向。
• 修改指针要同时考虑在前驱循环链和后继循环链上的修改。
• 某个节点的直接前驱的直接后继或其直接后继的直接前驱都是该节点本身。

静态链表
用一维数组来进行描述的一种链表，它利益数组下标号来访问下一个节点，因此需要定义一个足够大的节点数组。

概念归纳

$$链表?\begin{array}{l}链表带有【头结点】：\{\begin{array}{l}表头指针\text{表头指针}表头指针指示头节点\text{头节点}头节点\\ 头节点链接指针\text{头节点链接指针}头节点链接指针指示首元结点\text{首元结点}首元结点\end{array}\\ 链表没有【头节点】：表头指针\text{表头指针}表头指针指示首元结点\text{首元结点}首元结点\end{array}$$

单链表进行插入和删除操作实际上不需要移动数据元素，只需要修改相关指针。
在TypeScript语言中并没有C和C++中那样指针的概念以用过指针的相关操作带出数据，我们只能来模拟这个过程。

与线性表/顺序表相比
由于链表不必须按顺序存储，它在插入的时候可以达到O(1)的复杂度，比线性表和顺序表（时间复杂度O(n)）快得多。但是链表查找一个节点或者访问特定编号的节点却需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

2. 单链表的TypeScript语言实现

2.1 单链表的节点

链表是由一个一个节点通过某种关系建立关联构成的一种数据结构，单链表也是如此。单链表中的所有节点只有一个指向各自直接后继节点的指针域以及各自的数据域：

一个最基本的单链表节点看起来是这个样子的：

class Lnode{
    /**
     * 链表节点类
     * @class Lnode
     * @constructor
     * @param next {Lnode} 指向下一节点的指针
     * @param data {any} 节点的数据
     */
    next: Lnode | null;   // 节点类型（Lnode）的nest也是节点类型Lnode，null是任意类型的子类型也可以不写
    data: any;
    constructor(data:any){
        this.data = data;
        this.next = null;
    }
};

ADT LinkList{
    init(id, name)        # 初始化（构造）单链表
    is_empty()            # 判断单链表是否为空
    top()                 # 获取链表的头部节点
    
    clear()               # 清空链表
    del(index)            # 从中间删除索引为`index`的一个节点
    drop(index)           # 删除索引为`i`节点及其之后的所有节点
    drop(index_1,index_2) # 删除从索引为`index_1`（包含）开始到索引为`index_2`（包含）的一段节点
    
    append(node)          # 在链表的最右端嵌入一个新的节点node
    append_left(node)     # 在链表的最左端嵌入新的节点node
    insert(index, node)   # 在链表的第`index`个节的位置挂载新的节点`node`
    p_insert(pointer)     # 在指向链表中的某个指针pointer后面的位置插入新节点
    
    pop()                 # 弹出链表尾部节点
    pop_left()            # 弹出链表头节点并返回
    
    toArray()             # 获取链表节点依次构成的数组，可以方便用于链表的遍历和后续利用数组随机取值
    
    reverse()             # 反转链表，直接将原链表反转而不返回值
    getReverse()          # 反转链表，返回反转后的链表，不改变原链表
}

ADT LinkList{
    init(id, name)        # 初始化（构造）单链表
    is_empty