数据结构之单链表

单链表的读取

在单链表中,由于第 i 个元素到底在哪?没办法一开始就知道,必须得从头开始找。因此,对于单链表实现获取第 i 个元素的数据的操作 GetElem,在算法上,相对要麻烦一些。

思路:

  • 声明一个指针 p 指向链表第一个节点,初始化 j 从 1 开始;
  • 当 j < i 时,就遍历链表,让 p 的指针向后移动,不断指向下一节点,j 累加 1;
  • 若到链表末尾 p 为空,则说明第 i 个节点不存在;
  • 否则查找成功,返回节点 p 的数据。

单链表的插入

假设存储元素 e 的节点为 s,要实现节点 p、p->next 和 s 之间逻辑关系的变化,只需将节点 s 插入到节点 p、p->next 之间即可。

Y4Vmbj0AgX.png!large

根本用不着惊动其他节点,只需要让 s->next 和 p->next 的指针做一点改变即可。
让 p 的后继节点改成 s 的后继节点再把节点 s 变成 p 的后继节点。

s->next = p->next;
p->next = s;

kPqNhnnxbL.png!large

单链表的删除

设置存储元素 ai 的节点为 q,要实现将节点 q 删除单链表的操作,其实就是将它的前继节点的指针绕过,指向它的后继节点即可。

q = p->next;
p->next = q->next;
# 把 p 的后继节点改成 p 的后继的后继节点

aMI1V0bdf9.png!large

单链表第 i 个数据删除节点的算法思路

  1. 声明一指针 p 指向链表头结点,初始化 j 从 1 开始;
  2. 当 j< i 时,就遍历链表,让 p 的指针向后移动,不断指向下一个结点 j 累加 1;
  3. 若到链表末尾 p 为孔,则说明第 i 个结点不存在;
  4. 否则查找成功,将欲删除的结点 p->next 赋值给 q;
  5. 单链表的删除标准语句 p->next = q->next;
  6. 将 q 结点中的数据赋值给 e,作为返回;
  7. 释放 q 结点;
  8. 返回成功。

效率分析

单链表插入和删除算法,是由两部分组成:

  1. 遍历查找第 i 个节点
  2. 插入和删除节点。

时间复杂度都是 O(n);

从第 i 个位置,插入 10 个节点:
顺序存储结构:每一次插入都需要移动 n-1 个节点,每次都是 O(n)。
单链表:需要在第一次时,找到第 i 个位置的指针,通过赋值移动指针,时间复杂度都是 O(1)。

对于插入或删除数据越频繁的操作,单链表的效率优势就越是明显。

ai
本作品采用《CC 协议》,转载必须注明作者和本文链接
不要试图用百米冲刺的方法完成马拉松比赛。
本帖由 Galois 于 6个月前 解除加精
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!