数组模拟实现 双向链表

作者： 作者的头像   .临渊 ,  2022-02-09 16:09:28 ,  所有人可见 ,  阅读 877

2


1

数组模拟实现 双向链表

一、双向链表简介

双链表（ 双向链表 ）在单链表的基础上，
在每个结点处增加了一个指向 直接前驱（ 前一个结点 ）的指针。

所以与单链表相比，双链表从任意一个结点，都能很方便地找到 前驱 和 后继（ 后一个结点 ）。

所谓 “ 单链表的基础 ”： 数组模拟实现单链表 - AcWing

双链表1.jpg{:height=”80%” width=”80%”}

二、用数组模拟实现双链表

1. 结点的模拟

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

int e[N]; // 存储结点的 数值 部分 
int l[N]; // 指向 前驱 结点的指针 ( 指向 左边 的结点 ) 
int r[N]; // 指向 后继 结点的指针 ( 指向 右边 的结点 ) 
int idx; // 作用同 单链表

说明：e[N] 、 l[N]、r[N] 以 同一个下标 i 关联在一起，即共同组成一个结点。
r[N] 的数值，即为下一个结点（后继）的地址。
l[N] 的数值，即为上一个结点（前驱）的地址。

​ 由于使用数组模拟 双链表，所以这个地址，就是 前 / 后 结点的下标
​ 即： 结点 e[ l[a] ] ← 结点 e[a]→ 结点 e[ r[a] ]

三、双链表功能的实现

1. 初始化

void init()
{
    // 选择两个结点作为 链表的边界（头结点），这两个结点不记录数值信息
    // 下标为 0 的结点表示链表的左端点，下表为 1 的结点表示链表的右端点
    r[0] = 1; // 0 号点的右边是 1 号点
    l[1] = 0; // 1 号点的左边是 0 号点
    // 这两个头结点的引入，能让第一个数据结点的操作与普通的结点相同，简化操作。

    idx = 2; // 下标为 0 和 1 的结点被占用了 
}

说明：

在 单链表 中，我们单独定义了 头指针 head，并且将 尾指针 NULL 定义为 -1。
这两个指针不作为链表中的结点，因此不占用数组。

在 双链表 中，我们换一种处理方式，
选取两个数组元素分别作为 头结点 和 尾结点，
由此，可以选择数组的前两个元素。

因此可以理解为，头指针 head = 0 指向头结点 ( 第一个空的结点 )，
r[0] 指向第一个数据结点 ( 实际上的第一个结点 )，
最后一个数据结点的后继是下标为 1 的空结点，即 NULL = 1。

双链表2.jpg{:height=”67%” width=”67%”}

idx 的含义

同单链表，idx 为 即将插入的结点的下标。

在单链表中，数组最初为空，idx 从 0 开始，
因此 第 k 个插入的结点 的下标为 k - 1

但按上述方法实现双链表，下标 0 和 1 已经被占据，
因此 idx 从 2 开始，即第 1 个结点的下标为 2，第 2 个结点的下标为 3 ……
因此 第 k 个插入的结点 的下标为 k + 1

2. 插入结点

在双链表中，结点有四种不同的插入方式：

  1. 将结点 x 插入到下标为 k 的结点的 右边；
  2. 将结点 x 插入到下标为 k 的结点的 左边；
  3. 将结点 x 插入，作为第一个结点（在 最左侧 插入结点）；
  4. 将结点 x 插入，作为最后一个结点（在 最右侧 插入结点）。

上述的插入方式可以用一个函数实现。

// 在下标为 k 的结点的右边插入结点 x
void add( int k, int x )
{
    e[idx] = x;
    r[idx] = r[k];
    l[idx] = k;

    l[r[k]] = idx;  // ( 1 ) 
    r[k] = idx;     // ( 2 )
    // ( 1 )( 2 ) 代码前后顺序不能改变 

    idx++;
}

双链表3.jpg{:height=”67%” width=”67%”}

  1. 在下标为 k 的结点的 右边 插入结点 x，调用 add( k, x )

  2. 在下标为 k 的结点的 左边 插入结点 x，调用 add( l[k], x )

    说明：在 i 结点的左边插入新结点，
    相当于在 i 结点的前一个（左边）结点的右边插入新结点。

    如上图所示，在 b 结点的左边插入新结点，可转换为在 a 结点的右边插入新结点。
    对于 下标为 k 的结点，其左边结点下标为 l[k]

  3. 将结点 x 插入，作为第一个结点 ( 在 最左侧 插入结点 ) ，调用 add( 0, x )

    转换为在 head 结点的右边插入新结点，而 head 结点的下标为 0 ( 在初始化中已经定义)

  4. 将结点 x 插入，作为最后一个结点（在 最右侧 插入结点），调用 add( l[1], x )

    转换为在 NULL 结点前的一个结点的右边插入新结点，
    而 NULL 结点的下标为 1 , 其左边结点下标为 l[1]

（注意区分字母 L(数组名) 和 数字 1）

3. 删除结点

删除下标为 k 的结点

int remove( int k )
{
    r[l[k]] = r[k]; // 调整该结点前后两个结点的指针 
    l[r[k]] = l[k];
}

双链表4.jpg{:height=”67%” width=”67%”}

同样，删除第一个结点和最后一个结点，也可以调用该函数实现

删除第一个结点：remove( r[0] )
删除最后一个结点：remove( l[1] )

四、应用场景：

用数组实现双向链表，并支持其基本操作。

题源： 827. 双链表 - AcWing题库

五、函数模板

#include <iostream>

using namespace std;

const int N = 100010;

int e[N]; // 存储结点的 数值 部分 
int l[N]; // 指向 前驱 结点的指针 ( 指向 左边 的结点 ) 
int r[N]; // 指向 后继 结点的指针 ( 指向 右边 的结点 ) 
int idx; // 作用同 单链表

// 初始化
void init()
{
    // 0 表示左端点，1 表示右端点
    r[0] = 1;
    l[1] = 0;
    // 0 号点的右边是 1 号点
    // 1 号点的左边是 0 号点
    // 这两个点是链表的边界，不是真实的结点
    idx = 2; // 下标为 0 和 1 的结点被占用了 
} 

// 在下标为 k 的结点的右边插入结点 x
void add( int k, int x ) 
{
    e[idx] = x;
    r[idx] = r[k];
    l[idx] = k;

    l[r[k]] = idx;  // ( 1 ) 
    r[k] = idx;     // ( 2 )
    // ( 1 )( 2 ) 代码前后顺序不能改变 

    idx++;
}

// 删除下标为 k 的结点
int remove( int k )
{
    r[l[k]] = r[k]; // 调整该结点前后两个结点的指针 
    l[r[k]] = l[k];
} 


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

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

    while( m-- )
    {
        int k, x;
        string op;
        cin >> op;
        if( op == "L")
        {
            cin >> x;
            add( 0, x );
        }
        else if( op == "R")
        {
            cin >> x;
            add( l[1], x );
        }
        else if( op == "D")
        {
            cin >> k;
            remove( k + 1); // 注意下标的转换 
        }
        else if( op == "IL" )
        {
            cin >> k >> x;
            add( l[k + 1], x); // 注意下标的转换 
        }
        else if( op == "IR" )
        {
            cin >> k >> x;
            add( k + 1, x); // 注意下标的转换 
        }
    }

    for( int i = r[0]; i != 1; i = r[i]) cout << e[i] << " ";
    /* 注意与单链表不同
       i 的初始值是第一个结点的下标
       链表的终止条件是 NULL 结点的下标 1
        下一个 i 是下一个结点的下标 */ 
    cout << endl;   

    return 0;
}

六、参考资料

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

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

#include <iostream>

using namespace std;

const int N = 100010;

int e[N], l[N], r[N], idx;

void init()
{
    r[0] = 1;
    l[1] = 0;
    idx = 2;
}

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

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

int main()
{
    init();

    int m;
    cin >> m;
    while( m-- )
    {
        int k, x;
        string op;
        cin >> op;
        if( op == "L")
        {
            cin >> x;
            add( 0, x );
        }
        else if( op == "R" )
        {
            cin >> x;
            add( l[1], x );
        }
        else if( op == "D" )
        {
            cin >> k;
            remove( k + 1 );
        }
        else if( op == "IL" )
        {
            cin >> k >> x;
            add( l[ k + 1 ], x );           
        }
        else if( op == "IR" )
        {
            cin >> k >> x;
            add( k + 1, x);
        }
    }

    for( int i = r[0]; i != 1; i = r[i] ) cout << e[i] << " ";
    cout << endl;
    return 0;   
}

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

0 评论