线性表

线性表是由一系列数据元素构成的有限序列；在这些数据元素中，每一个元素都有一个明确的前驱和一个后继（除了首尾元素）；

Ⓜ️

特点：

• 一对一的关系：线性表中的元素之间是一对一的关系，每个元素仅有一个前驱和一个后继，形成线性序列；

• 顺序性：线性表中的元素是按照一定的顺序排列的，这个顺序是固定的，可以通过索引来访问；

• 简洁性：线性表的结构简单，仅需要存储数据元素以及维护它们之间的前驱和后继关系；

• 操作方便：由于线性表的结构简单直观，它便于进行插入、删除、查找等操作；

• 存储灵活：线性表可以采用多种方式存储，如顺序存储结构（数组）和链式存储结构（链表），还可以扩展出栈、队列等特殊线性表形式；

• 高效访问：在顺序存储的情况下，线性表可以实现高效的随机访问，即直接通过索引快速访问任何一个元素；

线性表在计算机程序设计中应用极为广泛，例如，它可以用来表示内存中的数据缓冲区、队列、栈、字符串等；在实际应用中，根据需要，线性表可以进一步演化为具有特定功能的抽象数据类型，如栈、队列、链表、有序表等；

顺序表

算法题

（408真题算法、力扣）🛩️🛩️🛩️🛩️

链表

单链表

线性表的链式存储称单链表，结点类型描述如下

struct LNode{
    int data; //数据域
    LNode *next; //指针域
}

为了操作上的方便，在单链表的第一个结点之前附加一个结点，称头结点；头结点的数据域可不设任何信息，也可以记录表长等信息；

注意：不论带不带头结点，头指针始终指向链表的第一个结点

Ⓜ️

🛩️头插建表

🛩️尾插建表

🛩️插、删、找

双链表

问题背景：单链表结点中要访问某个结点的前驱结点(插入、删除)时，只能从头开始遍历

双链表由一系列结点组成，每个结点包含数据域和两个指针域；这两个指针分别称为“前驱指针”和“后继指针”；适用于需要频繁进行插入和删除操作的场景；例如，它常用于实现栈、队列、列表等数据结构；

Ⓜ️

🛩️

特点：

• 灵活的结点访问：由于每个结点都有前驱和后继指针，我们可以轻松地在双链表中进行双向遍历；

• 高效的插入和删除：双链表在进行结点插入或删除操作时，可以不需要遍历整个链表，因此这些操作的时间复杂度通常是O(1)；

• 无须额外空间：与数组等数据结构不同，双链表在插入和删除时不需要额外空间，因为它可以通过改变指针来调整内存布局；

循环链表

分为循环单链表和循环双链表，在这种链表中，最后一个结点的指针指向第一个结点，形成一个环状结构；这种结构使得循环链表中的每个结点都可以通过指针环形遍历整个链表；循环链表可以看作是单向链表的一种扩展，它保留了单向链表的所有特性，并额外提供了一些独特的优点；

循环链表适用于需要环形遍历的场景，例如，在某些算法中，元素需要被循环使用，或者在模拟一些特定问题时，环状结构能够更好地描述问题本身；

Ⓜ️

Ⓜ️

静态链表

静态链表是一种利用数组来模拟链表结构的数据结构；在静态链表中，数组的每个元素都包含两部分：一部分是数据域，用于存储实际的数据；另一部分是游标（或称为指针）域，用于存储指向数组中下一个元素的索引；静态链表适用于那些需要频繁进行插入和删除操作，但又不需要动态扩展的场景；它特别适合于数据结构中的元素数量已知且固定，或者内存空间有限的情况；

Ⓜ️

特点：

• 数组实现：静态链表使用数组来存储数据，这使得它在内存中是连续存储的，可以利用数组的随机访问特性；

• 游标代替指针：在静态链表中，游标用于代替动态链表中的指针，存储下一个元素在数组中的索引；

• 有限的动态性：静态链表在创建时就已经确定了大小，因此它不具备动态链表动态扩展的能力；

• 高效的随机访问：由于游标实际上就是数组的索引，所以静态链表可以实现O(1)的随机访问时间复杂度；

• 节省空间：静态链表不需要像动态链表那样分配和释放内存，因此它在空间上更为节省；

算法题

（408真题算法、力扣）🛩️🛩️🛩️🛩️