双链表全部知识总结(初始化、插入、删除、遍历)

举报
高彬滔 发表于 2023/03/24 16:02:52 2023/03/24
【摘要】 1.双链表的初始化初始化双链表:首先通过malloc函数分配一个头结点空间,通过判断链表L是否为空来确定是否分配成功。将头结点的prior永远指向NULL,头结点的下一个结点暂时没有所以也指向NULLbool InitDLinkList(DLinkList &L){ L=(DNode *) malloc(sizeof(DNode)); if(L==NULL) ret...

1.双链表的初始化

初始化双链表:首先通过malloc函数分配一个头结点空间,通过判断链表L是否为空来确定是否分配成功。将头结点的prior永远指向NULL,头结点的下一个结点暂时没有所以也指向NULL

bool InitDLinkList(DLinkList &L){
    L=(DNode *) malloc(sizeof(DNode));
    if(L==NULL)
        return false;
    L->prior=NULL;
    L->next=NULL;
    retrun true;
}

1.1 判断双链表是否为空

要想判断双链表是否为空,即判断头结点的next的指针是否为空

bool Empty(DLinkList L){
    if(L->next==NULL)
        return false;
    else 
        return true;
}

2.双链表的插入

实现需求:在p结点之后插入s结点

2.1 p结点不是最后一个结点

image.png 分析步骤:

  1. 首先会把s结点指向p->next结点
  2. p的后继结点的前向指针指向s
  3. s结点的前向指针指向p结点
  4. p的后向指针指向s结点

image.png

代码实现:

bool InsertNextDNode(DNode *p, DNode *s){
    s->nest=p->next;
    p->next->prior=s;
    s->prior=p;
    p->next=s;
}

2.2 p结点是最后一个结点

image.png 当p结点是最后一个结点的时候,显然这时候p->next=NULL,所以就需要对 p->next->prior=s改良,判断p结点是否有后续结点,从而判断是不是需要修改p下一个结点的前向指针

if(p==NULL || S==NULL)
    return false;
s->next=p->next;
if(p->next!=NULL)
    p->next->prior=s;

3.双链表的删除

3.1 删除p的后继节点

分析:和插入的思考方式一样,同样我们需要考虑p的后继结点是否为NULL。

  1. 找到p的后继结点
  2. 判断p的后继结点是否为NULL,为NULL即p没有后继
  3. 将p的下一个结点指向q的下一个结点
  4. 判断q结点是否为最后一个结点
  5. free(q)

代码实现:

bool DeleteNextDNode(DNode *p){
    if(p==NULL)
        return false;
    DNode *q=p->next;
    if(q==NULL)
        return false;
    p->next=q->next;
    if(q->next!=NULL)
        q->next->prior=q;
    free(q);
    return true;
}

3.2 销毁链表

实现步骤:

  1. 循环释放各个数据结点
  2. 同时释放头结点
  3. 头指针指向空
void DestoryList(DLinkList &L){
    while(L->nex!=NULL)
        DeleteNextDNode(L);
    free(L);
    L=NULL;
}

4.双链表的遍历

对结点p做相应的处理,如打印

4.1 后向遍历

while(p!=NULL){
    p=p->next;
}

4.2 前向遍历

while(p!=NULL){
    p=p->prior;
}

4.3 前向遍历(跳过头结点)

while(p->prior=NULL){
    p=p->prior;
}

5.总结

  1. 修改指针的时候需要注意顺序
  2. 双链表可以很方便的找到给定结点的前驱节点,对前驱节点执行后插操作,这样就可以实现按位序插入的前插操作。
  3. 双链表不具备随机存取特性,查找操作只能通过顺序遍历实现
【版权声明】本文为华为云社区用户原创内容,未经允许不得转载,如需转载请自行联系原作者进行授权。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。