实现一个 LRU 缓存，支持 get 和 put 操作。

LRU 缓存是一种常见的缓存算法，它是 Least Recently Used 的缩写，意思是删除最近最少使用的缓存。实现 LRU 缓存可以使用哈希表和双向链表的数据结构。

具体实现步骤如下：

1. 定义一个哈希表和一个双向链表。

2. 哈希表用于存储缓存，其中键存储缓存键，值存储链表中相应节点的指针。

3. 双向链表用于存储缓存节点，链表头表示最近使用的缓存，链表尾表示最近未使用的缓存。

4. get操作：如果键存在于哈希表中，则将对应节点移动到链表头并返回节点值，否则返回 -1。

5. put操作：如果键存在于哈希表中，则将对应节点的值更新，将节点移到链表头。

6. 如果键不存在于哈希表中，首先创建一个新节点并加入链表头，然后将键和节点指针添加到哈希表中。

7. 如果缓存超过限制，删除链表尾节点，并在哈希表中删除对应键值对。

以下是一个简单的 Python 代码实现：

```python
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = {}
self.head = ListNode(0, 0) # 双向链表头
self.tail = ListNode(0, 0) # 双向链表尾
self.head.next = self.tail
self.tail.prev = self.head

def get(self, key: int) -> int:
if key in self.cache:
node = self.cache[key]
self.move_to_head(node)
return node.val
else:
return -1

def put(self, key: int, value: int) -> None:
if key in self.cache:
node = self.cache[key]
node.val = value
self.move_to_head(node)
else:
node = ListNode(key, value)
self.cache[key] = node
self.add_to_head(node)
if len(self.cache) > self.capacity:
tail_node = self.remove_tail()
del self.cache[tail_node.key]

def move_to_head(self, node):
self.remove_node(node)
self.add_to_head(node)

def remove_node(self, node):
node.prev.next = node.next
node.next.prev = node.prev

def add_to_head(self, node):
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node

def remove_tail(self):
node = self.tail.prev
self.remove_node(node)
return node
```

在上述代码中，节点类为：

```python
class ListNode:
def __init__(self, key=0, val=0):
self.key = key
self.val = val
self.prev = None
self.next = None
```

时间复杂度分析：

- get: O(1)
- put: O(1) ，若需要删除尾部则最坏为 O(capacity)。

因此，该算法的时间复杂度为 O(1)。