请选择 进入手机版 | 继续访问电脑版
 找回密码
 立即注册
双向链表的设计

双向链表的主要优点是对于任意给的结点,都可以很轻易的获取其前结点和后结点,其主要缺点是每个结点需要保存next和prev两个属性,因此需要更多的空间开销,同时结点的插入与删除操作也将更加耗时,因为需要操作更多的指向操作。

  • 双向链表单个节点结构:
WddiR28nnw5TIawA.jpg


双向链表节点

  • 双向链表的数据结构:
eYT4zp7Yst4z84sx.jpg


双向链表数据结构
双向链表的插入操作


  • 插入数据到链表尾部
N0gfRR1r8GMT1HFz.jpg


链表尾部插入数据

  • 插入数据到链表中间
Ca9jAnNwPw82EjhB.jpg


链表中部插入数据
双向列表删除操作


  • 删除链表尾部数据
WEz90PS56NEeeC9X.jpg


删除尾部数据

  • 删除链表中间数据
Wh269Hvq3zHnVCQd.jpg


删除中间数据
循环双向列表设计

循环双向链表是在普通双向链表基础上进化得到的。在普通的双向链表中,如果我们要获取最后一个节点的时候,我们只能从头开始遍历,一直遍历到最后才能够拿到最后一个节点的数据。而循环双向链表会把header的prev指向最后一个节点,最后一个节点next指向header。其数据结构如图所示:
buYl8u3Q7QyEFzyJ.jpg


循环双向链表
循环链表的添加、删除和普通的双向链表是一模一样的,这里就不再赘述。
分享至 : QQ空间
收藏

0 个回复

    您需要登录后才可以回帖 登录 | 立即注册