【数据结构】线性表概括

目录

 一、线性表

二、分类

三、实现

---

 一、线性表

线性表（linear list）是 n个具有相同特性的数据元素的有限序列。 

线性表中数据元素的个数称为线性表的长度。长度等于零的线性表称为空表。

线性表的逻辑图：

        线性表中的数据元素具有相同类型，相邻元素具有前驱和后继关系，相邻元素中在前的元素是后一个元素的前驱，在后的元素是前一个元素的后继。

        在这个序列中第一个元素没有前驱，最后一个元素没有后继。其他每个元素有且仅有一个前驱和一个后继。

二、分类

        线性表有两种存储结构：顺序存储和链接存储。一般来说可以分为顺序表和链表这两种基本结构。

        一般来说，线性表主要包括顺序表和链表。

        顺序表是将元素依次存储在一块连续的存储空间中，可以通过索引直接访问任何一个元素，因此具有较高的访问效率。

        链表则是通过节点之间的链接关系来存储元素，每个节点包含数据域和指针域，指针域指向下一个节点。

        链表的优点在于插入和删除操作效率较高，不需要移动大量元素，但访问效率相对较低，需要从头节点开始逐个遍历。

        还有一些特殊的线性表：栈和队列。

        栈是一种后进先出（LIFO）的数据结构，只允许在栈顶进行插入和删除操作。栈的应用非常广泛，如函数调用、表达式求值等。根据实现方式的不同，栈可以分为顺序栈和链栈。

        队列是一种先进先出（FIFO）的数据结构，允许在队尾插入元素，在队头删除元素。常见的队列类型有顺序队列和链队列。

下面是关于线性表的大概类型结构图：

• 顺序表和链表的区别

存储空间

• 顺序表：在物理存储上，顺序表的元素是连续存放的。所以在内存中，顺序表的各个元素占据着相邻的存储单元。
• 链表：链表的元素在逻辑上连续，但在物理存储上不一定连续。链表的每个元素（节点）包含 数据 和 指向下一个节点的指针，节点可以通过指针链接起来形成逻辑上的连续序列，但它们在内存中的位置可能是分散的。

随机访问

• 顺序表：支持随机访问，时间复杂度为O(1)。可以通过数组下标直接计算出元素的存储位置，从而快速访问。
• 链表：不支持随机访问，访问一个元素的时间复杂度为O(N)。因为需要从链表头节点开始，沿着指针逐个遍历节点，才能找到目标节点。

插入和删除操作

• 顺序表：可能需要搬移元素，效率低，时间复杂度是O(N)。
• 链表：只需修改指针指向。

容量概念

• 顺序表：通常有固定的容量限制（静态顺序表），但在动态顺序表中空间不够可以扩容。
• 链表：没有固定的容量概念，理论上可以无限添加节点，只要内存足够。

应用场景

• 顺序表：适用于元素个数相对固定，且需要频繁进行元素访问的场景。
• 链表：适用于元素个数不确定，且需要频繁进行插入和删除操作的场景

缓存利用率

• 顺序表：由于元素物理存储连续，在访问元素时，可以利用缓存的预取机制，缓存利用率高，能够提高数据访问的速度。
• 链表：元素物理存储分散，缓存预取机制难以发挥作用，缓存利用率低。

三、实现

1. 顺序表的实现

• 【数据结构】顺序表（sequential list）

2. 链表的实现

• 【数据结构】链表（linked list）

3. 栈的实现

• 【数据结构】栈（stack）

4. 队列的实现

• 【数据结构】队列（queue）