文章中没有相关细节的代码哦，主要是总结知识点。有具体实现需求的，可以咕咕咕哥一波，一大堆。。
线性表定义
零个或者多个数据元素的序列。
有且只有一个直接前驱元素，而且有且只有一个后驱元素。
线性表储存结构
-
顺序储存结构
线性表的顺序存储结构，指的是用一段地址连续和存储单元依次存储线性表的数据元素。
而且为了构建线性表，要在内存中找一块空地，这块空地的,而且数组的长度就是这个的最大容量。数组的长度和线性表的区别：
数据长度是存放线性表的存储空间的长度。
线性表的长度是线性表中数据元素的个数长度。
由此可以得出线性表的长度一定小于或者等会数组的长度。地址计算方法：
LOC(ai+1) = LOC(ai)+c获取元素操作，插入操作：
两个操作在次存储结构中都会引起后续表中的改变，导致时间复杂度都在O（n），但是查找操作可以根据数组的地址查找，所以时间复杂度为O（0）,这就代表了才类型的特点和优缺点。
优点：
- 无需为表示表中之间的逻辑而增加额外的存储空间。
- 可以快速的存取表中的任一位置的元素
缺点：
- 插入和删除操作需要移动大量的元素
- 当线性表变化较大时候，难以确定其中存储空间的容量势必会内存会浪费
- 造成空间的碎片
线性表链式储存结构
n个结点（node）链组成一个链表，即线性链表的链式储存。
节点：
节点包含
数据域：
把储存数据元素的信息称作数据域
指针域：
把后继位置的信息（即后继位置的地址）域称为指针域，每个节点包含一个指针称为单链表。
头指针：
链表中第一个节点的储存位置叫做头指针，最后一个节点指针为null。
它具体标示作用，且无论链表为不为空，头指针都不为空，而且他是必要因素在链表中。
头结点： 第一个节点前附设一个节点叫头结点，目的是为了跟方便为进行操作的统一，有了它对第一个节点的删除和插入与其他节点操作就相同了
单链表的读取：
在顺序存储结构，可以通过存储位置轻易找到，但在单链表中因为节点的位置只有前继节点能知道，所以比起顺序储存结构，会相对麻烦很多
单链表的整表的创建：
头插法和尾插法了解一下！！
单链表的删除和插入节点：
如果已知节点的位置，那么单链表的插入和删除操作时间复杂度就为O（1）！！，所以插入和删除操作越频繁，单链表的效率优势就会愈来愈明显
还有个重点：
单链表的节点插入或者删除是动态添加或者删除的，所以不会造成存储空间的浪费，同时大小也不会收到到限制。
单链表结构和顺序储存结构优缺点比对
这里分三围进行比对
存储分配方式：
- 顺序存储结构用一段连续的存储单元依次储存线性表的数据元素
- 单链表采用的是链表存储结构，即存储位置是随机的或者说不是连续的
时间性能 - 查找：顺序存储为O（1），单链表为O（n）
- 插入和和删除：顺序需要移动后续表位置，时间复杂度O（n），单链表得到某一位指针后时间复杂度为O(1)
空间性能 - 顺序存储结构需要预分配空间
- 单链表不需要预分配，只要有就可以分配，而且时间不收限制。
循环链表
讲单链表终端节点的指正端由空指针改为指向头结点，使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，检测循环链表。
合并循环链表：
让一号的单链表的末节点指针指向另二号节点的头结点，相同的二号单链表的尾节点指向一号的头结点，这样就形成了循环
双向链表
在单链表的每个节点中，再设置一个前驱元素结点的指针域。
当双向链表是空链表时，即前驱后继指针域都会指向头结点自身。
当不为空链表的时候头结点前驱指针会指向末节点，相同的末节点的后继指针会指向头结点。
因为可以顺反遍历，那么就得付出一丢丢代价：插入和删除时候就得更改两个指针啦。。
插入的注意，先赋值再改指针（数据结构中每个都得这样，新节点先建立关系在修改原节点的指针）
优缺点分析:
优点：反向遍历的增加可以提高算法的时间性能，
缺点：因为每个节点增加了指针域导致空间会展的多一些，这种思维被称作时间换空间。
网友评论