线性表之单链表

线性表

零个或者多个数据元素的有限序列

线性表中必须是相同类型的元素

• 线性表的长度是线性表中数据元素的个数
• 数组长度是存在线性表存储空间的长度

任意时刻 线性表的长度小于或者等于数组的长度

• 线性表无论读和存任意位置的时候时间复杂度都是O(1)
• 线性表进行增删的时候 时间复杂度都是O(n)

线性表的链式存储结构

让每个元素都获取它下一个元素的存储地址这样我们拿到第一个元素的时候就可以拿到它下一个元素的存储位置，拿到下一个元素 就可以递归去拿后面元素的存储位置

为了表示每个元素Ai和他后面元素的存储关系，对于元素Ai而言，除了存储自身的数据，还存储一个其直接后继的信息。我们把存储数据元素信息成为数据域，把存储直接后继位置成为 指针域，两个合起来成为Node。

N个节点组成一个链表。即线性表的链式存储结构

• 链表的第一个节点的存储位置 被成为头指针
• 链表的最后一个结点的指针执行NULL
• 有时候为了我们更加方便的对链表进行操作，会对单链表的第一个结点钱附加一个结点，称为头结点。

头指针和头结点的异同

• 头指针指向链表中第一个结点的位置。如果存储头结点，则头指针执行头结点的位置

• 头指针具有标示的作用，所以常以头指针冠以链表的名称

• 无论链表是否为空，头指针均不为空。头指针是链表的必要元素

• 头结点是为了操作统一的方法和名称而设立的，放到第一个结点之前，其数据域一般无意义，

• 有了头结点，删除和删除第一结点就变得统一了

• 头结点可有可无，不是线性表的链式存储结构的必要要素

线性表的单链表的存储结构

typedef struct Node{ ElementType Data; struct Node*next; }Node;

单链表的查找 需要从第一个位置开始查，根据当前指针一直往后面查。时间复杂度类似线性表的顺序存储结构的增删，好的情况大O计法为O(1),坏的情况为O(n)

单链表的插入和删除

现在存在Node(p),Node(p->next)，现在有一个s结点想要插入到两者中间

s->next = p->next
p->next = s

如果两者倒过来 将发生很严重的Bug

单链接的删除操作

核心语法

q = p->next;
p->next = q->next;

线性表的顺序存储和链式存储做比较

• 如果只是插入删除一个元素的话，单链表和线性表的没有任何区别都是O(n),但是如果插入若干元素比如10个元素的话，第一次的时间复杂度两者均为O(N)，但是如果是线性表的话，后面的时间复杂度均为O(1)，而线性表每次均为O(N),所以频繁的发生插入和删除的话，首选还是单链表