一种物理存储单元上非连续、非顺序的，数据元素的逻辑顺序为指针链接次序的数据结构：链表

结构体链表（动态链表）

由于动态链表每一个节点都需要 new 操作分配内存空间，而 new 操作极耗时，因此算法题不常用结构体链表，而常用数组模拟链表。

单向链表

创建

节点结构

单向链表每个节点包含数据域和指针域，数据域储存数据，指针域指向下一个节点，一般用结构体实现。

// 数据域为一个int值
struct NODE
{
    int value;
    NODE *next;
};

头指针、头节点、尾指针

单向链表除了储存数据的节点，还有头指针、头节点。

头指针指向头节点，链表必须有头指针，否则将无法知晓链表从哪里开始，数据就会丢失在内存里。
头节点是一个不储存数据的节点（也可以选择把链表长度储存在头节点），在某些情况下头节点可以使问题更简化。
- 在单链表中可以没有头节点，如下图。轻微修改初始化链表的方式即可实现。本模板均为含头节点的链表。

尾指针指向链表最后一个节点，本例中就是储存 $3$ 的节点。
- 没有尾节点只不过不能在 $O(1)$ 时间尾接元素，影响不大。本模板没有使用尾节点。（但图中标有尾节点）
链表最后一个节点的指针为空指针 NULL，标志链表结束。

初始化

第 $1$ 行：分配一个新节点
第 $2$ 行：将头节点指向 NULL

NODE *head;
void init()
{
    head = new NODE;
    head->next = NULL;
}

头插元素

第 $1$ 行：分配一个新节点
第 $2$ 行：储存值
第 $3$ 行：将新节点指向第一个节点（即头节点指向的节点）
第 $4$ 行：将头节点指向新节点

void push_front(int x)
{
    NODE *node = new NODE;
    node->value = x;
    node->next = head->next;
    head->next = node;
}

尾接元素

第 $1$ 行：分配一个新节点
第 $2$ 行：储存值
第 $3$ 行：因为新节点将会是最后一个节点，所以将新节点指向 NULL
第 $4\sim6$ 行：从头遍历到尾，找到之前的最后一个节点的地址
第 $7$ 行：将之前的最后一个节点指向新节点

void push_back(int x)
{
    NODE *node = new NODE;
    node->value = x;
    node->next = NULL;
    NODE *p = head;
    while (p->next != NULL)
        p = p->next;
    p->next = node;
}

插入节点

如图，如果要在链表第 0 个节点后插入一个新节点，那就需要这几步：

找到第 0 个节点
创建新节点并储存值
将新节点指针指向第 1 个节点
将第 0 个节点的指针改为指向新节点

第 $1\sim3$ 行：从头遍历找到第 id 个节点
第 $4$ 行：分配一个新节点
第 $5$ 行：储存值
第 $6$ 行：将新节点指向第 id+1 个节点（即第 id 个节点指向的节点）
第 $7$ 行：将第 id 个节点指向新节点

void insert(int id, int x)
{
    NODE *tmp = head;
    for (int i = 0; i <= id; i++)
        tmp = tmp->next;
    NODE *node = new NODE;
    node->value = x;
    node->next = tmp->next;
    tmp->next = node;
}

删除节点

如图，如果要删除第 1 个节点，需要这几步：

找到第 0 个节点
储存第 1 个节点地址
- 防止丢失
将第 0 个节点指向第 2 个节点
释放第 1 个节点

第 $1\sim3$ 行：从头遍历找到第 id-1 个节点
第 $4$ 行：储存第 id 个节点的地址（即第 id-1 个节点指向的节点）
第 $5$ 行：将第 id-1 个节点指向第 id+1 个节点（即第 id 个节点指向的节点）
第 $6$ 行：释放第 id 个节点

void erase(int id)
{
    NODE *tmp = head;
    for (int i = 0; i < id; i++)
        tmp = tmp->next;
    NODE *del = tmp->next;
    tmp->next = del->next;
    delete del;
}

遍历输出

输出比较简单，从头开始遍历输出，直到指针为空指针。

void print()
{
    for (NODE *p = head->next; p != NULL; p = p->next)
        cout << p->value << ' ';
    cout << endl;
}

双向链表

双向链表无非是每个节点多了一个指针，用来储存前一个节点的地址。包含头指针、头节点（可选）、数据节点、尾指针（可选）

一般用双向循环链表，这样可以不需要头节点、尾指针。

STL 实现：\<list\>

STL list 容器实际上就是双向链表，因此可以直接使用，非常方便。（当然手写的效率可能会更高）

数组模拟链表（静态链表）

由于动态链表效率太低，在算法题中几乎不可用，因此一般使用数组模拟链表。其思维和链表一样，只不过并没有动态分配内存空间，而是直接划分一个数组出来，数组的每一位就是一个链表节点，数组下标便作为链表的地址，next 指针就用整型来表示。

但是静态链表有一个缺点是，删除节点后不能像动态链表一样释放它的空间，这个节点会仍然存在于数组中，只不过再也不会遍历到它。这个问题在算法题一般不会有问题，但实际应用不建议使用静态链表。

单向静态链表

const int SIZE = 100010;  // 链表长度

int head, idx;            // 头指针、数组位数
int val[SIZE], nxt[SIZE]; // 链表数据、下一位指针

// 初始化静态链表
void init()
{
    head = -1;
    idx = 0;
}

// 头插元素
void push_front(int x)
{
    val[idx] = x;
    nxt[idx] = head;
    head = idx;
    idx++;
}

// 在第pos位元素后插入x（元素序号从0开始）
void insert(int pos, int x)
{
    val[idx] = x;
    nxt[idx] = nxt[pos];
    nxt[pos] = idx;
    idx++;
}

// 删除第pos位元素，不可删除节点0
void erase(int pos)
{
    nxt[pos] = nxt[nxt[pos]];
}

// 遍历输出
void print()
{
    for (int i = head; i != -1; i = nxt[i])
        cout << val[i] << ' ';
    cout << endl;
}

双向静态链表

const int SIZE = 100010; // 链表长度

int idx, val[SIZE], nxt[SIZE], prv[SIZE]; // 数组位数、链表数据、下一位指针、上一位指针

// 初始化静态双向链表
void init()
{
    nxt[0] = 1;
    prv[1] = 0;
    idx = 2;
}

// 头插元素
void push_front(int x)
{
    val[idx] = x;
    nxt[idx] = nxt[0];
    prv[idx] = 0;
    prv[nxt[0]] = idx;
    nxt[0] = idx;
    idx++;
}

// 尾接元素
void push_back(int x)
{
    val[idx] = x;
    nxt[idx] = 1;
    prv[idx] = prv[1];
    nxt[prv[1]] = idx;
    prv[1] = idx;
    idx++;
}

// 在第pos位元素后插入x（元素序号从2开始）
void insert(int pos, int x)
{
    val[idx] = x;
    nxt[idx] = nxt[pos];
    prv[idx] = pos;
    prv[nxt[pos]] = idx;
    nxt[pos] = idx;
    idx++;
}

// 删除第pos位元素，不可删除节点0/1
void erase(int pos)
{
    nxt[prv[pos]] = nxt[pos];
    prv[nxt[pos]] = prv[pos];
}

// 遍历输出
void print()
{
    for (int i = nxt[0]; i != 1; i = nxt[i])
        cout << val[i] << ' ';
    cout << endl;
}

数据结构 | 链表