Linear List 线性表
[TOC]
基本概念
最常用，最简单的一种数据结构。
是由n（n>=0）个数据元素（结点）a[0]，a[1]，a[2]…，a[n-1]组成的有限序列。
一个数据元素可以由若干个数据项item组成。数据元素称为记录record，含有大量记录的线性表又称为文件file。
这种结构具有下列特点 ：
- 头元素：存在一个唯一的没有前驱的（头）数据元素；
- 尾元素：存在一个唯一的没有后继的（尾）数据元素；
- 除此之外，每一个数据元素均有一个直接前驱和一个直接后继数据元素。
一、两种表示结构 1.顺序表示 2.链式表示
1.1 顺序表示
使用数组来存储线性表。
随机访问效率高，插入删除可能需要移动大量的数据。
1.2 链式表示：链表 linked list
使用链表来存储线性表。
数据存储于节点Node的数据域中，节点之间使用指针或引用连接。
插入效率高，随机访问效率低。
1.2.1 线性链表(又名单链表、单向链表) singly linked list
特点是链表的方向是单向的
1.2.2 循环链表 circular linked list
单向链表的表尾指向表头，则整个链表形成一个环。
是否为空的判断条件是下一个节点是不是头指针。
1.2.2 双向链表 double linked list
单向链表只能顺着一个方向查找元素，指针域只指示后继节点。
因此 nextElement的时间复杂度是O(1),而PriorElement的时间复杂度是O(n)。
为了克服这种缺点，产生了双向链表double linked list.指针域有两个指针，分别指向前驱和后继节点。
1.2.3 其他链表：静态链表 Static Linked List
static_linked_list.png
用数组描述的链表，即称为静态链表
对于线性链表，也可用一维数组来进行描述。这种描述方法便于在没有指针类型的高级程序设计语言中使用链表结构。
仍旧有指针型链表的优点。
