在数据结构中，顺序表的插入和删除操作的时间复杂度是什么

在数据结构中，顺序表的插入和删除操作的时间复杂度都是O(n)，顺序表是一种基本的线性数据结构，插入或删除一个元素时需要移动后续的所有元素，导致时间复杂度的增加，因此时间复杂度都是O(n)。

一、在数据结构中，顺序表的插入和删除操作的时间复杂度是什么

顺序表的插入操作需要先将插入位置以及之后的元素向后移动一位，然后再将要插入的元素放到插入位置处。因此，在最坏的情况下，需要移动n个元素，时间复杂度为O(n)。

顺序表的删除操作需要将删除位置之后的所有元素向前移动一位，以填补被删除元素的位置。因此，在最坏的情况下，需要移动n-1个元素，时间复杂度为O(n)。

因此，在数据结构中，顺序表的插入和删除操作的时间复杂度都为O(n)。

二、数据结构

1、简介

数据结构是一种具有一定逻辑关系，在计算机中应用某种存储结构，并且封装了相应操作的数据元素集合。它包含三方面的内容，逻辑关系、存储关系及操作。不同种类的数据结构适合于不同种类的应用，而部分甚至专门用于特定的作业任务。例如，计算机网络依赖于路由表运作，B 树高度适用于数据库的封装。随着应用程序变得越来越复杂和数据越来越丰富，几百万、几十亿甚至几百亿的数据就会出现，而对这么大对数据进行搜索、插入或者排序等的操作就越来越慢，数据结构就是用来解决这些问题的。

2、常见的数据结构

• 栈（Stack）：栈是一种特殊的线性表，它只能在一个表的一个固定端进行数据结点的插入和删除操作。
• 队列（Queue）：队列和栈类似，也是一种特殊的线性表。和栈不同的是，队列只允许在表的一端进行插入操作，而在另一端进行删除操作。
• 数组（Array）：数组是一种聚合数据类型，它是将具有相同类型的若干变量有序地组织在一起的集合。
• 链表（Linked List）：链表是一种数据元素按照链式存储结构进行存储的数据结构，这种存储结构具有在物理上存在非连续的特点。
• 树（Tree）：树是典型的非线性结构，它是包括，2 个结点的有穷集合 K。
• 图（Graph）：图是另一种非线性数据结构。在图结构中，数据结点一般称为顶点，而边是顶点的有序偶对。
• 堆（Heap）：堆是一种特殊的树形数据结构，一般讨论的堆都是二叉堆。
• 散列表（Hash table）：散列表源自于散列函数(Hash function)，其思想是如果在结构中存在关键字和T相等的记录，那么必定在F(T)的存储位置可以找到该记录，这样就可以不用进行比较操作而直接取得所查记录。

3、常用算法

数据结构研究的内容：就是如何按一定的逻辑结构，把数据组织起来，并选择适当的存储表示方法把逻辑结构组织好的数据存储到计算机的存储器里。算法研究的目的是为了更有效的处理数据，提高数据运算效率。数据的运算是定义在数据的逻辑结构上，但运算的具体实现要在存储结构上进行。一般有以下几种常用运算：

• 检索：检索就是在数据结构里查找满足一定条件的节点。一般是给定一个某字段的值，找具有该字段值的节点。
• 插入：往数据结构中增加新的节点。
• 删除：把指定的结点从数据结构中去掉。
• 更新：改变指定节点的一个或多个字段的值。
• 排序：把节点按某种指定的顺序重新排列，例如递增或递减。

三、顺序表

1、简介

顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。

2、顺序表实现代码

#define TRUE 1
#define LIST_INIT_SIZE 100 // 初始分配空间
#define LISTINCREMENT 10   // 空间分配增值
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASBLE -1
#define OVERFLOW -2
typedef int Status;
typedef int Elemtype;

typedef struct {
    ElemType *elem; // 头指针
    int length;     // 顺序表使用长度
    int listsize;   // 顺序表总长
} SqList;
//初始化空的顺序表
Status InitList_Sq(SqList *L) {
    L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
    if (!L->elem) // 等效于 L->elem == NULL
        exit(OVERFLOW);
    L->length = 0; // 此函数仅仅是创造一片空间，为储存数据时为空表
    L->listsize = LIST_INIT_SIZE;
    return OK;
} //

3、顺序表特点

优点

• 顺序表的逻辑空间连续的同时物理空间也连续。
• 顺序表可以随机读取元素，时间复杂度O(1)，适合有经常读取元素的场景。
• 顺序表内存上可以动态分配，很好解决了数组长度固定的限制可能导致的溢出。

缺点

其插入和删除函数的原理就决定了其在操作过程中可能大量移动数据的特点，如在表头插入或者删除元素，就需要移动顺序表内的所有元素，但是在表尾插入或者删除元素时又比较方便，时间复杂度O(n)。

延伸阅读1：顺序表的三个要素

• 用elems 记录存储位置的基地址
• 分配一段连续的存储空间size
• 用length 记录实际的元素个数，即顺序表的长度