I've always imagined how useful it would be to have a cheat sheet-style comparison of data structures in Java and C++. With such a resource, mastering any programming language would be much easier. After procrastinating for nearly 8–9 years, I've finally put it together. Let’s begin.
Vector
a vector is a dynamic array that can grow and shrink in size automatically while providing fast access to its elements, typically implemented using contiguous memory for efficient indexing.
Operation | C++ | Java ( Vector / ArrayList ) | Time Complexity |
begin() | v.begin() returns iterator to first element | v.firstElement()
Returns the first element | O(1) |
end() | v.end() return iterator to position after last element | No direct equivalent ( can use v.lastElement()) | O(1) |
size() - return number of elements | v.size() | v.size() | O(1) |
empty() - checks if empty
| v.empty() | v.isEmpty() | O(1) |
at() | v.at( index ) return element at index | v.get( index ) | O( 1 ) |
assign() | v.assign(n, val) replaces elements | No direct equivalent - v.clear() + v.addAll() | O(n) |
push_back() - add element in last | v.push_back(vao) | v.add(val) | O(1) |
pop_back() - remove last element | v.pop_back() | v.remove( v.size() - 1) | O(1) |
insert() - element add in a position | v.insert(it, val) | v.add( index, val ) | O(n) |
erase() - removes element at position
| v.erase(it) | v.remove(index) | O(n) |
clear() | v.clear() | v.clear() | O(n) |
LinkedList
Both C++ std::list and Java LinkedList implement a double linked list, making them efficient for insertions and deletions but slower for random access.
Operation | C++ ( list ) | Java ( LinkedList ) | Time Complexity |
Add element at the end | list.push_back(val) | list.add( val ) | O(1) |
Add an element at the front | list.push_front(val) | list.addFirst(val) | O(1) |
Insert at position | list.insert( it, val ) | list.add( index, val ) | O(n) |
Remove last element | list. pop_back() | list.removeLast() | O(1) |
Remove first element | list.pop_front() | list.removeFirst() | O(1) |
Remove element by value | list.remove(val) | list.remove(Object o) | O(n) |
Remove element by index | No operation | list.remove(index) | O(n) |
Access first element | list.front() | list.getFirst() | O(1) |
Access last element | list.back() | list.getLast() | O(1) |
Access element by index | No operation | list.get( index ) | O(n) |
Check size | list.size() | list.size() | O(1) |
Check if empty | list.empty() | list.isEmpty() | O(1) |
Reverse list | list.reverse() | Collections.reverse(list); | O(n) |
Sort list | list.sort() | Collections.sort(list) | O(n log n) |
Clear list | list.clear() | list.clear() | O(n) |
Iterate through elements | for(auto it = list.begin(), it != list.end(); ++it) | for( E item: list) | O(n) |
Queue
A Queue is a linear data structure that follows the FIFO (First In, First Out) principle. This means that elements are added at the back (enqueue) and removed from the front (dequeue), just like a real-world queue (e.g., a line at a ticket counter).
In Java Linked list worked as Queue and C++ there is dedicated Queue in STL
Operation | C++ | Java ( LinkedLIst ) | Time Complexity |
Enqueue ( Add to back ) | q.push(val) | q.add(val) or q.offer( val ) | O(1) |
Dequeue ( remove from front ) | q.pop(); | q.pop() or q.remove() | O(1) |
Access front element | q.front() | q.peek() | O(1) |
Access last element | q.back() | No operation | O(1) |
Check if queue is empty | q.empty() | q.isEmpty() | O(1) |
Check queue size | q.size() | q.size() | O(n) |
iteration | while(!q.empty() ) | for( E item: q ) | O(n) |
Deque
A Deque (pronounced "deck") stands for Double-Ended Queue. It is a linear data structure that allows insertions and deletions from both the front and the back, unlike a regular queue which follows FIFO (First-In-First-Out).
Operation | C++ | Java | Time Complexity |
Declaration | deque < int > dq; | Deque<Integer> dq = new ArrayDeque<>(); | O(1) |
Insert at front | dq.push_front(val) | dq.addFirst(val) | O(1) |
Insert at back | dq.push_back(val) | dq.addLast(val) | O(1) |
Remove from front | dq.pop_front() | dq.removeFirst(); | O(1) |
Remove from back | dq.pop_back() | dq.removeLast | O(1) |
Access front | dq.front() | dq.getFirst(); | O(1) |
Access back | dq.back() | dq.getLast(); | O(1) |
Check size | dq.size() | dq.size() | O(1) |
Check if empty | dq.empty() | dq.isEmpty() | O(1) |
Clear deque | dq.clear() | dq.clear() | O(n) |
Stack
A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. This means that the last element added to the stack is the first one to be removed—similar to a stack of plates, where you add new plates on top and remove the topmost plate first.
Operation | C++ | Java | Time Complexity |
Declaration | stack< int > st; | Stack<Integer> st = new Stack<>() | O(1) |
Push | st.push(x) | st.push(x); | O(1) |
Pop | st.pop() | st.pop() | O(1) |
Top element | st.top(); | st.peek() | O(1) |
size | st.size() | st.size() | O(1_ |
empty | st.empty() | st.isEmpty() | O(1) |
clear | st.clear() | st.clear() | O(n) |
