数据结构漫游记：静态双向链表

嘿，各位技术潮人！好久不见甚是想念。生活就像一场奇妙冒险，而编程就是那把超酷的万能钥匙。此刻，阳光洒在键盘上，灵感在指尖跳跃，让我们抛开一切束缚，给平淡日子加点料，注入满满的passion。准备好和我一起冲进代码的奇幻宇宙了吗？Let's go！

我的博客：yuanManGan

我的专栏：C++入门小馆 C言雅韵集 数据结构漫游记  闲言碎语小记坊 题山采玉

目录

双向链表

定义链表

头插

打印

按值查找

insert_back

insert_front

删除指定位置

上期介绍了单链表，我们知道单链表在插入删除等部分，要实现这些功能要找到上一个结点会很困难，针对这一困难，我们可以再设置一个数组来存储该结点的上一个结点。

双向链表

定义链表

#include<iostream>

using namespace std;

const int N = 1e5 + 10;

int prev[N], ne[N], e[N], h, id;
int mp[N];

头插

// h id next
void push_front(int x)
{
    id++;
    e[id] = x;
    mp[x] = id;//存储下标
    ne[id] = ne[h];
    prev[id] = h;

    prev[ne[h]] = id;
//最后处理哨兵位
    ne[h] = id;
}

注意这里要最后改变ne[ h ]，不然找不到下一个结点。

时间复杂度O(1)。

打印

该操作无二异，直接看代码

void print()
{
    for(int i = ne[h]; i; i = ne[i])
        cout << e[i] << "->"; 
    cout << endl;       
}

时间复杂度O(n)。 

按值查找

很简单

int find(int x)
{
    return mp[x];
}

时间复杂度O(1)。 

insert_back

插入在指定位置之后，之前实现也很简单，现在就要仅仅只需要多处理一下prev就可以了

// p  x  p->next
void insert_back(int p, int x)
{
    id++;
    e[id] = x;
    mp[x] = id; 
    ne[id] = ne[p];
    prev[id] = p;
    
    prev[ne[p]] = id;
    ne[p] = id;//老样子最后处理ne[p]
}

时间复杂度O(1)。  

insert_front

好了到了双向链表的优点地方了，在这里找到前一个元素就轻轻松松了。

p-prev x  p  
void insert_front(int p, int x)
{
    id++；
    e[id] = x;
    mp[x] = id;

    ne[id] = p;
    pre[id] = prev[p];

    ne[prev[p]] = id;
    prev[p] = id;

}

时间复杂度O(1)。  

删除指定位置

删除也是很简单咯

pre[p] p ne[p]
void erace(int p)
{
	mp[e[p]] = 0;
    ne[prev[p]] = ne[p]; prev[ne[p]] = prev[p];
}

时间复杂度O(1)。 

总体来说双向链表在单链表学习的基础上来学习就是很简单了，有些操作时间复杂度不是O(1)就不进行实现了，实现起来也不难，但不会经常遇到，就这样吧！谢谢大家！