跳到主要内容

最常用的数据结构

定长数组

arr = [0] * 10

动态数组

l = []
# Add a new element at tail
l.append(1)

单链表

# To mimic singly linked list, always operate at head
l = deque()
# insert at head, time complexity O(1)
l.appendleft(7)
# access head, time complexity O(1)
l[0]
# remove head, time complexity O(1)
l.popleft()

双向链表

q = deque()
# insert at tail, time complexity O(1)
q.push(7)
# access tail, time complexity O(1)
q[-1]
# remove tail, time complexity O(1)
q.pop()
# insert at head, time complexity O(1)
q.pushleft(7)
# access head, time complexity O(1)
q[0]
# remove head, time complexity O(1)
q.popleft()

# To mimic stack, always operate at tail
s = deque()
s.append(7)
s[-1]
s.pop()

队列

# To mimic a FIFO queue, push at tail, pop at head
q = deque()
q.append(7)
q[0]
q.popleft()
len(q) == 0

优先队列(堆)

# min heap by default
pq = []
heapq.heappush(pq, 7)
pq[0]
heapq.heappop(pq)
len(pq) == 0

HashMap

m = {}

HashSet

s = set()