线性表

线性表是一种简单的数据结构，数据元素之间存在着一对一的关系。其存储方法通常采用顺序存储和链式存储

线性表的顺序存储可以采用结构体的形式，它含有两个域。一个整型的长度域，用以存放表中的元素的个数；另一个数组域，其类型可以根据需要而定。顺序存储的优点是可以随机存取，且存储空间比较节约，而缺点就是表的扩充比较困难，插入和删除操作者都需要大量的元素移动。

线性表的链式存储是通过节点之间的连接得到的。根据连接方式的不同可以分为：单向链表、双向链表和循环链表等。

单向链表由一个数据域和一个指针域组成，数据域用来存放结点的信息；指针域用来指出下一个结点的地址。在单向链表中，只能从某个结点出发找它的后继结点。单向链表的最大优点是表的扩充容易、插入和删除操作方便，而缺点就是存储空间比较浪费。

双向链表是由一个数据域和两个指针域组成的，他的优点是既能查找结点的前驱，也能找到结点的后继。

循环列表使最后一个结点的指针指向头借点的地址，形成一个首尾相连的环。利用循环链表将使某些运算比单向链表简单。

栈

栈是一种运算限制的线性表，它只允许在栈顶进行插入和删除操作

栈的逻辑结构和线性表相同，数据元素之间存在一对一关系，其主要特点是“先进后出”

栈的存储结构有顺序栈和链表之分

主要应用有子程序调用，递归调用

队列

队列是一种操作受限制的线性表，一般队列只允许在队尾进行插入操作，在队头进行删除操作。

队列的逻辑结构和线性表也相同，数据元素之间存在一对一的关系，其主要特点是“先进先出”

Java Collection Mapping

顺序线性表 – ArrayList
链式线性表 – LinkedList
栈 – Stack / LinkedList
队列 – Queue / LinkedList