如何完成线性表结构下的增删查？

这篇文章主要讲解如何在线性表结构下实现增加、删除、查找（CRUD）操作。

线性表 ^{1 2 3 4}

线性表是一种基础的数据结构，它由n个具有相同数据类型的元素组成的有限序列。 ³ 线性表中的元素在逻辑上是连续的，即除了第一个元素外，每个元素都有一个直接前驱，除了最后一个元素外，每个元素都有一个直接后继。
常见的线性表结构有：

• 数组 ¹
• 链表 ^{3 1}

线性表的顺序存储与链式存储 ⁴

顺序存储 ⁴

顺序存储是指用一组地址连续的存储单元依次存储线性表中的数据元素，通常用数组来实现。
优点：

• 可以随机访问表中的任意元素。
  缺点：
• 插入和删除操作需要移动大量元素。
• 需要预先分配存储空间，容易造成空间浪费。

链式存储 ^{3 4}

链式存储是指用一组任意的存储单元存储线性表中的数据元素，元素之间的逻辑关系通过指针来连接，通常用链表来实现。 ³
优点：

• 插入和删除操作不需要移动元素，只需要修改指针。
• 不需要预先分配存储空间，可以动态扩展。
  缺点：
• 不能随机访问表中的任意元素，需要从头开始遍历。
• 需要额外的空间存储指针。

线性表的常见操作

线性表常见的操作包括：

• 增加（Create）：向线性表中插入一个新元素。
• 删除（Delete）：删除线性表中的一个元素。
• 查找（Read）：查找线性表中指定元素的位置。
• 修改（Update）：修改线性表中指定元素的值。

数组实现

增加

• 在数组末尾添加元素：时间复杂度为O(1)。
• 在数组中间或开头插入元素：需要将插入位置后的所有元素后移一位，时间复杂度为O(n)。

删除

• 删除数组末尾的元素：时间复杂度为O(1)。
• 删除数组中间或开头的元素：需要将删除位置后的所有元素前移一位，时间复杂度为O(n)。

查找

• 查找指定元素：
  • 如果数组是无序的，需要遍历整个数组，时间复杂度为O(n)。
  • 如果数组是有序的，可以使用二分查找，时间复杂度为O(log n)。

修改

• 已知元素位置：时间复杂度为O(1)。
• 未知元素位置：先查找，再修改，时间复杂度取决于查找算法。

链表实现 ³

增加

• 在链表末尾添加元素：时间复杂度为O(n)，需要先遍历到链表末尾。
• 在链表指定位置插入元素：时间复杂度为O(n)，需要先遍历到指定位置。

删除

• 删除链表末尾的元素：时间复杂度为O(n)，需要先遍历到链表末尾。
• 删除链表指定位置的元素：时间复杂度为O(n)，需要先遍历到指定位置。

查找

• 查找指定元素：需要从头开始遍历链表，时间复杂度为O(n)。

修改

• 已知元素位置：时间复杂度为O(1)。
• 未知元素位置：先查找，再修改，时间复杂度取决于查找算法。

总结