学习笔记之线性表

[学习笔记] - 线性表

顺序存储

使用连续的存储单元依次进行存储。

属性：

• 存储起始位置：数组data
• 最大容量： 数组长度MaxSize
• 当前长度： length

随机读取： LOC（\(a_{i+1}\)）= LOC（\(a_i\)）+ c （c为单个元素空间占用大小），因此顺序存储对于随机读取时间复杂度为O(1)。

插入和删除操作涉及到元素移位，最坏情况为删除第一个元素（剩余元素全部迁移）和插入操作（剩余元素全部后移），时间复杂度为O(n)。

---

链式存储

以单链表为例，每个节点除了存储数据本身，存储一个指针指向后继节点。

通常有头指针指向第一个节点，链表最后的节点next指针为空。

单链表的读取

需要依次遍历，时间复杂度O(n)

单链表的插入和删除

时间复杂度为O(1)

- 插入

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

- 删除

q = p->next;
p->next = q->next;
free(q);  // 释放被删除节点空间

链式存储插入删除时间复杂度小，随机读取时间复杂度高

---

循环链表

circular linked list - 将单链表终端节点的指针由空改为指向头节点，是单个链表形成一个环。

双向链表

DoublyLinked list - 是在单链表的每个节点，再设置一个指向前驱节点的指针。解决单链表无法直接访问前驱的问题。

• 插入

s->prior = p;
s->next = p->next;
p->next->prior = s;
p->next = s;

• 删除

p->prior->next = p->next;
p->next->prior = p->prior;

循环双向链表

循环链表 + 双向链表

---

相关知识

双向链表可用来实现LRU（Least Recently Used）算法，是cache eviction中常用的策略。