Data Structures (old)

This list contains the data structures that could be implemented/explained.

---

1. Beginner:

Arrays and Lists; operations & related DS

• Array (Both sorted and unsorted)

Title	c	cpp	java	python	blog post
Insertion in array
Deletion in array		delete-array-cpp
Array doubling and amortized complexity		array-doubling-cpp
Dynamic Arrays		dynamic-arrays-cpp
Vector (C++ STL)		vector-cpp
Array Rotation		array-rotation-cpp

• Linked Lists (Both sorted and unsorted)

Title	c	cpp	java	python	blog post
Insertion, Deletion, Search, Traversal, Reversal		list-implementation-cpp
Reverse Linked List		reverse-ll-cpp
Add numbers using Linked Lists		add-ll-cpp
Multiply numbers using Linked Lists		multiply-ll-cpp
Merge Sort using Linked Lists		merge-sort-ll-cpp
List using STL (C++)		list-stl-cpp
Forward List in STL (C++)		forward-list-cpp
Floyd Cycle Detection			ll-cycle-detect-java
Partition Linked Lists around a value			ll-partition-java
Check whether linked list is a palindrome			ll-palindrome-java
Check for intersection of two linked lists			intersection-ll-java
Delete middle node from Linked List			delete-middle-java

---

Stacks

Title	c	cpp	java	python	blog post
Stack using arrays		stack-array-cpp
Stack using linked lists		stack-ll-cpp
STL stack (C++)		stl-stack
Infix to Postfix converstion		infix-to-postfix-cpp
Implement Stack using queues
Stack that supports getMin in O(1) time and O(1) space

---

Queues

Title	c	cpp	java	python	blog post
Queue using arrays		queue-array-cpp
Queue using linked lists		queue-ll-cpp
STL queue (C++)		stl-queue
Implement queue using stacks
Circular queue implementation
Doubly ended queue implementation
Max Priority Queue		max-pq-cpp
Min Priority Queue		min-pq-cpp
STL priority queue (C++)		stl-pq

---

Hashing

Title	c	cpp	java	python	blog post
Implementation of HashMap		hashmap-cpp

---

2. Intermediate

Tree related Data Structures

Binary Trees, BST, Generic Trees

Title	c	cpp	java	python	blog post
Construct binary tree from traversal		construct-binary-tree-cpp
Diameter of binary tree		dia-btree-cpp
Generic Tree implementation		generic-tree-cpp	generic-tree-java
Binary Search Tree implementation		bst-cpp
Convert linked list to BST		ll-to-bst-cpp
Largest BST in a binary tree		largest-bst-cpp
Morris traversal of a tree		morris-traversal-cpp
Check whether two n-ary trees are mirrors		check-nary-trees
STL map (C++)		stl-map
STL set (C++)		stl-set
Check subtree of a tree		check-subtree-cpp
Least Common Ancestor algorithms (Naive, Binary Lifting, RMQ)		lca-algos-cpp

---

Heaps

Title	c	cpp	java	python	blog post
Heap Implementation		heap-cpp
STL priority queue (max heap)		stl-pq-max
STL priority queue (min heap)		stl-pq-min
Merge two heaps		merge-heaps-cpp

---

Disjoint Set Union

Title	c	cpp	java	python	blog post
Disjoint Set Union implementation

---

Segment Trees

Title	c	cpp	java	python	blog post
Segment Tree implementation		seg-tree-cpp
Lazy Propagation in Segment Tree		seg-lazy-cpp

---

Tries

Title	c	cpp	java	python	blog post
Trie implementation		trie-cpp
Pattern matching with trie DS		pattern-matching-trie-cpp

---

Additional features in C++ :

• Iterators and ranges
• Policy-based data structures

---

3. Advanced (Not a priority for those studying for Interns/Placements):

Title	c	cpp	java	python	blog post
Binary Indexed Trees		bit-cpp
Interval Tree
Suffix Array
Sparse Table
Suffix Automation
Suffix Tree

---

4. Expert (Not a priority for those studying for Interns/Placements):

• Heavy-light decomposition
• Treap / Cartesian Tree
• K-d Tree
• Link-cut Tree
• Splay Tree
• Palindromic Tree
• Rope, Dancing Links
• Radix Tree
• Dynamic Suffix Array

---

References:

1. Data Structures List GFG
2. CodeChef Discuss: List of DS Algo
3. Quora: List of DS that a competitive programmer must know