一.链表（灵活的内存动态管理，反结构：线性表顺序结构）

含义：一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

生成：链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。

结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

特点：链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

缺点：

链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

优点：

链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。

链表有很多种不同的类型：

1.单向链表：有一个缺点就是要找一个数，必须要从头开始找起，十分麻烦。

2.双向链表：

必须使其最后一个结点的指针指向表头结点，而不是象单链表那样置为NULL。

是判断该结点链域的值是否是表头结点，当链域值等于表头指针时，说明已到表尾。而非象单链表那样判断链域值是否为NULL。

循环链表：结点除含有数据域外，还有两个链域，一个存储直接后继结点地址，一般称之为右链域；一个存储直接前驱结点地址，一般称之为左链域。

优化：

插入操作处理顺序：中间节点的逻辑，后节点逻辑，前节点逻辑。按照这个顺序处理可以完成任何链表的插入操作。

删除操作的处理顺序：前节点逻辑，后节点逻辑，中间节点逻辑。

按照此顺序可以处理任何链表的删除操作。

如果不存在其中的某个节点略过即可。

二.线性表

分类：

一般线性表：就是我们通常所说的“线性表”，可以自由的删除或添加结点。

受限线性表：包括栈和队列和字符串，受限表示对结点的操作受限制。

特点：

均匀性：虽然不同数据表的数据元素可以是各种各样的，但对于同一线性表的各数据元素必定具有相同的数据类型和长度。

有序性：各数据元素在线性表中的位置只取决于它们的序号，数据元素之前的相对位置是线性的，即存在唯一的“第一个“和“最后一个”的数据元素，除了第一个和最后一个外，其它元素前面均只有一个数据元素(直接前驱)和后面均只有一个数据元素（直接后继）。

三.链表和线性表区别

1.数组是将元素在内存中连续存放，由于每个元素占用内存相同，可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一个元素，需要移动大量元素，在内存中空出一个元素的空间，然后将要增加的元素放在其中。同样的道理，如果想删除一个元素，同样需要移动大量元素去填掉被移动的元素。如果应用需要快速访问数据，很少或不插入和删除元素，就应该用数组。

2.链表恰好相反，链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针联系到一起。比如：上一个元素有个指针指到下一个元素，以此类推，直到最后一个元素。如果要访问链表中一个元素，需要从第一个元素开始，一直找到需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了，只要修改元素中的指针就可以了。如果应用需要经常插入和删除元素你就需要用链表数据结构了。

3.逻辑结构和内存存储角度来看

(1) 从逻辑结构角度来看

a, 数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费。

b,链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。（数组中插入、删除数据项时，需要移动其它数据项）

(2)从内存存储角度来看

a,(静态)数组从栈中分配空间, 对于程序员方便快速,但自由度小。

b, 链表从堆中分配空间, 自由度大但申请管理比较麻烦.