链表

链表由节点组成

  • 节点的属性:
    1. 关键字key
    2. 由节点对象代替的指针prev,next
      单向节点只有next指针
  • 链表由表头(一个节点对象)和指针构成

链表的形式

  • 单链接或双链接:
    单链接只有next指针,双链接指针齐全
  • 循环或非循环:
    L.head.prev = L.tail
    L.tail.next = L.head
  • 已排序或未排序

链表相关操作

  • 链表的搜索:
    从n = L.head开始,遍历n.next,直到找到与给定参数相同的key或者n = null为止。
  • 链表的插入:
    1. 如果链表为空,则直接将x作为表头:
      L.head = x;
    2. 将给定关键字的新节点x链接到表头
      x.next = L.head;
      L.head.prev = x;
      L.head = x;
      x.prev = null;
  • 链表的删除:
    1. 如果当前节点为表头:
      L.head = x.next;
      x.next.prev = nil;
    2. 如果当前节点为表尾:
      x.prev.next = nil;
    3. 当前节点前后都有节点:
      x.prev.next = x.next;
      x.next.prev = x.prev;

有哨兵的双向链表

L.head.prev = L.nil;
L.tail.next = L.nil;
L.nil.next = L.head;
L.nil.prev = L.tail;

  • 链表的搜索:
    从n = L.nil.next开始遍历整个链表,知道key等于给定参数或n = L.nil;
  • 链表的插入:
    插入到L.nil和L.nil.next中间
  • 链表的删除:
    x.prev.next = x.next;
    x.next.prev = x.prev;
  • 对单一链表,增加哨兵会提高效率
  • 对多个短链表,增加哨兵可能会浪费存储空间
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • //leetcode中还有花样链表题,这里几个例子,冰山一角 求单链表中结点的个数----时间复杂度O(n)这是最...
    暗黑破坏球嘿哈阅读 1,731评论 0赞 6
  • 本文内容:1、 什么是链表?2、 链表共分几类?3、 链表的 C 实现! 总表:《数据结构?》 工程代码 Gith...
    半纸渊阅读 40,276评论 0赞 54
  • 链表 概念 说到链表,coder们都不会陌生,在日常开发中或多或少都会用到它。它是链式存储的线性表,简称链表。链表...
    扈扈哈嘿阅读 2,175评论 0赞 5
  • redis使用两种数据结构保存链表,分别是ziplist与linkedlist,内存占用及常用操作效率各不相同。本...
    但莫阅读 1,260评论 0赞 1
  • 关键字:pip使用,虚拟环境,beautiful soup 在前面几篇博客我们记录了python的一些简单...
    谜00016阅读 579评论 2赞 1

友情链接更多精彩内容