LRUCache之问

今天面了拼多多，LRUCache再次出现在了我的面前，面对这个半年以来面对最多的面试代码问题，我给出我的解决方案：

1、链表

使用链表作为最主要的数据结构，将数据按照先后顺序在链表尾部插入，直到满了开始从头减去链表，时间复杂度分析分别为：

使用单向链表，get需要找到我们要的cache所在位置，因此时间复杂度为O(n),add由于需要先判断是否已经存在，所以需要调用get方法，在满的时候需要remove，所以虽然删除时间复杂度为O(1)，整体时间复杂度为O(n),而remove从头部删除时间复杂度为O(1)但是在中间的时候需要做get操作，时间复杂度依旧为O(n)。使用双向链表可以降低add()时间复杂度，但是整体来说时间复杂度在O(n).

2、HashMap + LinkedList

使用双向链表保存数据，使用HashMap保存数据在LinkedList中的位置，时间复杂度如下：