近期为了面试做准备,复习了下关于链表的一些知识点,做个记录~

首先何谓链表? 
链式存储的线性表,简称链表。链表由多个链表元素组成,这些元素称为节点。结点之间通过逻辑连接,形成链式存储结构。存储结点的内存单元,可以是连续的也可以是不连续的。逻辑连接与物理存储次序没有关系。

链表分为两个域: 
值域:用于存放结点的值 
链域:用于存放下一个结点的地址或位置

从链表分类来讲,可以按以下两种情况进行分类:

1、从内存角度出发:链表可分为静态链表和动态链表

2、从链表存储方式的角度出发:可以分为单链表、双链表和循环链表

静态链表: 
把线性表的元素存放在数组中,这些元素可能在物理上是连续存放的,也有可能不是连续的,它们之间通过逻辑关系来连接,数组单位存放链表结点,结点的链域指向下一个元素的位置,即下一个元素所在的数组单元的下标。显然静态链表需要数组来实现。 
引出的问题:数组的长度定义的问题,无法预支。

动态链表:(实际当中用的最多) 
改善了静态链表的缺点。它动态的为节点分配存储单元。当有节点插入时,系统动态的为结点分配空间。在结点删除时,应该及时释放相应的存储单元,以防止内存泄露。

单链表: 
单链表是一种顺序存储的结构。 
有一个头结点,没有值域,只有连域,专门存放第一个结点的地址。 
有一个尾结点,有值域,也有链域,链域值始终为NULL。 
所以,在单链表中为找第i个结点或数据元素,必须先找到第i - 1 结点或数据元素,而且必须知道头结点,否者整个链表无法访问。

循环链表: 
循环链表,类似于单链表,也是一种链式存储结构,循环链表由单链表演化过来。单链表的最后一个结点的链域指向NULL,而循环链表的建立,不要专门的头结点,让最后一个结点的链域指向链表结点。 
(循环链表与单链表的区别) 
区别一、链表的建立。单链表需要创建一个头结点,专门存放第一个结点的地址。单链表的链域指向NULL。而循环链表的建立,不要专门的头结点,让最后一个结点的链域指向链表的头结点。 
区别二、链表表尾的判断。单链表判断结点是否为表尾结点,只需判断结点的链域值是否是NULL。如果是,则为尾结点;否则不是。而循环链表盘判断是否为尾结点,则是判断该节点的链域是不是指向链表的头结点。

双链表: 
双链表也是基于单链表的,单链表是单向的,有一个头结点,一个尾结点,要访问任何结点,都必须知道头结点,不能逆着进行。而双链表则是添加了一个链域。通过两个链域,分别指向结点的前结点和后结点。这样的话,可以通过双链表的任何结点,访问到它的前结点和后结点。但是双链表还是不够灵活,在实际编程中比较常用的是循环双链表。但循环双链表使用较为麻烦。
---------------------
作者:渲染笔墨情
来源:CSDN
原文:https://blog.csdn.net/qq_37675827/article/details/78537744
版权声明:本文为博主原创文章,转载请附上博文链接!

 

内容来源于网络如有侵权请私信删除
你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!