数组模拟实现 单链表

一、单链表简介

作用：单链表是一种 链式存储 的数据结构，用一组 地址任意 的存储单元存放线性表中的数据元素。

构成：单链表由 结点 组成（ 结点 = 数据 + 指针 ）

​ ① 数据：具体的数值（ 类比于数组 ）；
​ ② 指针：下一个结点的地址。

二、单链表与数组对比

{:height=”70%” width=”70%”}

对于数组：查询元素 快，插入或删除元素 慢

查找元素 9 ，只要通过 下标 1 即可找到 b[1] = 9
查找元素 9 之后的数组元素，则通过 下标加 1 ，得到 b[ 1 + 1 ] = b[2] = 16

删除元素 9 时，需要把其后面的所有元素向前移动一位，以填补 9 的空位。
插入新元素，则需要将插入位置后的元素向后移动一位，以空出空位给新元素。

对于单链表：查询元素 慢，插入或删除元素 快

查找元素 9 ，需要从 头指针 Head 开始，根据指针，逐个结点寻找 Head → 5 → 9。
查找元素 9 之后的元素，则通过数值 9 的结点的 指针，找到下一个结点。

插入或删除元素，只要改变其前后的指针的指向关系，不影响其他元素。

三、用数组模拟实现单链表（静态链表）

1. 结点的模拟：

模拟 链表 关键在于模拟 结点，
模拟 结点，就需要有 数值域 与 指针域。

因此，创建两个一维数组，分别作为链表的 数值域 与 指针域。

int e[N]; // e[i] 表示结点 i 的数值 
int ne[N]; // ne[i] 表示结点 i 的 next 指针（即结点 i 的下一个结点的地址） 

说明：e[N] 与 ne[N] 以 同一个下标 i 关联在一起，即共同组成一个结点。
而 ne[i] 中的数值，即为下一个结点的地址。

​ 由于使用数组模拟单链表，所以这个地址，就是 下一个结点的下标
​ 即：结点 e[a],ne[a] → 结点 e[ ne[a] ],ne[ ne[a] ]

2. 其他准备工作：

int head; // 头指针，指向头结点
int idx; // 其值为即将插入的新结点的下标

说明：头结点：链表的第一个结点
头指针：指向头结点的指针（其值为第一个结点的下标）

{:height=”70%” width=”70%”}

idx 的作用：用数组模拟的链表称为静态链表，即链表的大小在一开始就确定了（同数组的创建）。
插入一个新结点（即为空的数组赋值）：e[idx] = value; ne[idx] = next
由此，以 idx 为下标的结点被插入，若还需要插入新结点，idx 要作为新结点的下标，因此 idx ++

idx 的引申含义：

链表中没有结点：idx = 0；
插入第一个结点后：idx = 0 + 1 = 1；
插入第二个结点后：idx = 1 + 1 = 2 ；
......

插入第 i 个结点后：idx = i

因此 idx 表示链表 曾经 一共 插入了 多少个结点。
同样，对于第 k 个插入的结点的下标 = k - 1

但是 idx 并 不能表示 此时链表中一共有多少个结点，因为即使有结点被删除，idx 始终递增。

对于删除的结点，其数据仍然保存在数组中，
只是不再有指针指向它，即无法被访问到，我们就认为该结点从链表中删除了。
这就克服了数组删除元素后，后面的元素需要前移来填补空位的缺点。

四、单链表功能的实现：

1. 初始化

void init(){
    idx = 0; // 当前链表中没有结点，可以从 0 开始创建 
    head = -1; // 数组下标没有 -1，因此用 -1 表示空 NULL
}

{:height=”30%” width=”30%”}

2. 插入结点：

① 将结点 x 插入到 头结点

void add_to_head( int x )
{
    e[idx] = x; // 新结点的数值 
    ne[idx] = head; // 新结点指针指向的是原来 head 指向的结点 (1)
    head = idx; // head 指向新结点 (2)
    // (1) (2) 顺序不能改变
    idx++; 
}

{:height=”50%” width=”50%”}

② 在下标为 k 的结点后插入结点 x

void add( int x, int k ) 
{
    e[idx] = x; // 新结点的数值 
    ne[idx] = ne[k]; // 新结点指针指向的是原来 下标为 k 的结点指向的结点 (1)
    ne[k] = idx; // 原来 下标为 k 的结点指针指向新结点 (2) 
    // (1) (2) 顺序不能改变
    idx++;
} 

{:height=”50%” width=”50%”}

说明：单链表可以在任意的位置插入结点，但是想在 O( 1 ) 的时间复杂度下插入，
就只能是在某个点的后面插入。
因为单链表能在 O( 1 ) 的时间内找到下一个结点，但找不到上一个结点，
单链表只往后看，不往前看，想找前面的结点，只能从头开始重新遍历。

3. 删除结点

① 删除下标为 k 的结点之后的那个结点：

void remove( int k ) 
{
    ne[k] = ne[ne[k]]; // 下标为 k 的结点的指针指向 原来下一个结点的 下一个结点 
//  ne[k] = ne[k + 1]; // 错误，下标为 k 的结点的下一个点的下标是 ne[k]，而不是 k + 1 
}

{:height=”50%” width=”50%”}

② 删除头结点

void remove_head()
{
    head = ne[head]; // 头指针 head 指向下下个结点（删除了下一个结点） 
}

{:height=”50%” width=”50%”}

说明：删除下标为 k 的结点，只是使得没有指针指向该结点 e[k],ne[k]
这样当我们在访问链表的元素时，就会忽略该结点，
相当于删除了这个结点，而实际上这个结点的值还保存在数组中。

​ 虽然造成了一定的空间的浪费，但是好处在于速度快
​ （即克服了数组删除元素后，后面的元素需要前移来填补空位的缺点）

五、应用场景：

存储一组数据序列，并实现 顺序查找、插入、删除等操作。

题源 ： 826. 单链表 - AcWing题库

六、函数模板

#include<iostream>
using namespace std;

const int N = 100010;

int head; // 表示头结点的下标 
int e[N]; // e[i] 表示结点 i 的值 
int ne[N]; // ne[i] 表示结点 i 的 next 指针（即结点 i 的下一个结点的地址） 
int idx; // 存储当前用到的地址

// 初始化          
void init()
{
    idx = 0; // 当前链表中没有结点，可以从 0 开始创建 
    head = -1; // 数组下标没有 -1，因此用 -1 表示空 NULL
}

// 插入结点
// 根据插入结点位置的不同分为不同方式： 

// 将 x 插入到头结点（即 head 指向的结点）
// head 为头指针，其不携带数值，它指向的结点才是第一个结点 
void add_to_head( int x )
{
    e[idx] = x; // 新结点的数值 
    ne[idx] = head; // 新结点指针指向的是原来 head 指向的结点 (1)
    head = idx; // head 指向新结点 (2)
    // (1) (2) 顺序不能改变
    idx++; 
}

// 在下标为 k 的结点后插入新的结点，值为 x 
void add( int x, int k ) 
{
    e[idx] = x; // 新结点的数值 
    ne[idx] = ne[k]; // 新结点指针指向的是原来 下标为 k 的结点指向的结点 (1)
    ne[k] = idx; // 原来 下标为 k 的结点指针指向新结点 (2) 
    // (1) (2) 顺序不能改变
    idx++;
} 

// 删除下标为 k 的结点之后的那个结点 
void remove( int k ) 
{
    ne[k] = ne[ne[k]]; // 下标为 k 的结点的指针指向 原来下一个结点的下一个结点 
//  ne[k] = ne[k + 1]; // 错误，下标为 k 的结点的下一个点的下标是 ne[k]，而不是 k + 1 
}

void remove_head()
{
    head = ne[head]; // 头指针 head 指向下下个结点（删除了下一个结点） 
}

int main()
{
    int m;
    cin >> m;

    init(); // 不要忘了初始化

    while( m-- )
    {
        int k, x;
        char op;

        cin >> op;
        if( op == 'H')
        {
            cin >> x;
            add_to_head(x);
        }
        else if( op == 'D' )
        {
            cin >> k;
            if( k == 0)
            {
                remove_head();
            }
            else remove(k - 1); 
            // 注意题目中描述为：第 k 个插入的元素，因此下标为 k - 1 
        }
        else
        {
            cin >> k >> x;
            add( x , k - 1 );
            // 注意题目中描述为：第 k 个插入的元素，因此下标为 k - 1
        }
    }

    for( int i = head; i != -1; i = ne[i] ) cout << e[i] << ' ';
    cout << endl; 

    return 0;
}

七、补充：静态链表和动态链表

之所以用数组模拟链表（用静态链表代替动态链表），就是因为静态链表处理问题更 快。

动态链表，其结点可通过结构体创建，数量不限（需要一个就创建一个）

struct Node
{
    int val;
    Node *next;
}

但每次创建一个结点 Node，就要调用一次 new Node();，而这个操作是 非常耗时 的。

在笔试中，链表的长度多为十万到百万，单单是把这些结点都 new 出来，就已经超时了，
因此在平时笔试中，我们一般不会采用这种动态链表方式。（在实际的项目开发等运用中，仍多采用动态链表）

另一个方面，用数组模拟链表（静态链表）可以做用指针模拟链表的所有操作。

八、(无注释版)函数模板

#include <iostream>
using namespace std;

const int N = 100010;

int e[N], ne[N], head, idx;

void init()
{
    head = -1;
    idx = 0;
}

void add_to_head( int x )
{
    e[idx] = x;
    ne[idx] = head;
    head = idx;
    idx++;
}

void add( int k, int x )
{
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx++;
}

void remove( int k )
{
    ne[k] = ne[ne[k]];
}

void remove_head()
{
    head = ne[head];
}

int main()
{
    int m;
    scanf( "%d", &m);

    init();

    while( m-- )
    {
        int x, k;
        char t;
        cin >> t;
        if( t == 'H' )
        {
            scanf( "%d", &x);
            add_to_head( x );
        }
        else if( t == 'I' )
        {
            scanf( "%d%d", &k, &x );
            add( k - 1, x );
        }
        else if( t == 'D' )
        {
            scanf( "%d", &k );
            if( k == 0 )
            {
                remove_head();
            }
            else
            {
                remove( k - 1 );
            }
        }
    }

    for( int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
    // 注意 i 的变化 ( i 为当前结点的指针，而不是 i++ )
    cout << endl;
    return 0;
} 

九、参考资料

1. y 总的课~~
2. 单链表_百度百科 (baidu.com)

（接受批评指正，欢迎交流补充~~ XD）