线性表中的双链表
作者：Rem ㅤ | 发布时间：
介绍
在单链表中，节点只能单向顺序访问，只能从前向后遍历，如果要找出某节点的前驱就只能从头遍历，这样时间度为O(n)，使用双链表可以解决这一问题，在双链表中除了首节点和尾节点每个节点都可以直接找到其前驱和后继，同样找出某节点的前驱节点时时间复杂度只有O(1)。但是每个节点多占用4Byte的空间来保存前驱指针，所以这是以空间换时间的一种体现。
代码对比
类定义
单链表：
template <class T>
class LNode //单链表节点
{
public:
T data; //数据域
struct LNode *next; //指针域
LNode(T data) : data(data), next(NULL) {} //有参构造
LNode() : next(NULL) {} //无参构造
};双链表：
template <class T>
class LinearTable
{
public:
T data; //数据
struct LinearTable *prior, *next; //前驱和后继指针
LinearTable() : prior(NULL), next(NULL){}; //无参构造
LinearTable(T _data) : data(_data), prior(NULL), next(NULL){}; //有参构造
LinearTable(LinearTable<T> *_prior, T _data) : prior(_prior), data(_data), next(NULL){}; //带前驱节点的有参构造
};
双链表多了一个指针。另外此处我多用了一个有参构造函数，在创建节点的时候可以调用该构造函数直接确定节点的前驱，可以优化代码结构。
前插法创建链表
单链表：
template <class T>
LinkList<T> List_HeadInsert(LinkList<T> &head, int n) //带头结点的头插法创建链表,n为数据数量
{
head = new LNode<T>; //头节点
T data; //数据
for (int i = 0; i < n; i++)
{
cin >> data; //读取输入
LNode<T> *s = new LNode<T>(data); //创建新的节点
s->next = head->next; //插入到头部
head->next = s;
}
return head; //返回头节点
}双链表：
template <class T>
LinkList<T> List_HeadInsert(LinkList<T> &head, int n) //带头结点的头插法创建链表,n为数据数量
{
head = new LNode<T>; //头节点
T data; //数据
for (int i = 0; i < n; i++)
{
cin >> data; //读取输入
LNode<T> *s = new LNode<T>(head, data); //创建新的节点
s->next = head->next; //更新后继
head->next = s; //更新后继
if (s->next != NULL)
s->next->prior = s; //更新前驱
s->prior = head; //更新前驱
}
return head; //返回头节点
}
相比之下双链表多了一步更新前驱节点。
前插法插入新的节点
单链表：
template <class T>
LinkList<T> FrontInsert(LinkList<T> head, T data, int i) //前插法，将值为data的新节点插入到链表第i个位置前面
{
if (i < 1 || i > GetLength(head)) //非法输入
return NULL;
LNode<T> *r = GetElem(head, i); //调用查找第i个节点函数
LNode<T> *newNode = new LNode<T>(r->data); //新节点
r->data = data;
newNode->next = r->next; //插入,本质为后插+交换第i个节点与新节点的值
r->next = newNode;
return head;
}
双链表：
template <class T>
LinkList<T> FrontInsert(LinkList<T> head, T data, int i) //前插法，将值为data的新节点插入到链表第i个位置前面
{
if (i < 1 || i > GetLength(head)) //非法输入
return NULL;
LNode<T> *r = GetElem(head, i); //调用查找第i个节点函数
LNode<T> *newNode = new LNode<T>(r->prior, data); //新节点
newNode->next = r; //更新后继
r->prior->next = newNode; //更新后继节点
r->prior = newNode; //更新前驱节点
return head;
}
此处两者有较大不同，单链表是通过数据交换实现，本质还是后插；而双链表可以实现直接前插。
删除指定节点
单链表：
template <class T>
LinkList<T> DeleteNode(LinkList<T> head, LNode<T> *p) //删除节点p
{
//将p的下一个节点的值赋给p，删除p的下一个元素
if (p->next != NULL)
{
p->data = p->next->data; //赋值
LNode<T> *q = p->next; //保存将删除节点的位置，防止无法释放空间
p->next = q->next; //删除
delete q;
}
else // p是尾节点，则只能从头查找并删除
{
LNode<T> *r = head->next; //移动指针
while (r->next != p) //查找p的前驱节点
{
r = r->next;
}
r->next = p->next; //删除
delete p;
}
}
双链表：
stemplate <class T>
LinkList<T> DeleteNode(LinkList<T> head, LNode<T> *p) //删除节点p
{
LNode<T> *f = p->prior; // p的前驱
LNode<T> *n = p->next; // p的后继
f->next = n; //删除
if(n!=NULL)
n->prior = f;
delete p;
return head;
}
代码地址
标签：学习笔记, c/c++