一、顺序表

二.链表

目录

 一、顺序表

二.链表

---

---

一.顺序表

1.基本概念：是指用一组地址连续的存储单元依次存储数据元素的线性结构。我们常见的顺序表有数组。

2.操作方面：可以基本实现数据的增删改查，因为有下标索引，所以查询工作很方便，效率很高。但是在增加元素和删除就不是很方便了，因为元素要整体移位置，会比较麻烦，下面的链表可以解决这个问题。

3.时间复杂度的对比：如图所示

二.链表

1.链表和顺序表有所区别，储存地址不一定是连续的。当查询操作多的时候一般用顺序表，删除和插入多的一般用链表，选择合适的数据结构很重要。

2.单链表有head头结点，后继结点，尾结点指向为null。用指针进行遍历时，While（p.next!=null）即可。

图示：

3.head头结点的数据域可以不存储任何信息，也可以存储如线性表的长度等类的附加信息。头结点的指针域指向首元结点。并且头结点不计入链表的长度。

4.注意：单链表只有后继结点，可以向后移动，不可以回头。当结点在向后移动时，要保存p结点往后的结点，可以设置一个临时q=p.next来保存p的后继结点。

5.在插入时，注意顺序，如：要求在head和head.next之间插入一个s，代码如下：

s.next=head.next;   

head.next=s;(注：两者顺序不能调换)

6.删除时，单链表与顺序表比较很是方便，时间复杂度是O（1），只需将要删除的结点的后继结点改为待删除结点的后继结点即可。

在java中删除的结点会自动回收，在c语言中要自己释放删除的结点：free(p)。

实现代码如下:

                 s.next=p.next; (s为待删除结点p的前一个结点)

7.头插法：倒序排列——可以理解为将其插在head和head.next之间。实现代码：将数组元素值传递给s结点，for循环遍历

                  s.next=L.head.next;

                   L.head.next=s;

图示：

注：在实际运用中一般要用一个q来临时保存s的后继结点。

8.尾插法：正序排列——可以理解为一个个按顺序插在head后面。实现代码：将数组元素值传递给s结点，for循环遍历

将t设置为L.head

t.next=s;

            t=s；//将t向后移动

图示：

9.单链表例题：

（一）求中位数：

方法一，找到编号（n-1）/2+1位置的结点即可。其中可以用Math.cell（n/2f）向上取整代替，其中f是为了使其里面变成double类型。

方法二,快慢指针法，快指针一次移动两个结点，慢结点一次移动一个结点。所有当快指针遍历完时，慢指针只走了一般，即所指向的位置就是中位数。

（二）统计最大值个数：

方法一，直观方法，先找最大值，再遍历寻找等于最大值的数，统计个数，需要用到两次while循环。

方法二，设置p指向首结点，初始化最大值为首结点的值，p=p.next不停的向后移动。

思想：当遍历未结束时，将后继的结点和max比较，比它大设置新的max值，个数记为1。再次遇到相同的值，个数再加1……知道遇到比max大的后继结点，在设置新的max值，重置个数为1，依次进行直到结束。一次while循环即可。

（三）二路归并有序表A和B合并为新的升序表C，空间复杂度为O（1），只能结点重组来建立单链表C。

（四）将A和B中的相同元素放入单链表C，不改变A和B，只能通过复制来建立单链表C。两者注意区分。

图示：

10.双链表：可以理解为高级一些的链表，结点由前端指针域，数据域和后端指针域三要素组成。每一个结点有两个指向，其中头结点的前端指向null，尾结点后端指向null。

图示如下：

11.双链表和单链表的对比：双链表更加高效，可以实现从前往后，也可以从后往前遍历；而单链表则是比较单一，只能从前往后，只有一个指针，无法找前驱结点。

在删除一个结点时，双链表不需要找到前驱结点，只需要找到删除的结点就可以实现删除操作。  

12.循环链表：顾名思义，就是是表中最后一个结点的指针域指向头结点(首节点和末节点被连接在一起)，整个链表形成一个环。

                                                            图示：

13.循环链表和单链表区别：单链表的尾结点指针指向空地址，表示这就是最后的结点了。循环链表的尾结点指针是指向链表的头结点。

14.循环链表的运用：适用于存储有循环特点的数据，比如约瑟夫问题：由一群元素构成的环形链表，首先由某个元素开始报数，报到K时的那个元素需要出圈，然后又由下一个元素开始报数，直到全部的元素出圈时才结束。