Data Structures Reference

All common data structures across C++, Java, Python, and C# — syntax only, no algorithms.

---

1. Array (Static)

Fixed-size, contiguous memory. O(1) access by index.

C++

#include <array>

int arr[5] = {1, 2, 3, 4, 5};        // C-style array
std::array<int, 5> arr2 = {1,2,3,4,5}; // std::array (fixed size)

arr[0];        // access
arr[0] = 10;   // update

Java

int[] arr = {1, 2, 3, 4, 5};        // primitive array
Integer[] arr2 = new Integer[5];     // object array

arr[0];        // access
arr[0] = 10;   // update
arr.length;    // size

Python

# Python lists act as dynamic arrays
arr = [1, 2, 3, 4, 5]

arr[0]         # access
arr[0] = 10    # update
len(arr)       # size

# Fixed-size using array module
import array
arr2 = array.array('i', [1, 2, 3, 4, 5])  # 'i' = int

C#

int[] arr = {1, 2, 3, 4, 5};
int[] arr2 = new int[5];

arr[0];        // access
arr[0] = 10;   // update
arr.Length;    // size

---

2. Dynamic Array (List / Vector)

Resizable array. Amortized O(1) append.

C++

#include <vector>

std::vector<int> v = {1, 2, 3};
v.push_back(4);       // add to end
v.pop_back();         // remove from end
v.insert(v.begin() + 1, 99);  // insert at index
v.erase(v.begin() + 1);       // remove at index
v.size();             // size
v[0];                 // access
v.front();            // first element
v.back();             // last element
v.empty();            // check if empty
v.clear();            // remove all

Java

import java.util.ArrayList;

ArrayList<Integer> list = new ArrayList<>();
list.add(1);              // add to end
list.add(1, 99);          // insert at index
list.remove(0);           // remove at index
list.remove(Integer.valueOf(99)); // remove by value
list.get(0);              // access
list.set(0, 10);          // update at index
list.size();              // size
list.isEmpty();           // check if empty
list.contains(10);        // search
list.clear();             // remove all

Python

lst = [1, 2, 3]
lst.append(4)          # add to end
lst.insert(1, 99)      # insert at index
lst.pop()              # remove from end
lst.pop(1)             # remove at index
lst.remove(99)         # remove by value
lst[0]                 # access
lst[0] = 10            # update
len(lst)               # size
99 in lst              # search
lst.clear()            # remove all

C#

using System.Collections.Generic;

List<int> list = new List<int> {1, 2, 3};
list.Add(4);              // add to end
list.Insert(1, 99);       // insert at index
list.RemoveAt(0);         // remove at index
list.Remove(99);          // remove by value
list[0];                  // access
list[0] = 10;             // update
list.Count;               // size
list.Contains(10);        // search
list.Clear();             // remove all

---

3. Stack (LIFO)

Last In, First Out. O(1) push/pop.

C++

#include <stack>

std::stack<int> st;
st.push(1);    // push
st.push(2);
st.top();      // peek top → 2
st.pop();      // remove top
st.size();     // size
st.empty();    // check if empty

Java

import java.util.Stack;
// or prefer Deque as stack:
import java.util.ArrayDeque;

ArrayDeque<Integer> st = new ArrayDeque<>();
st.push(1);        // push
st.push(2);
st.peek();         // peek top → 2
st.pop();          // remove top
st.size();         // size
st.isEmpty();      // check if empty

Python

# Use list as stack
st = []
st.append(1)    # push
st.append(2)
st[-1]          # peek top → 2
st.pop()        # remove top
len(st)         # size
not st          # check if empty

C#

using System.Collections.Generic;

Stack<int> st = new Stack<int>();
st.Push(1);      // push
st.Push(2);
st.Peek();       // peek top → 2
st.Pop();        // remove top
st.Count;        // size
st.Contains(1);  // search

---

4. Queue (FIFO)

First In, First Out. O(1) enqueue/dequeue.

C++

#include <queue>

std::queue<int> q;
q.push(1);     // enqueue
q.push(2);
q.front();     // peek front → 1
q.back();      // peek back → 2
q.pop();       // dequeue (removes front)
q.size();      // size
q.empty();     // check if empty

Java

import java.util.ArrayDeque;
import java.util.Queue;

Queue<Integer> q = new ArrayDeque<>();
q.offer(1);      // enqueue
q.offer(2);
q.peek();        // peek front → 1
q.poll();        // dequeue (removes front)
q.size();        // size
q.isEmpty();     // check if empty

Python

from collections import deque

q = deque()
q.append(1)       # enqueue
q.append(2)
q[0]              # peek front → 1
q.popleft()       # dequeue
len(q)            # size
not q             # check if empty

C#

using System.Collections.Generic;

Queue<int> q = new Queue<int>();
q.Enqueue(1);    // enqueue
q.Enqueue(2);
q.Peek();        // peek front → 1
q.Dequeue();     // dequeue
q.Count;         // size
q.Contains(2);   // search

---

5. Deque (Double-Ended Queue)

Insert/remove from both ends in O(1).

C++

#include <deque>

std::deque<int> dq;
dq.push_front(1);   // add to front
dq.push_back(2);    // add to back
dq.front();         // peek front
dq.back();          // peek back
dq.pop_front();     // remove front
dq.pop_back();      // remove back
dq.size();

Java

import java.util.ArrayDeque;

ArrayDeque<Integer> dq = new ArrayDeque<>();
dq.addFirst(1);    // add to front
dq.addLast(2);     // add to back
dq.peekFirst();    // peek front
dq.peekLast();     // peek back
dq.pollFirst();    // remove front
dq.pollLast();     // remove back
dq.size();

Python

from collections import deque

dq = deque()
dq.appendleft(1)   # add to front
dq.append(2)       # add to back
dq[0]              # peek front
dq[-1]             # peek back
dq.popleft()       # remove front
dq.pop()           # remove back
len(dq)

C#

using System.Collections.Generic;

// Use LinkedList as deque
LinkedList<int> dq = new LinkedList<int>();
dq.AddFirst(1);          // add to front
dq.AddLast(2);           // add to back
dq.First.Value;          // peek front
dq.Last.Value;           // peek back
dq.RemoveFirst();        // remove front
dq.RemoveLast();         // remove back
dq.Count;

---

6. Linked List

Nodes connected by pointers. O(1) insert/delete at known node; O(n) access.

C++

#include <list>

// Singly linked list — manual
struct Node {
    int data;
    Node* next;
    Node(int d) : data(d), next(nullptr) {}
};

// STL doubly linked list
std::list<int> ll = {1, 2, 3};
ll.push_front(0);       // add to front
ll.push_back(4);        // add to back
ll.pop_front();         // remove front
ll.pop_back();          // remove back
ll.front();             // peek front
ll.back();              // peek back
ll.size();

Java

import java.util.LinkedList;

LinkedList<Integer> ll = new LinkedList<>();
ll.addFirst(1);          // add to front
ll.addLast(2);           // add to back
ll.removeFirst();        // remove front
ll.removeLast();         // remove back
ll.getFirst();           // peek front
ll.getLast();            // peek back
ll.size();

Python

# Manual singly linked list
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# Python collections.deque is a doubly linked list
from collections import deque
ll = deque([1, 2, 3])
ll.appendleft(0)    # add to front
ll.append(4)        # add to back
ll.popleft()        # remove front
ll.pop()            # remove back

C#

using System.Collections.Generic;

LinkedList<int> ll = new LinkedList<int>();
ll.AddFirst(1);          // add to front
ll.AddLast(2);           // add to back
ll.RemoveFirst();        // remove front
ll.RemoveLast();         // remove back
ll.First.Value;          // peek front
ll.Last.Value;           // peek back
ll.Count;

---

7. Hash Map (Dictionary)

Key-value pairs. Average O(1) get/put.

C++

#include <unordered_map>  // O(1) avg
#include <map>            // O(log n), sorted

std::unordered_map<string, int> mp;
mp["alice"] = 25;         // insert / update
mp["bob"] = 30;
mp["alice"];              // access → 25
mp.count("alice");        // check existence → 1
mp.erase("alice");        // delete
mp.size();

for (auto& [key, val] : mp)
    cout << key << ": " << val;

Java

import java.util.HashMap;

HashMap<String, Integer> map = new HashMap<>();
map.put("alice", 25);         // insert / update
map.get("alice");             // access → 25
map.getOrDefault("bob", 0);   // safe access
map.containsKey("alice");     // check existence
map.remove("alice");          // delete
map.size();

for (var entry : map.entrySet())
    System.out.println(entry.getKey() + ": " + entry.getValue());

Python

mp = {}
mp["alice"] = 25        # insert / update
mp["alice"]             # access → 25
mp.get("bob", 0)        # safe access
"alice" in mp           # check existence
del mp["alice"]         # delete
len(mp)

for key, val in mp.items():
    print(key, val)

# Counter (frequency map)
from collections import Counter
freq = Counter([1, 2, 2, 3, 3, 3])  # {3:3, 2:2, 1:1}

C#

using System.Collections.Generic;

Dictionary<string, int> dict = new Dictionary<string, int>();
dict["alice"] = 25;           // insert / update
dict["alice"];                // access → 25
dict.ContainsKey("alice");    // check existence
dict.TryGetValue("bob", out int val); // safe access
dict.Remove("alice");         // delete
dict.Count;

foreach (var kvp in dict)
    Console.WriteLine($"{kvp.Key}: {kvp.Value}");

---

8. Hash Set

Unique elements. Average O(1) add/remove/search.

C++

#include <unordered_set>  // O(1) avg
#include <set>            // O(log n), sorted

std::unordered_set<int> st;
st.insert(1);      // add
st.insert(2);
st.count(1);       // check existence → 1
st.erase(1);       // remove
st.size();

for (int x : st) cout << x;

Java

import java.util.HashSet;

HashSet<Integer> set = new HashSet<>();
set.add(1);           // add
set.add(2);
set.contains(1);      // check existence → true
set.remove(1);        // remove
set.size();

for (int x : set) System.out.println(x);

Python

st = set()
st.add(1)         # add
st.add(2)
1 in st           # check existence → True
st.remove(1)      # remove (raises if not found)
st.discard(1)     # remove (safe)
len(st)

# From list
st2 = {1, 2, 3}

C#

using System.Collections.Generic;

HashSet<int> set = new HashSet<int>();
set.Add(1);           // add
set.Add(2);
set.Contains(1);      // check existence → true
set.Remove(1);        // remove
set.Count;

foreach (int x in set) Console.WriteLine(x);

---

9. Priority Queue (Heap)

Min or max element always at top. O(log n) insert, O(1) peek, O(log n) remove.

C++

#include <queue>

// Max-heap (default)
std::priority_queue<int> maxPQ;
maxPQ.push(3);
maxPQ.push(1);
maxPQ.push(5);
maxPQ.top();      // 5 (max)
maxPQ.pop();      // removes 5

// Min-heap
std::priority_queue<int, vector<int>, greater<int>> minPQ;
minPQ.push(3);
minPQ.top();      // smallest

Java

import java.util.PriorityQueue;
import java.util.Collections;

// Min-heap (default)
PriorityQueue<Integer> minPQ = new PriorityQueue<>();
minPQ.offer(3);
minPQ.offer(1);
minPQ.offer(5);
minPQ.peek();     // 1 (min)
minPQ.poll();     // removes 1

// Max-heap
PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Collections.reverseOrder());
maxPQ.offer(3);
maxPQ.peek();     // largest

Python

import heapq

# Min-heap
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 5)
heap[0]                  # peek min → 1
heapq.heappop(heap)      # removes min → 1

# Max-heap (negate values)
maxHeap = []
heapq.heappush(maxHeap, -3)
-heapq.heappop(maxHeap)  # → 3

# Build heap from list
nums = [3, 1, 5]
heapq.heapify(nums)

C#

// .NET 6+ has PriorityQueue
using System.Collections.Generic;

// Min-heap (lower priority value = higher priority)
PriorityQueue<int, int> pq = new PriorityQueue<int, int>();
pq.Enqueue(3, 3);   // (element, priority)
pq.Enqueue(1, 1);
pq.Enqueue(5, 5);
pq.Peek();          // 1
pq.Dequeue();       // removes 1
pq.Count;

---

10. Tree Map / Sorted Map

Key-value pairs with keys kept in sorted order. O(log n) all operations.

C++

#include <map>

std::map<int, string> mp;
mp[1] = "one";
mp[3] = "three";
mp[2] = "two";

mp.begin()->first;     // smallest key
mp.rbegin()->first;    // largest key
mp.lower_bound(2);     // iterator to first key >= 2
mp.upper_bound(2);     // iterator to first key > 2

Java

import java.util.TreeMap;

TreeMap<Integer, String> mp = new TreeMap<>();
mp.put(1, "one");
mp.put(3, "three");
mp.put(2, "two");

mp.firstKey();          // smallest key → 1
mp.lastKey();           // largest key → 3
mp.floorKey(2);         // largest key <= 2
mp.ceilingKey(2);       // smallest key >= 2
mp.headMap(3);          // keys < 3
mp.tailMap(2);          // keys >= 2

Python

from sortedcontainers import SortedDict  # pip install sortedcontainers

mp = SortedDict()
mp[1] = "one"
mp[3] = "three"
mp[2] = "two"

mp.keys()[0]          # smallest key
mp.keys()[-1]         # largest key
mp.bisect_left(2)     # index of first key >= 2

C#

using System.Collections.Generic;

SortedDictionary<int, string> mp = new SortedDictionary<int, string>();
mp[1] = "one";
mp[3] = "three";
mp[2] = "two";

// Iterates in sorted key order
foreach (var kvp in mp)
    Console.WriteLine($"{kvp.Key}: {kvp.Value}");

---

11. Sorted Set / Tree Set

Unique elements in sorted order. O(log n) all operations.

C++

#include <set>

std::set<int> st;
st.insert(3);
st.insert(1);
st.insert(5);

*st.begin();           // smallest → 1
*st.rbegin();          // largest → 5
st.lower_bound(2);     // iterator to first >= 2
st.upper_bound(3);     // iterator to first > 3
st.erase(3);

Java

import java.util.TreeSet;

TreeSet<Integer> st = new TreeSet<>();
st.add(3);
st.add(1);
st.add(5);

st.first();         // smallest → 1
st.last();          // largest → 5
st.floor(2);        // largest <= 2 → 1
st.ceiling(2);      // smallest >= 2 → 3
st.headSet(3);      // elements < 3
st.tailSet(3);      // elements >= 3

Python

from sortedcontainers import SortedList  # pip install sortedcontainers

sl = SortedList([3, 1, 5])
sl.add(2)
sl[0]               # smallest → 1
sl[-1]              # largest → 5
sl.bisect_left(2)   # index of first >= 2
sl.remove(3)

C#

using System.Collections.Generic;

SortedSet<int> st = new SortedSet<int>();
st.Add(3);
st.Add(1);
st.Add(5);

st.Min;              // smallest → 1
st.Max;              // largest → 5
st.GetViewBetween(2, 4); // subset [2..4]
st.Remove(3);

---

12. Graph Representations

C++

#include <vector>
#include <unordered_map>

int n = 5; // number of nodes

// Adjacency List (unweighted)
vector<vector<int>> adj(n);
adj[0].push_back(1);
adj[0].push_back(2);

// Adjacency List (weighted)
vector<vector<pair<int,int>>> wadj(n);
wadj[0].push_back({1, 10}); // node 1, weight 10

// Adjacency Matrix
vector<vector<int>> mat(n, vector<int>(n, 0));
mat[0][1] = 1;

// Edge List
vector<pair<int,int>> edges;
edges.push_back({0, 1});

Java

import java.util.*;

int n = 5;

// Adjacency List (unweighted)
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
adj.get(0).add(1);
adj.get(0).add(2);

// Adjacency List (weighted)
List<List<int[]>> wadj = new ArrayList<>();
for (int i = 0; i < n; i++) wadj.add(new ArrayList<>());
wadj.get(0).add(new int[]{1, 10}); // node 1, weight 10

// Adjacency Matrix
int[][] mat = new int[n][n];
mat[0][1] = 1;

Python

from collections import defaultdict

n = 5

# Adjacency List (unweighted)
adj = defaultdict(list)
adj[0].append(1)
adj[0].append(2)

# Adjacency List (weighted)
wadj = defaultdict(list)
wadj[0].append((1, 10))   # (node, weight)

# Adjacency Matrix
mat = [[0] * n for _ in range(n)]
mat[0][1] = 1

# Edge List
edges = [(0, 1), (0, 2)]

C#

using System.Collections.Generic;

int n = 5;

// Adjacency List (unweighted)
List<List<int>> adj = new List<List<int>>();
for (int i = 0; i < n; i++) adj.Add(new List<int>());
adj[0].Add(1);
adj[0].Add(2);

// Adjacency List (weighted)
List<List<(int node, int weight)>> wadj = new List<List<(int, int)>>();
for (int i = 0; i < n; i++) wadj.Add(new List<(int, int)>());
wadj[0].Add((1, 10));

// Adjacency Matrix
int[,] mat = new int[n, n];
mat[0, 1] = 1;

---

13. Binary Tree Node

C++

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

TreeNode* root = new TreeNode(1);
root->left  = new TreeNode(2);
root->right = new TreeNode(3);

Java

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

TreeNode root = new TreeNode(1);
root.left  = new TreeNode(2);
root.right = new TreeNode(3);

Python

class TreeNode:
    def __init__(self, val=0):
        self.val = val
        self.left = None
        self.right = None

root = TreeNode(1)
root.left  = TreeNode(2)
root.right = TreeNode(3)

C#

class TreeNode {
    public int Val;
    public TreeNode Left, Right;
    public TreeNode(int x) { Val = x; }
}

TreeNode root = new TreeNode(1);
root.Left  = new TreeNode(2);
root.Right = new TreeNode(3);

---

14. Trie (Prefix Tree)

C++

struct TrieNode {
    TrieNode* children[26] = {};
    bool isEnd = false;
};

struct Trie {
    TrieNode* root = new TrieNode();

    void insert(string word) {
        TrieNode* node = root;
        for (char c : word) {
            int i = c - 'a';
            if (!node->children[i])
                node->children[i] = new TrieNode();
            node = node->children[i];
        }
        node->isEnd = true;
    }

    bool search(string word) {
        TrieNode* node = root;
        for (char c : word) {
            int i = c - 'a';
            if (!node->children[i]) return false;
            node = node->children[i];
        }
        return node->isEnd;
    }
};

Java

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEnd = false;
}

class Trie {
    TrieNode root = new TrieNode();

    void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (node.children[i] == null)
                node.children[i] = new TrieNode();
            node = node.children[i];
        }
        node.isEnd = true;
    }

    boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (node.children[i] == null) return false;
            node = node.children[i];
        }
        return node.isEnd;
    }
}

Python

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str):
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.is_end = True

    def search(self, word: str) -> bool:
        node = self.root
        for c in word:
            if c not in node.children:
                return False
            node = node.children[c]
        return node.is_end

C#

using System.Collections.Generic;

class TrieNode {
    public Dictionary<char, TrieNode> Children = new();
    public bool IsEnd = false;
}

class Trie {
    TrieNode root = new TrieNode();

    public void Insert(string word) {
        TrieNode node = root;
        foreach (char c in word) {
            if (!node.Children.ContainsKey(c))
                node.Children[c] = new TrieNode();
            node = node.Children[c];
        }
        node.IsEnd = true;
    }

    public bool Search(string word) {
        TrieNode node = root;
        foreach (char c in word) {
            if (!node.Children.ContainsKey(c)) return false;
            node = node.Children[c];
        }
        return node.IsEnd;
    }
}

---

Quick Reference Table

Data Structure	C++	Java	Python	C#
Dynamic Array	vector<T>	ArrayList<T>	list	List<T>
Stack	stack<T>	ArrayDeque<T>	list	Stack<T>
Queue	queue<T>	ArrayDeque<T>	deque	Queue<T>
Deque	deque<T>	ArrayDeque<T>	deque	LinkedList<T>
Linked List	list<T>	LinkedList<T>	deque	LinkedList<T>
Hash Map	unordered_map	HashMap	dict	Dictionary
Hash Set	unordered_set	HashSet	set	HashSet
Sorted Map	map	TreeMap	SortedDict	SortedDictionary
Sorted Set	set	TreeSet	SortedList	SortedSet
Min-Heap	priority_queue (greater)	PriorityQueue	heapq	PriorityQueue
Max-Heap	priority_queue	PriorityQueue (reversed)	heapq (negated)	PriorityQueue