双链表与单链表不同的是:双链表是双向的,而单链表是单向的
1.定义
此时prior表示前结点,next表示后结点
typedef struct node
{
int data;
struct node* prior,*next;
}node,*list;
2.初始化
bool inite(list& l)
{
l = (node*)malloc(sizeof(node));
if (l == NULL)
return false;
l->prior = NULL;
l->next = NULL;
return true;
}
3.判断是否为空
bool empty(list l)
{
if (l->next == NULL)
return true;
else
return false;
}
4.插入(在p后面插入s)
注意是先e与后面的y相连,再e与x相连(顺序不能反)
//在p后面插入s
bool insert(node*p,node*s)
{
if (p == nullptr || s == nullptr)
return false;
s->next = p->next;
if (p->next != nullptr) //如果p不是最后一个结点
p->next->prior = s;
s->prior = p;
p->next = s;
}
5.删除(删除p的后继结点q)
本质上就是把两个结点之间的两条线给断了
bool deletel(node* p)
{
if (p == nullptr)
return false;
node* q = p->next;
if (q == nullptr)
return false; //p已经是最后一个结点了
p->next = q->next;
if (q->next != nullptr)
q->next->prior = p;
free(q);
return true;
}
6.删除整个链表
通过while循环不断地删除链表中的一个个点
void destroyall(list& l)
{
while (l->next != nullptr)
deletel(l);
free(l);
l = nullptr;
}
7.遍历
//后向遍历
void back(node* p)
{
while (p != nullptr)
p = p->next;
}
//前向遍历
void step(node* p)
{
while (p != nullptr)
p = p->prior;
}