链表

单链表

1
2
3
4

typedef struct {
    ElementType data;
	LNode* next;
}LNode,*LinkList; //LinkList定义表头，LNode*定义结点，两者本质相同

通常使用带头节点的链表，便于空表与非空表的逻辑判断

插入

LInsert(&L,i,e)：表明在结点i前插入元素e

1
2

s->next = p->next;
p->next = s; //将节点s连到p之后，顺序不可颠倒

• 头节点可视为第0个结点

• 其最坏时间复杂度为O(n)，必须先找到结点i的前驱才能进行操作，而这必须从头进行遍历。

后插：假如已经有一个指向结点i的指针p，则后插仅需要O(1)时间复杂度

前插优化方案：当作后插处理，最后交换两结点元素值

1
2
3
4
5

//假如已有p结点指针，前插s结点
s->next = p->next;
p->next = s;
s->data = p->data;
p->data = e;

优化后的方案时间复杂度为O(1)

按位序删除

其定位逻辑与插入操作相同，详细的删除代码：

1
2
3
4

LNode *q = p->next;  //q指向被删除结点
e = q->data;		//e返回结点值
p->next = q->next;  //将q结点从链中断开
free(q);			//回收被删结点内存空间

双链表

在单链表的基础上添加前驱指针prior

方便插入与删除操作(不用做数据交换)

双链表插入

1
2
3
4
5
6
7

//假如在p结点后插入
s->next = p->next;
if(p->next != NULL){ //p的后继非空
    p->next->prior = s;
}
s->prior = p;
p->next = s;

对于前插与按位插入，只需定位到指定结点，通过前驱指针定位到前驱结点进行后插操作即可

循环链表

尾结点指针指向头节点的链表

• 可以循环遍历整个链表
• 从头节点找到尾部，时间复杂度为O(n)
• 从尾部找到头节点，时间复杂度为O(1)

循环双链表

• 初始化链表时，prior和next指针同时指向头节点自己。

循环双链表插入

必须记住：头节点的prior指针必须指向链表的尾结点，表尾结点的next必须指向头节点！

循环双链表删除

与上图同理

静态链表

分配一整片连续的内存空间，结点集中分布

内存地址映射规律：起始地址addr+i*结点长度（i即上图游标，结点长度即元素长度+游标长度）

初始化

a[0]的next设为-1;

查找

从头节点出发依次向后遍历，时间复杂度为O(n)

插入

插入位序为i的结点：

1. 找到空结点存入数据元素
2. 从头节点出发找到位序为i-1的结点
3. 修改新结点next
4. 修改i-1号结点的next

在具体实现的时候所有空闲next指针可设为-2，方便寻找空结点

优点：增删不需要移动大量元素

缺点：容量固定不可变，不能随机存取

操作系统使用的文件分配表FAT采用的就是静态链表，因为其数据元素数量固定不变

顺序表VS链表

逻辑结构

同属线性表，都是线性结构

存储结构