数据结构谈恋爱系列(二) 链表妹子"/>
和数据结构谈恋爱系列(二) 链表妹子
链表(List)
链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
↑↑↑↑↑↑上面这句话过于抽象
不如来看看下图的妹子↓↓↓↓↓↓
为什么是这位妹子呢?单纯是因为有火车轨道
链表就相当于一辆火车↓↓↓↓↓↓↓(当然我指的是线性表)
特点:
线性表的链式存储表示的特点是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)
每个元素存储:
1.本身的信息 (数据域)
2.指示器直接后继的存储位置 (指针域)
类比以上的火车 第一节车厢不仅要存储他的信息(乘客人数,车厢号。。。。)还要存储第二节车厢的位置信息
第二节车厢也要存储第三节车厢的信息。
优点:在插入时 时间复杂度低
缺点:在查找时必须从头开始找 ,十分麻烦
部分链表:
1.单链表(线性表):
a.集合中必存在唯一的一个“第一元素”。
b.集合中必存在唯一的一个 “最后元素” 。
c.除最后一个元素之外,均有唯一的后继(后件)。
d.除第一个元素之外,均有唯一的前驱(前件)。
2.循环链表:
与单链表一样,是一种链式的存储结构,所不同的是,循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点,从而构成一个环形的链。
1、在建立一个循环链表时,必须使其最后一个结点的指针指向表头结点,而不是象单链表那样置为NULL。此种情况还使用于在最后一个结点后插入一个新的结点。
2、在判断是否到表尾时,是判断该结点链域的值是否是表头结点,当链域值等于表头指针时,说明已到表尾。而非象单链表那样判断链域值是否为NULL。
3.双向链表:
在双向链表中,结点除含有数据域外,还有两个链域,一个存储直接后继结点地址,一般称之为右链域;一个存储直接前驱结点地址,一般称之为左链域
所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。
更多推荐
和数据结构谈恋爱系列(二) 链表妹子
发布评论