【数据结构】线性表List基础概念总结（无代码）

一、基本概述

1、概念：零个或多个数据元素的有限序列

2、特点：类型相同、有限性、有序性、

3、在较复杂的线性表中，一个数据元素可以由若干个数据项组成。

二、线性表的抽象数据类型

• 对于一个线性表，插入数据和删除数据都是必须的操作
• 线性表的抽象数据类型定义如下：

• 对于复杂的个性化的操作，其实就是把基本操作组合起来实现的。

三、线性表的顺序存储结构

1、读取存取数据时，不管是哪个位置，时间复杂度都是O(1)；

2、插入删除操作时，时间复杂度都是O(n)；

四、线性表的链式存储结构

    n个结点链结成一个链表，即为线性表的链式存储结构，因为此链表的每个结点中只包含一个指针域（指向后继结点），所以叫单链表。

1、单链表的读取

• 时间复杂度：O(n)。从头开始查找，直到第i个节点。
• 核心思想：工作指针后移→算法的常用技术

2、单链表的插入

3、单链表的删除

4、插入和删除的对比

5、单链表的整表创建

    创建单链表的过程是一个动态生成链表的过程。即从空表的初始状态起，依次建立各元素结点，并逐个插入链表。插队的思想。

• 头插法：始终让新结点在第一的位置。
• 尾插法：把每次新结点都插在终端结点的后面。

6、单链表的整表删除

    在内存中将链表内容给释放掉。不能直接将结点置为空，因为结点有数据域和指针域，需要根据指针将每个结点的数据域置为空。

总结：顺序存储结构和单链表结构的对比

经验型结论：

• 若需要频繁查找，很少进行插入和删除操作，推荐顺序存储结构；若需要频繁的插入和删除时，推荐单链表结构。
• 若事先知道线性表的元素个数，推荐顺序存储结构。若事先不知道元素个数，推荐单链表结构。

五、其他链表

1、静态链表：用数组描述的链表，也叫游标实现法。

    第一个元素的cur放第一个空闲结点的下标，最后一个元素放第一个有数值的结点的下标，这样就可以完全确定该数组了。

    在实现插入操作时，先在有数值结点的尾巴上插入一个元素并将cur置为理论上的下一个元素的下标，然后将第一个元素的cur值+1，再修改要插入位置的结点前的cur值进行改变即可。

• 插入操作：静态模拟动态链表结构的存储空间的分配

从备用链表取第一个结点作为待插入的新结点。

• 删除操作：

• 静态链表的优缺点：

2、循环链表

 这里不用头指针，用指向终端结点的尾指针来表示循环链表，此时查找开始结点和终端结点就很方便了。

将两个循环链表合并成一个表时：

3、双向链表

双向循环链表：

增加和删除元素的注意事项自己想明白了就行。

总结：

线性表总结