一、顺序表

• 结点定义(静态)：

• 结点定义(动态)：

二、链表

  分为单链表(分为普通单链表、单循环链表)、双链表(分为普通双链表、双循环链表)

三、静态链表

  静态链表借助数组来描述线性表的链式存储结构，结点也有数据域data和指针域 next，与前面所讲的链表中的指针不同的是，这里的指针是结点的相对地址（数组下标），又称游标。和顺序表一样，静态链表也要预先分配一块连续的内存空间。当指针域为-1时表示链表结束。

四、链表和顺序表的比较

注意：

• 对于查找来说，顺序表的按下标查找的时间复杂度为O(1)，按内容查找时间复杂度为O(n)；链表的查找时间复杂度为O(n)。
• 对于插入、删除等运算，顺序表的时间复杂度一般为O(n)，链表的时间复杂度为O(1)。

附：王道课后习题笔记

1.给定有n个元素的一维数组，建立一个有序单链表的最低时间复杂度是（O(nlog₂ⁿ)）。

2.为了方便插入和删除数据，可以使用双链表存放数据。

3.将两个有n个元素的有序表归并成一个有序表，其最少比较次数为（n）。

4.线性表的静态链表存储结构与顺序存储结构相比，其优点是（便于插入和删除）。

5.对于一个线性表，既要求能够快速地进行插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应采用（链式）存储结构。

6.

7.

8.


9.

10.

11.

12.