数据结构与算法

数据结构与算法知识详解
帅旋
关注
充电
IT宅站长,技术博主,架构师,全网id:arthinking。

链表数据结构

发布于 2020-04-28 | 更新于 2024-05-16

4、链表

4.1、使用场景

  • 在许多列表,队列和堆栈实现中使用;
  • 非常适合创建循环列表;
  • 可以轻松地对诸如火车等现实世界的物体进行建模;
  • 某些特定的Hashtable实现用于处理散列冲突;
  • 用于图的邻接表的实现中。

4.2、术语

Head:链表中的第一个节点;

Tail:链表中的最后一个节点;

Pointer:指向下一个节点;

Node:一个对象,包含数据和Pointer。

image-20200425181834771

4.3、实现思路

这里使用双向链表作为例子进行说明。

4.3.1、插入节点

往第三个节点插入:x

从链表头遍历,直到第三个节点,然后执行如下插入操作:

遍历到节点位置,把新节点指向前后继节点:

image-20200425183248297

后继节点回溯连接到新节点,并移除旧的回溯关系:

image-20200425183730055

前继节点遍历连接到新节点,并移除旧的遍历关系:

image-20200425183845347

完成:

image-20200425183952287

注意指针处理顺序,避免在添加过程中导致遍历出现异常。

4.3.2、删除节点

删除c节点:

从链表头遍历,直到找到c节点,然后把c节点的前继节点连接到c的后继接节点:

image-20200425184600050

把c节点的后继节点连接到c的前继节点:

image-20200425184813983

移除多余指向关系以及c节点:

image-20200425184856386

完成:

image-20200425184952139

同样的,注意指针处理顺序,避免在添加过程中导致遍历出现异常。

4.4、时间复杂度

操作 单向链表 双向链表
查找 O(n) O(n)
Insert at head O(1) O(1)
中间追加 O(n) O(n)
尾部追加 O(1) O(1)
头部移除 O(1) O(1)
尾部移除 O(n) O(1)
中间移除 O(n) O(n)

4.5、编程实践

本文作者: 帅旋

本文链接: https://www.itzhai.com/columns/dsa/linked-list.html

版权声明: 版权归作者所有,未经许可不得转载,侵权必究!联系作者请加公众号。

×
IT宅

关注公众号及时获取网站内容更新。

请帅旋喝一杯咖啡

咖啡=电量,给帅旋充杯咖啡,他会满电写代码!

IT宅

关注公众号及时获取网站内容更新。