【数据结构】双向链表 C++

2024-04-17 12:39:42

一、什么是双向链表

1、定义

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

双向链表的结构如图（图片来源于网络）：

2、时空复杂度

双向链表的空间复杂度是 O ( n ) O(n) O(n) 的，其时间复杂度如下：

操作 时间复杂度
遍历 O ( n ) O(n) O(n)
访问指定节点 O ( 1 ) O(1) O(1)
删除指定编号节点 O ( n ) O(n) O(n)
删除指定位置节点 O ( 1 ) O(1) O(1)
在指定编号的节点后插入节点 O ( n ) O(n) O(n)
在指定位置的节点后插入节点 O ( 1 ) O(1) O(1)
查询前驱、后继 O ( 1 ) O(1) O(1)
修改指定编号节点的值 O ( n ) O(n) O(n)
修改指定位置节点的值 O ( 1 ) O(1) O(1)
交换两个 list 容器 O ( 1 ) O(1) O(1)

二、双向链表的基本操作

1. 定义双向链表节点

每个节点有三个值：

  1. val：存储每个节点的权值；
  2. last：指向每个节点的前面的第一个节点；
  3. next：指向每个节点的后面的第一个节点；

代码如下：

template<typename T>
struct ListNode{
    T value;
    ListNode<T>* last;
    ListNode<T>* next;
    ListNode():value(0){
        last=NULL,next=NULL;
    }
    ListNode(const T &x):value(x){
        last=NULL,next=NULL;
    }
    ~ListNode(){
        value=0;
        delete last;
        delete next;
    }
};

2. 创建双向链表类

类里面包含两个节点和一个变量：

  1. headnode：头节点，初始时前驱后继均为空，值为 − 1 -1 −1；
  2. endnode：尾节点，初始时前驱后继均为空，值为 − 1 -1 −1；
  3. listsize：记录双向链表的节点个数，不包含头尾节点；

代码如下：

template<typename T>
class list{
    private:
        unsigned listsize;
        ListNode<T>* headnode;
        ListNode<T>* endnode;
};

3. 初始化双向链表类

共有四种初始化方式：

  1. list<类型名> a;：此时创建一个空的双向链表；
  2. list<类型名> a(n);：此时创建一个大小为 n n n 的双向链表，并将所有点的初始值赋为 0 0 0；
  3. list<类型名> a(n,m)：此时创建一个大小为 n n n 的双向链表，并将所有点的初始值赋为 m m m；
  4. list<类型名> a={a1,a2,a3,...,an};：此时创建一个大小为 n n n 的双向链表，并将第 i i i 个节点的初始值赋为 a i a_i ai​；

第一种初始化方式代码如下：

list():listsize(0){
    headnode=new ListNode<T>(-1);
    endnode=new ListNode<T>(-1);
}

第二种初始化方式代码如下：

list(const int &size_t):
    listsize(size_t) {
    headnode=new ListNode<T>(-1);
    endnode=new ListNode<T>(-1);
    ListNode<T>* now=headnode;
    for(int i=0;i<listsize;++i){
        ListNode<T>* newnode=new ListNode<T>(0);
        endnode->last=newnode;newnode->next=endnode;
        newnode->last=now;now->next=newnode;
        now=now->next;
    }
}

第三种初始化方式代码如下：

list(
    const int &size_t,
    const int &val
):listsize(size_t){
    headnode=new ListNode<T>(-1);
    endnode=new ListNode<T>(-1);
    ListNode<T>* now=headnode;
    for(int i=0;i<listsize;++i){
        ListNode<T>* newnode=new ListNode<T>(val);
        endnode->last=newnode;newnode->next=endnode;
        newnode->last=now;now->next=newnode;
        now=now->next;
    }
}

第四种初始化方式代码如下：

typedef std::initializer_list<T> lisval;
list(lisval vals){
    listsize=0;
    headnode=new ListNode<T>(-1);
    endnode=new ListNode<T>(-1);
    ListNode<T>* now=headnode;
    for(auto val:vals){
        ListNode<T>* newnode=new ListNode<T>(val);
        endnode->last=newnode;newnode->next=endnode;
        newnode->last=now;now->next=newnode;
        now=now->next; ++listsize;
    }
}

3. 一些基础的函数

这些函数是除了加点删点之外最常见的几个函数。

  1. size()：获取链表的大小，返回一个 unsigned 值，表示当前链表中普通节点（非头尾节点）的个数。

    代码如下：

    unsigned size() const {
    return listsize;
}

  2. empty()：返回当前链表是否为空，如果是，返回 true，否则返回 false。

    代码如下：

    bool empty() const {
    return listsize==0;
}

  3. begin()：返回第一个普通节点。

    代码如下：

    ListNode<T>* begin(
) const {
    return headnode->next;
}

  4. end()：返回尾指针。

    代码如下：

    ListNode<T>* end(
) const {
    return endnode;
}

  5. rbegin()：返回最后一个普通节点。

    代码如下：

    ListNode<T>* rbegin(
) const {
    return endnode->last;
}

  6. rend()：返回头指针。

    代码如下：

    ListNode<T>* rend(
) const {
    return headnode;
}

  7. front()：返回第一个普通节点的值。

    代码如下：

    T front() const {
    return begin()->value;
}

  8. back()：返回最后一个普通节点的值。

    代码如下：

    T back() const {
    return rbegin()->value;
}

  9. print()：遍历并输出链表中每个普通节点的值，结尾换行。

    代码如下：

    void print(
) const {
    if(empty()) return;
    ListNode<T>* now=headnode->next;
    while(now->next!=NULL){
        printf("%d ",now->value);
        now=now->next;
    } putchar('\n');
}

  10. swap(list<类型名> &b)：交换两个 list 容器，实际上是交换头尾指针和 l i s t s i z e listsize listsize。

    代码如下：

    void swap(list<T> &b){
    ListNode<T>* temp;
    temp=headnode;
    headnode=b.headnode;
    b.headnode=temp;
    temp=endnode;
    endnode=b.endnode;
    b.endnode=temp;
    unsigned size_t=listsize;
    listsize=b.listsize;
    b.listsize=size_t;
}

5. 插入节点

共四种方法，代码如下：

void push_back(
    const T &val
){ ++listsize;
    if(endnode->last==NULL){
        ListNode<T>* newnode=new ListNode<T>(val);
        endnode->last=newnode;newnode->next=endnode;
        headnode->next=newnode;newnode->last=headnode;
        return;
    }
    ListNode<T>* pre=endnode->last;
    ListNode<T>* newnode=new ListNode<T>(val);
    pre->next=newnode;newnode->last=pre;
    newnode->next=endnode;endnode->last=newnode;
}

void push_front(
    const T &val
){ ++listsize;
    if(headnode->next==NULL){
        ListNode<T>* newnode=new ListNode<T>(val);
        endnode->last=newnode;newnode->next=endnode;
        headnode->next=newnode;newnode->last=headnode;
        return;
    }
    ListNode<T>* suf=headnode->next;
    ListNode<T>* newnode=new ListNode<T>(val);
    headnode->next=newnode;newnode->last=headnode;
    newnode->next=suf;suf->last=newnode;
}

void insert(
    const T &pos,
    const T &val
){  
    int nowpos=0;
    if(pos==0){
        push_front(val);
        ++listsize; return;
    } else if(pos>=listsize){
        push_back(val);
        ++listsize; return;
    }
    ListNode<T>* now=headnode->next;
    while(now->next!=NULL){
        ++nowpos;
        if(nowpos==pos){
            ListNode<T>* newnode=new ListNode<T>(val);
            ListNode<T>* suf=now->next;
            newnode->next=suf;suf->last=newnode;
            newnode->last=now;now->next=newnode;
            ++listsize; return;
        }
        now=now->next;
    }
}

void insert(
    ListNode<T>* now,
    const T &val
){
    if(now==endnode){push_back(val); return;}
    ListNode<T>* newnode=new ListNode<T>(val);
    ListNode<T>* suf=now->next;
    newnode->next=suf;suf->last=newnode;
    newnode->last=now;now->next=newnode;
    ++listsize; return;
}

6. 修改指定位置的值

两种方法，代码如下：

void reassign(
    const T &pos,
    const T &val
){
    if(pos>listsize) return;
    if(empty()||!pos) return;
    ListNode<T>* now=headnode->next;
    int nowpos=0;
    while(now->next!=NULL){
        ++nowpos;
        if(nowpos==pos){
            now->value=val;
            return;
        } now=now->next;
    }
}

void reassign(
    ListNode<T>* now,
    const int &val
) const {
    now->value=val;
}

7.删除节点

和插入一样，共有四种，代码如下：

void pop_back(){
    if(empty()) return;
    ListNode<T>* now=endnode->last;
    ListNode<T>* pre=now->last;
    if(pre==headnode){
        endnode->last=NULL;
        headnode->last=NULL;
        --listsize; return;
    }
    endnode->last=pre;
    pre->next=endnode;
    --listsize;
}

void pop_front(){
    if(empty()) return;
    ListNode<T>* now=headnode->next;
    ListNode<T>* suf=now->next;
    if(suf==endnode){
        endnode->last=NULL;
        headnode->last=NULL;
        --listsize; return;
    }
    headnode->next=suf;
    suf->last=headnode;
    --listsize;
}

void erase(
    const int &pos
) {
    if(pos>listsize) return;
    if(empty()||!pos) return;
    ListNode<T>* now=headnode->next;
    int nowpos=0;
    while(now!=endnode){
        ++nowpos;
        if(nowpos==pos){
            ListNode<T>* pre=now->last;
            ListNode<T>* suf=now->next;
            if(pre
上一篇：【MYSQL】MySQL整体结构之系统服务