一、线性表（定义）
线性表（Linear List）：是具有相同属性的数据元素的一个有限序列。它有顺序、链接、散列等存储结构，第一元素称为表头元素，最后一个元素称为表尾元素。在任意一对；相邻结点ai,ai+1(1<=i<=n),ai称为ai+1的直接前趋，ai+1称为ai的直接后继。
线性表的基本特征：若至少含有有一个结点，则除起始结点没有直接前趋外，其他结点有且仅有一个直接前趋；除终端结点没有直接后继外，其他结点有且仅有一个直接后继。
二、线性表的存储结构及基本运算
线性表根据其物理存储连续性状态及存储顺序可划分为顺序存储结构和链表存储结构。
顺序存储结构：把线性表中的所有元素按照其逻辑顺序依次存储到计算机存储器中从指定存储位置开始的一块连续的存储空间中。因此，逻辑结构中相邻的结点在存储结构中仍相邻。我们把顺序存储的线性表统称为顺序表，它的顺序存储结构是利用数组来实现的。
顺序存储下的线性表的基本运算：
（1）初始化线性表。即构造一个空表，它的长度（length）置0。
（2）清除线性表中的所有元素。
（3）获取线性表的长度。
（4）检查线性表是否为空。
（5）获取线性表中指定序号的元素。
（6）遍历线性表。
（7）从线性表查找具有给定值的元素。
（8）更新线性表中具有给定值的元素。
（9）向线性表的末尾添加一个元素。
（10）向线性表的表头插入一个元素。
（11）向线性表中满足条件的位置插入一个元素。
（12）从线性表中删除表头元素。
（13）从线性表中删除等于给定值的元素。
（14）对线性表进行排序。
链接存储结构：每一个存储单位（称之为存储结点，简称结点），由所存元素本身的信息和元素间逻辑关系信息组成，它可以任意顺序存储任意存储空间里。
也就是说，链接存储结构不要求元素依次存储在一块连续存储空间。
采用链接存储结构的线性表称之为链接表。在进行链接存储时，每个结点除包含元素本身外，若只设置一个引用指向它后面元素（后继），这样构成的链接表称之为线性单向链接表，简称单链表。
若设置两个引用分别指向它前面元素（前驱）和后面的元素（后继），这样构成的链表称之为线性双向链接表，简称双向链表。在单链表中，若尾结点的后继不是指向null，而是指头结点，称之为循环链表。
链表的基本运算：
（1）初始化，通过new建立一个空表。
（2）求表长size。线性表的表长等于单嘁链表所含表结点的个数。
（3）按序号查找。链表逻辑相邻的结点并不是存贮在物理相邻的单元中，所以不能像顺序表那样按序号i查找结点，在链表中只能从首结点出发，顺后继next逐个往下搜索，直到找到第i个结点为止。
故链表无法实现随机存取。
（4）定位，即按值查找，也就是从前往后的顺序，依次比较各结点数值域（item）与给定值X相等的结点的序号就是运算幽幽结果，若没有这样的结点运算结果为0。
（5）删除。除了remove(Object o)方法需要先定义，其它各重载remove()方法直接将待删除结点的item、prev、next置为null，然后修改其前驱的后继，后继的前驱，必要是修改first、last。
（6）插入。删除是unlink，插入是link，基本上删除的反向操作。
链表的其他运算：
（1）建表，即将一个线性表中的数据元素依次输入并建立该线性表的单链表，也就是初始化运算和插入运算结合应用。
（2）消除重复结点，即删除数据域（item）的值相同的多余结点，只保留其中序号最小的一个。
顺序表和链表的比较：
1）顺序表无需额外空间存储各结点间关系系，较之链表占用存储空间小；
2）顺序表以位置（索引）直接存取各结点，存取方便；插入和删除时需要移动大量数据，效率低；链表在存取结点时需要从头结点或尾结点逐一打开后继或前驱，存取效率较低，而插入和删除时，只需要修改前驱和后继，不需要移动数据，效率较顺序表要高。
3）顺序表要求占用连续空间，只能预先分配（静态分配），分配空间太大，易造成资源浪费，太小，易造成数据溢出；链表没有这方面的要求，存储空间可以动态分配，任意修改空间大小。
4）顺序表只能存储线性表，而链表除此之外还可以存储非线性表。
三、栈
栈（Stack）又称堆栈：是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。允许进行插入和删除的一端称为栈项，另一端称为栈底。栈项的第一个元素称为栈顶元素，不含任何数据元素的栈称为空栈。
进栈（也称入栈），即向一个栈插入新元素，它是把该元素放到栈项元素的上面，使之成为新的栈顶元素。
出栈（或退栈），即从一个栈删除元素，它是把栈顶元素删除掉，使其下面相邻的元素成为新的栈顶元素。
栈的特征（栈的修改原则）：后进先出或先进后出（Last In First Out,简称LIFO）。
栈有两种实现方法：顺序实现和链接实现，这和线性表相似。栈的顺序存储结构称为顺序栈，通常由一个一维数组（Arrays）实现。栈的链式存储结构称为链栈，可以通过链表（LinkedList）实现。
栈的基本运算：
（1）初始化栈，构造一个空栈。
（2）清空栈
（3）检查栈是否为空
（4）读取栈顶元素
（5）向栈中插入元素
（6）从栈中删除元素
（7）检查栈是否已满（仅适用于顺序栈）
四、队列
队列（Queue）简称队，也是一种去处受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。
进行插入的一端称为队尾（rear）,进行删除的一端称为队首（front），向队列中插入新元素称为进队或入队，新元素进队后就成为新的队尾元素；从队列中删除元素称为离队或出队，元素离队后，其后继元素就成为队首元素。
由队列的定义可知队列的特征是：先进先出（First In First Out，简称FIFO）
队列的存储结构也有顺序存储结构和链接存储结构两种。
前者称为顺序队，它也可由数组实现；后者称为链队，它与线性表和栈一样也可由LinkedList实现。
队列的基本运算：
（1）初始化队列，构造一个空队列，队首、队尾置为null。
（2）队列清空
（3）检查队列是否为空
（4）读取队首元素
（5）向队列插入元素
（6）从队列中删除元素
（7）检查队列是否已满（仅限于顺序队）。
答：线性表相当于数组，在内存中连续存放数据； 线性链表中的数据存放位置是随机分配的，有指针连接前后数据。详情>>
答：这种心智与活动均集中于单一物体的现象，其实就是儿童内心深处的外在表现详情>>
答：普遍必然性：科学理论来自于实践，也必须回到实践，它必须能够解释其适用范围内的已知的所有事实详情>>
答：光信息技术 应用物理学 物理学 地理物理系国防 材料物理专业详情>>
