数据结构和算法线性表(四)

线性表

线性表是最基本、最简单、也是最常用的一种数据结构。一个线性表是n个具有相同特性的数据元素的有限序列。

线性表的分类：

线性表中数据存储的方式可以是顺序存储或链式存储，
按照数据的存储方式不同，可以将线性表分为顺序表和链表。

顺序表

顺序表是在计算机内存中以数组的形式保存的线性表，是指用一组地址连续的存储单元，依次存储线性表中的各个元素，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。

顺序表的时间复杂度

get(i):不论数据元素量N有多大，只需要一次get[i]就可以获取到对应的元素，所以时间复杂度为O(1);
insert(int i,T t):每一次插入，都需要把i位置后面的元素移动一次，随着元素数量N的增大，移动的元素也越多，时间复杂为O(n);
remove(int i):每一次删除，都需要把i位置后面的元素移动一次，随着数据量N的增大,移动的元素也越多，时间复杂度为O(n);

缺点:
由于顺序表的底层由数组实现，数组的长度是固定的，所以在操作的过程中涉及到了容器扩容操作。这样会导致顺序表在使用过程中的时间复杂度不是线性的，在某些需要扩容的结点处，耗时会突增，尤其是元素越多，这个问题越明显

链表

链表是一种物理存储单元上非连续、非顺序的存储结构，其物理结构不能只管的表示数据元素的逻辑顺序，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列的结点（链表中的每一个元素称为结点）组成，结点可以在运行时动态生成。

1.单向链表

单向链表是链表的一种，它由多个结点组成，每个结点都由一个数据域和一个指针域组成，数据域用来存储数据，指针域用来指向其后继结点。
链表的头结点的数据域不存储数据，指针域指向第一个真正存储数据的结点。

2.双向链表

双向链表也叫双向表，是链表的一种，它由多个结点组成，每个结点都由一个数据域和两个指针域组成，数据域用来存储数据，其中一个指针域用来指向其后继结点，另一个指针域用来指向前驱结点。
链表的头结点的数据域不存储数据，指向前驱结点的指针域值为null，指向后继结点的指针域指向第一个真正存储数据的结点。

链表的复杂度分析

get(int i):查询都需要从链表的头部开始，依次向后查找，随着数据元素N的增多，比较的元素越多，时间复杂度为O(n)
insert(int i,T t):插入需要先找到i位置的前一个元素，然后完成插入操作，随着数据元素N的增多，查找的元素越多，时间复杂度为O(n);
remove(int i):移除需要先找到i位置的前一个元素，然后完成插入操作，随着数据元素N的增多，查找的元素越多，时间复杂度为O(n)

两者对比

相比较顺序表，链表插入和删除的时间复杂度虽然一样，但仍然有很大的优势，因为链表的物理地址是不连续的，
它不需要预先指定存储空间大小，或者在存储过程中涉及到扩容等操作,同时它并没有涉及的元素的交换。
相比较顺序表，链表的查询操作性能会比较低。
如果我们的程序中查询操作比较多，建议使用顺序表，增删操作比较多，建议使用链表。

算法题

1,链表反转（递归）
2,链表有环（快慢指针）
3,链表入口（快慢指针）