数据结构学习笔记（3）—— 线性表（顺序存储结构与链式存储结构）
本文主要参考书籍为《大话数据结构》第三章，线性表。
目录
一、定义
元素间是有顺序的；每一个元素都只有一个前驱或后继（第一个和最后一个除外）。
n表示线性表的长度。当n=0时称为空表。
二、线性表的抽象数据类型定义
三、线性表的顺序存储结构
三个最重要的属性是：
线性表的长度小于等于数组的长度。
1）顺序存储结构的插入操作
2）顺序存储结构的删除结构
3）插入、删除和存取数据的时间复杂度
4）顺序存储结构的优缺点
四、线性表的链式存储结构
1、单链表的基本原理和操作
顺序存储结构最大缺点的原因：
链式存储结构的思路：
以前在顺序结构中，每个数据元素只需要存数据元素苏信息就可以了。现在链式结构中，除了要存数据元素信息外，还要存储它的后继元素的存储地址。
有时我们会在链表的第一个节点前加头结点，头结点的数据域可以不存储任何信息，也可以存储如下图所示的附加信息：
其与头指针的区别如下：
空表的头节点的指针域为空：
（1）链表的读取
在单链表中，第i个元素到底在哪里，我们没有办法一上来就知道，必须从头开始找：
（2）链表的插入
这两句的顺序一定不能错：
（3）链表的删除
（4）总结一下链表的插入和删除
都是由这两步组成的：
2、单链表的整表创建整表创建思路:1）头插法2）尾插法
3、单链表的整表删除
4、单链表与顺序存储结构对比
5、静态链表
早期的编程语言没有指针，如何实现单链表？
（cur为cursor游标的简写）
举个例子：
1）静态列表的插入操作
静态列表不存在动态列表的结点申请(malloc函数)和释放(free函数)。
2）静态列表的删除操作
3）静态列表的优缺点
6、循环链表
空循环链表的结构：
非空循环链表的结构：
7、双向链表
双向链表是在单链表的每个结点中，再设置有一个指向其前驱结点的指针域（所以双向链表有两个 指针域）。
双向链表也可以是循环表，空表如下图：
非空表如下图：