Sunday, February 16, 2025

Data structure in C++ vs Java - Part 1

 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)