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

一、什么是双向链表

1、定义

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

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

2、时空复杂度

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

操作	时间复杂度
遍历	$O(n)$
访问指定节点	$O(1)$
删除指定编号节点	$O(n)$
删除指定位置节点	$O(1)$
在指定编号的节点后插入节点	$O(n)$
在指定位置的节点后插入节点	$O(1)$
查询前驱、后继	$O(1)$
修改指定编号节点的值	$O(n)$
修改指定位置节点的值	$O(1)$
交换两个 list 容器	$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$；
2. endnode：尾节点，初始时前驱后继均为空，值为 $-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$ 的双向链表，并将所有点的初始值赋为 $0$；
3. list<类型名> a(n,m)：此时创建一个大小为 $n$ 的双向链表，并将所有点的初始值赋为 $m$；
4. list<类型名> a={a1,a2,a3,...,an};：此时创建一个大小为 $n$ 的双向链表，并将第 $i$ 个节点的初始值赋为 $a_i$；

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

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 容器，实际上是交换头尾指针和 $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==headnode||suf==endnode){endnode->last=NULL;headnode->next=NULL;delete now;--listsize; return;}pre->next=suf;suf->last=pre;delete now;--listsize; return;}now=now->next;}
}

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

8. 注销双向链表类

遍历一遍，然后将每个节点都删除就可以了。

代码如下：

~list(){ListNode<T>* now=headnode->next;while(now!=NULL){ListNode<T>* nxt=now->next;delete now;now=nxt;} delete headnode; listsize=0;
}

三、完整代码

我知道你们只看这个

码风丑陋，不喜勿喷

#include<stdio.h>
#include<stdlib.h>
#include<initializer_list>
namespace STL{template<typename T>struct ListNode{T value;ListNode<T>* last;ListNode<T>* next;ListNode():value({}){last=NULL,next=NULL;}ListNode(const T &x):value(x){last=NULL,next=NULL;}~ListNode(){// value={};last=NULL;next=NULL;}};template<typename T>class list{private:unsigned listsize;ListNode<T>* headnode;ListNode<T>* endnode;public:list():listsize(0){headnode=new ListNode<T>(T({-1}));endnode=new ListNode<T>(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;}}unsigned size() const {return listsize;}bool empty() const {return listsize==0;}ListNode<T>* begin() const {return headnode->next;}ListNode<T>* end() const {return endnode;}ListNode<T>* rbegin() const {return endnode->last;}ListNode<T>* rend() const {return headnode;}T front() const {return begin()->value;}T back() const {return rbegin()->value;}void print() const {if(empty()) return;ListNode<T>* now=headnode->next;while(now->next!=NULL){printf("%lld ",now->value);now=now->next;} putchar('\n');}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;}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;}void pop_back(){if(empty()) return;ListNode<T>* now=endnode->last;ListNode<T>* pre=now->last;if(pre==headnode){endnode->last=NULL;headnode->next=NULL;delete now;--listsize; return;}endnode->last=pre;pre->next=endnode;delete now;--listsize;}void pop_front(){if(empty()) return;ListNode<T>* now=headnode->next;ListNode<T>* suf=now->next;if(suf==endnode){endnode->last=NULL;headnode->next=NULL;delete now;--listsize; return;}headnode->next=suf;suf->last=headnode;delete now;--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==headnode||suf==endnode){endnode->last=NULL;headnode->next=NULL;delete now;--listsize; return;}pre->next=suf;suf->last=pre;delete now;--listsize; return;}now=now->next;}}void erase(ListNode<T>* now){  if(now==headnode) return;if(now==endnode) return;if(empty()) return;ListNode<T>* pre=now->last;ListNode<T>* suf=now->next;if(pre==headnode||suf==endnode){endnode->last=NULL;headnode->last=NULL;delete now;--listsize; return;}pre->next=suf;suf->last=pre;delete now;--listsize; return;}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;}~list(){ListNode<T>* now=headnode->next;while(now!=NULL){ListNode<T>* nxt=now->next;delete now;now=nxt;} delete headnode;listsize=0;}};
}
using STL::list;signed main(){system("pause");
}

给个赞再走吧