_ _ _ _ _ _ _
| (_) | | | | | (_) | |
| |_ _ __ | | _____ __| | | |_ ___| |_
| | | '_ \| |/ / _ \/ _` | | | / __| __|
| | | | | | < __/ (_| | | | \__ \ |_
|_|_|_| |_|_|\_\___|\__,_| |_|_|___/\__|
1.1 原理
链表与数组都非常基础也非常常用,从底层数据结构上看,数组需要一块连续的内存空间来存储数据,而链表则不需要,链表通过指针将一组零散的内存块串联起来使用。
日常中有三种常见的链表结构:
- 单向链表
- 双向链表
- 循环链表
1.2 分析
对于单链表来说,插入和删除操作的时间复杂度为 $O(1)$。
双向链表可以支持 $O(1)$ 时间复杂度下找到前驱节点。
1.3 思考
- 如何用链表来实现LRU缓存淘汰策略?
- 了解Java中的LinkedHashMap的实现原理,其中用到的是什么链表?
- 在实践中什么时候选择数组?什么时候选择链表?
1.4 LeetCode练习
有疑问加站长微信联系(非本文作者)