第三章 线性表

线性表（List）：零个或多个数据元素的有限序列。
线性表强调是有限的
随机存取结构：存取时间性能是O(1)
线性表-顺序存储结构
存、读数据时，复杂度O(1)
插入、删除数据时，复杂度O(n)
线性表缺点：插入和删除操作时，需要移动大量元素
线性表-链式存储结构
数据域+指针域=节点
单链表
头指针
尾指针指向NULL或^
头指针和头结点的异同
头指针是链表必需的
头节点不是链表必需的
对于插入或是删除操作，单链表的效率优势很明显
单链表的整表创建
头插法
尾插法
单链表的整表删除
单链表和顺序存储结构的优缺点
P70
静态链表
没有指针和引用的语言，如何实现单链表？ —>用数组来实现

第一个元素的cur存放备用链表（即后面的空闲空间）第一个节点下标
数组最后一个元素的cur用来存放头结点（第一个插入元素的下标）
静态链表优缺点
1、插入和删除时，只需要修改游标，不需要移动元素
2、给没有指针的高级语言设计了一种实现单链表能力的方法
3、失去了顺序存储结构随机存取的良好特性
循环链表
单循环链表
用头指针来表示循环链表
用尾指针来表示循环链表rear
两个循环链表合并成一个链表，用尾指针很简单
双向链表
两个指针：直接前驱指针，直接后继指针
prior指针
next指针