linux链表参考2-阿里云开发者社区

linux链表参考2

2011-06-17 768

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 双链表 1、双向链表（Double Linked List）　双（向）链表中有两条方向不同的链，即每个结点中除next域存放后继结点地址外，还增加一个指向其直接前趋的指针域prior。

双链表

1、双向链表（Double Linked List）
　双（向）链表中有两条方向不同的链，即每个结点中除next域存放后继结点地址外，还增加一个指向其直接前趋的指针域prior。

注意：
    　①双链表由头指针head惟一确定的。
    　②带头结点的双链表的某些运算变得方便。
    　③将头结点和尾结点链接起来，为双（向）循环链表。

2、双向链表的结点结构和形式描述
①结点结构(见上图a)

②形式描述
    typedef struct dlistnode{
         DataType data;
         struct dlistnode *prior,*next;
      }DListNode;
    typedef DListNode *DLinkList;
    DLinkList head;

3、双向链表的前插和删除本结点操作
    　由于双链表的对称性，在双链表能能方便地完成各种插入、删除操作。
①双链表的前插操作

    void DInsertBefore(DListNode *p,DataType x)
      {//在带头结点的双链表中，将值为x的新结点插入*p之前，设p≠NULL
        DListNode *s=malloc(sizeof(DListNode));//①
        s->data=x;//②
        s->prior=p->prior;//③
        s->next=p;//④
        p->prior->next=s;//⑤
        p->prior=s;//⑥
       }
②双链表上删除结点*p自身的操作

    void DDeleteNode(DListNode *p)
      {//在带头结点的双链表中，删除结点*p，设*p为非终端结点
          p->prior->next=p->next;//①
          p->next->prior=p->prior;//②
          free(p);//③
      }
注意：
    　与单链表上的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。
    　上述两个算法的时间复杂度均为O(1)。

linux链表参考2

热门文章

最新文章

相关课程

相关电子书

相关实验场景

推荐镜像

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

linux链表参考2

热门文章

最新文章

相关课程

相关电子书

相关实验场景

推荐镜像