专栏首页hui数据结构 - 链表

数据结构 - 链表

为什么需要链表

顺序表的构建需要预先知道数据大小来申请连续的存储空间,而在进行扩充(插入、删除)时又需要进行数据的搬迁,所以使用起来并不是很灵活。

链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。

链表的定义

链表(Linked list)是一种常见的基础数据结构,是一种 线性表的链式存储结构,存储地址空间不需要是连续的,而是在每一个节点(数据存储单元)里存放下一个节点的位置信息(即地址)。

链式存储有关的术语

  • 结点: 数据元素的存储映像。由数据域和地址域两部分组成。
  • 链表: n个结点由 指针链 组成一个链表。它是线性表的链式存储映像,称为线性表的链式存储结构。

单向链表

单向链表也叫单链表,是链表中最简单的一种形式,它的每个节点包含两个域,一个数据域和一个链接域(地址域)。这个链接指向链表中的下一个节点,而最后一个节点的链接域则指向一个空值(通常用 NULL^ 表示)。

  • 数据域 data 用来存放具体的数据。
  • 链接域 next 用来存放下一个节点的位置。
  • L 指向链表的头节点(首节点)的位置,从 L 出发能找到表中的任意节点。

单向循环链表

  • 数据域 data 用来存放具体的数据。
  • 地址域 next 用来存放下一个节点的位置,但最后一个结点的地址域要存储链表头结点的地址

优点: 从链表中的任一个结点出发均可找到链表中其他结点。

双向链表

一种更复杂的链表是 双向链表。每个结点有两个链接:一个指向前一个节点(当此节点为第一个节点时,指向空值),而另一个指向下一个节点(当此节点为最后一个节点时,指向空值)。

  • 数据域 data 用来存放具体的数据。
  • 地址域 pre 用来存放前一个节点的位置,地址域 next 用来存放下一个节点的位置。

优点: 方便找链表中的某个结点的前驱结点。

小扩展

头指针

  • 头指针是指链表指向第一个结点的指针,若链表有头结点,则是指向头结点的指针。
  • 头指针具有标识作用, 所以常用头指针冠以链表的名字。
  • 无论链表是否为空,头指针均不为空。头指针是链表的必要元素。

头结点

  • 头结点是为了操作的统一和方便而设立的,放在第一元素的结点之前,其数据域一般无意义(也可存放链表的长度)。
  • 有了头结点,对在第一元素结点前插入结点和删除第一结点,其操作与其它结点的操作就统一了。
  • 头结点不一定是链表必须要素。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 各数据结构的基本概念和术语汇总

    线性表中任一数据元素都可以 随机存取 ,所以 线性表的顺序存储结构是一种随机存取的存储结构。

    忆想不到的晖
  • 树和二叉树

    ​ 2. 当 n > 1 时,其余结点可分为 m(m > 0)个互不相交的有限集T1、T2,… ,Tm,其中每一个集合本身又是一颗树,并且称为根的 子树(Sub...

    忆想不到的晖
  • Python、PyGame游戏项目

    pyinstaller: 把项目打包成可执行文件(.exe),可在 Windows 环境下运行程序,无需 Python 环境。

    忆想不到的晖
  • AI_第一部分 数据结构与算法(5.链表上篇)

    第四阶段我们进行深度学习(AI),本部分(第一部分)主要是对底层的数据结构与算法部分进行详尽的讲解,通过本部分的学习主要达到以下两方面的效果:

    还是牛6504957
  • [leetcode链表系列]2 删除链表中的节点

    链表的一个节点是由数据域和指针域构成,指针域的地址值为下个元素的地址。那么我们需要插入或者删除一个元素怎么处理呢?

    我是程序员小贱
  • 不懂数据库索引的底层原理?那是因为你心里没点b树

      前几天下班回到家后正在处理一个白天没解决的bug,厕所突然传来对象的声音:   对象:xx,你有《时间简史》吗?   我:我去!妹子,你这啥癖好啊,我有时间...

    Java团长
  • 每日面试题推送及讲解-20190410

    第一题是对Hash表的考察,哈希表的特点:关键字和它在表中存储位置之间存在一种函数关系。这个函数我们称为为哈希函数。而键(key)经过hash函数得到的结果作为...

    每天学Java
  • 用js来实现那些数据结构14(树02-AVL树)

    zaking
  • 世界第一超算跑深度学习模型,2.76万块V100 GPU将分布式训练扩展到极致

    在这篇论文中,研究者介绍了同步分布式 DL 中一种新型通信策略,它主要由梯度缩减编排和梯度张量分组策略组成。这些新技术令计算和通信之间产生了最完美的重叠,并且完...

    机器之心
  • 判断链表是否有环

    判断一个单向链表是否有环。(指向表头结点的指针为head) 方法一: (1)用两个指针p1和p2分别指向表头结点,即p1=p2=head (2)p1和p2分别...

    顶级程序员

扫码关注云+社区

领取腾讯云代金券