最常用的数据结构

定长数组

Python

arr = [0] * 10

Java

int[] arr = new int[10];

C++

vector<int> arr(10);

动态数组

Python

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

Java

List<Integer> l = new ArrayList<>();
// Add a new element at tail
l.add(1);

C++

vector<int> l;
// Add a new element at tail
l.push_back(1);

双向链表

Java

// LinkedList is actually a doubly-linked list, to mimic singly linked list, always operate at head
LinkedList<Integer> l = new LinkedList<>();
// insert at head, time complexity O(1)
l.offerFirst(7)
// access head, time complexity O(1)
l.peekFirst()
// remove head, time complexity O(1)
l.pollFirst()

C++

// std::list uses std::deque by default, to mimic singly linked list, always operate at head
list<int> l;
// insert at head, time complexity O(1)
l.push_front(7);
// access head, time complexity O(1)
l.front();
// remove head, time complexity O(1)
l.pop_front();

# deque allows O(1) operation at both head and tail. Only use appendleft/popleft to mimic singly-linked list
from collections import deque

# create a new singly linked list
l = deque()
# insert at head, time complexity O(1)
l.appendleft(7)
# access head, time complexity O(1)
l[0] if len(l) > 0 else None
# remove head, time complexity O(1)
l.popleft() if len(l) > 0 else None

栈

Python

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

Java

Stack<Integer> s = new Stack<>();
s.push(7)
s.peek();
s.pop()
s.empty()

C++

stack<int>  s;
s.push(7)
s.top();
s.pop()

队列

Python

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

Java

Queue<Integer> q = new LinkedList<>();
q.offer(7);
q.peek();
q.poll();
q.isEmpty();

C++

queue<int> q;
s.push_back(7)
s.front();
s.pop();
s.empty()

双端队列

Python

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()

Java

Deque<Integer> q = new ArrayDeque<>();
// insert at tail, time complexity O(1)
q.offerLast(7)
// access tail, time complexity O(1)
q.peekLast()
// remove tail, time complexity O(1)
q.pollLast()
// insert at head, time complexity O(1)
q.offerFirst(7)
// access head, time complexity O(1)
q.peekFirst()
// remove head, time complexity O(1)
q.pollFirst()

C++

deque<int> q;
// insert at tail, time complexity O(1)
q.push_back(7)
// access tail, time complexity O(1)
q.back()
// remove tail, time complexity O(1)
q.pop_back()
// insert at head, time complexity O(1)
q.push_front(7)
// access head, time complexity O(1)
q.front()
// remove head, time complexity O(1)
q.pop_front()

优先队列（堆）

Python

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

Java

// min heap by default
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(7);
pq.peek();
pq.poll();
pq.isEmpty();

C++

// max heap by default
priority_queue<int> pq;
pq.push(7)
pq.top();
pq.pop();
pq.empty()

HashMap

Python

m = {}

Java

Map<String, Integer> m = new HashMap<>();

C++

unordered_map<string, int> m;

HashSet

Python

s = set()

Java

Set<Integer> m = new HashSet<>();

C++

unordered_set<int> s;