data-structures

最常用的数据结构

定长数组

arr = [0] * 10

int[] arr = new int[10];

vector<int> arr(10);

动态数组

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

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

vector<int> l;
// Add a new element at tail
l.push_back(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()

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

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

双向链表

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

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

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

栈

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

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

stack<int>  s;
s.push(7)
s.top();
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

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

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

优先队列（堆）

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

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

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

HashMap

m = {}

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

unordered_map<string, int> m;

HashSet

s = set()

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

unordered_set<int> s;