[数据结构]线性表一 - pod4g/tool GitHub Wiki

1. 线性表的抽象数据类型

ADT 线性表(List)
Data
  线性表的数据对象集合为{a1, a2, ..., an}，每个元素的类型均为DataType，其中，除第一个元素a1外，剩下的所有元素有且仅有一个直接前驱，除了最后一个元素an外，剩下的所有元素有且仅有一个直接后继元素。数据元素之间的关系是一对一的关系。
Operation
  InitList(length) 初始化一个长度为length的线性表
  IsEmpty(L) 线性表L是否为空？为空返回true，否则返回false
  ClearList(L) 清空线性表L
  InsertList(L, elem, i) 把elem数据元素插入到线性表L的i位置
  DeleteElem(L, i) 把线性表L中的第i位元素删除
  LocateElem(L, elem) 返回线性表L中elem的位置，不存在返回-1
  GetElem(L, i) 返回线性表第i个元素
  ListLength(L) 返回线性表L的长度
endADT

2. 线性表的顺序存储结构

顺序存储结构，我们也可以称之为顺序表，使用数组实现顺序表

顺序表访问和修改的时间复杂度是O(1)，插入和删除的复杂度是O(n)

3. 线性表的链式存储结构

节点由两部分构成：

数据域
指针域

3.1 头指针

链表中第一个节点的内存地址，称之为头指针

3.2 头结点

单链表的第一个节点前附设一个结点，称之为头结点

头结点的数据域可以不存储任何信息，也可以存储如线性表的长度等附加信息，头结点的指针域存储指向第一个节点的指针

3.3 头指针和头结点的异同

头指针是指链表指向第一个节点的指针，若链表有头结点，则是指向头结点的指针
头指针具有表示作用，所以常用头指针冠以链表的名字
无论链表是否为空，头指针均不为空。头指针是链表的必要元素
头结点是为了操作的统一和方便而设立的，放在第一元素的节点之前，其数据域一般无意义（也可以存放链表长度）
有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其他结点的操作就统一了
头结点不是链表的必要元素

理解：头指针要么指向头结点，如果头结点不存在（因为不是必要元素），就指向第一个结点

单链表的读取、更新、删除、插入时间复杂度都是O(N)，因为我们进行任何操作以前，都要从头结点遍历整个链表，那么相对于顺序表，它的优势究竟是什么？如果每次都插入1个元素，优势不明显，如果插入10个呢？对于插入或删除数据约频繁的操作，单链表的优势就越明显