数据结构与算法—链表list

目录

链表

链表类型

链表插入

链表删除

写程序注意点

与数组区别

链表应用

LRU 实现思想

---

链表

        链表，一种提高数据读取性能的技术，在硬件设计、软件开发中有广泛应用。常见CPU缓存，数据库缓存，浏览器缓存等。缓存满时，采用相应的策略清除一部分缓存。如FIFO,LFU(Least Frequently Used),LRU(Least Recently Used)

链表类型

        单链表，双链表，循环链表

链表插入

 

x->next = p->next;
p->next = x;

链表删除

删除p节点的后继节点

p->next = p->next->next；

删除链表的最后一个节点

if(head->next ==  NULL)head = NULL;

写程序注意点

链表尾空，代码能否工作

链表只有一个节点，

链表包含两个节点？

链表头尾节点处理

与数组区别

数组需要连续的存储空间；链表不需要连续的存储

数组与链表的对比，并不能局限于时间复杂度。

数组简单易用，在实现上使用连续的内存空间，借助于CPU的缓存机制，预读数组中的数据，访问效率更高。而链表在内存中并不是连续存储，没法预读。

数组缺点，系统没有足够的连续空间，导致内存不足。数组申请时大小固定，如果不够用，不支持动态扩容。

如果代码对内存使用苛刻，使用数组。因为链表节点占用空间。而且链表的删除，插入导致内存申请和释放，容易造成内存碎片。

链表应用

LRU 实现思想

维护一个链表，越靠近尾部节点，是越早之前访问。有新数据访问时，从链表头开始顺序遍历链表。

1. 如果数据已经被缓存到链表中，遍历链表，将其从原来位置删除，插入到链表头。
2. 如果不在缓存中，缓存未满，直接将此节点插入到链表的头部
3. 如果缓存满，，将链表尾节点删除，将新的节点插入链表的头部

list.h

typedef struct listNode
{struct listNode *next;void *value;
}listNode;typedef struct linkedList
{listNode *head;size_t len;
}linkedList;