【2.3】链表

  • 通过指针把它的一串存储结点链接成一个链
  • 存储结点由两部分组成:
    • 数据域 + 指针域(后继地址)

一、分类

(根据链接方式和指针多寡)

二、单链表(singly linked list)

2.1 简单的单链表

  • 整个单链表: head
  • 第一个结点: head
  • 空表判断: head == NULL
  • 当前结点 a1:curr

2.2 带头结点的单链表

  • 整个单链表: head
  • 第一个结点: head->next,head ≠ NULL
  • 空表判断: head->next == NULL ;当前结点a1:fence->next (curr 隐含)

2.3 单链表的结点类型

2.4 单链表类定义

2.5 查找单链表中第 i 个结点

2.6 单链表的插入

2.7 单链表插入算法

2.8 单链表的删除

从链表中删除结点 x

  1. 用 p 指向元素 x 的结点的前驱结点
  2. 删除元素为 x 的结点
  3. 释放 x 占据的空间

2.9 单链表删除算法

2.10 单链表上运算的分析

对一个结点操作,必先找到它,即用一个指针指 向它

找单链表中任一结点,都必须从第一个点开始

p = head;
while (没有到达) p = p->next;

单链表的时间复杂度 𝑂(𝑛)

  • 定位:𝑂(𝑛)
  • 插入:𝑂(𝑛) +𝑂(1)
  • 删除:𝑂(𝑛) +𝑂(1)

三、双链表(double linked list)

为弥补单链表的不足,而产生双链表

  • 单链表的 next 字段仅仅指向后继结点,不能有效地找 到前驱, 反之亦然
  • 增加一个指向前驱的指针

3.1 双链表及其结点类型的说明

3.2 双链表插入过程(注意顺序)

3.3 删除过程

三、循环链表 (circularly linked list)

将单链表或者双链表的头尾结点链接起来,就是一个循 环链表

不增加额外存储花销,却给不少操作带来了方便

  • 从循环表中任一结点出发,都能访问到表中其他结点

四、讨论

4.1 链表的边界条件

  • 几个特殊点的处理
    • 头指针处理
    • 非循环链表尾结点的指针域保持为 NULL
    • 循环链表尾结点的指针回指头结点
  • 链表处理
    • 空链表的特殊处理
    • 插入或删除结点时指针勾链的顺序
    • 指针移动的正确性: 插入| 查找或遍历

4.2 思考

  • 带表头与不带表头的单链表?
  • 处理链表需要注意的问题?

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾蛟

个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn

Sam avatar
About Sam
专注生物信息 专注转化医学