Data Structures




Topics:



Overview:



Linked List:











Singly Linked List:



  1. Introduction to Linked List

  2. Linked List vs Array

  3. Linked List Insertion

  4. Linked List Deletion (Deleting a given key)

  5. Linked List Deletion (Deleting a key at given position)

  6. A Programmer?s approach of looking at Array vs. Linked List

  7. Find Length of a Linked List (Iterative and Recursive)

  8. How to write C functions that modify head pointer of a Linked List?

  9. Swap nodes in a linked list without swapping data

  10. Reverse a linked list

  11. Merge two sorted linked lists

  12. Merge Sort for Linked Lists

  13. Reverse a Linked List in groups of given size

  14. Detect and Remove Loop in a Linked List

  15. Add two numbers represented by linked lists | Set 1

  16. Rotate a Linked List

  17. Generic Linked List in C


Circular Linked List:



  1. Circular Linked List Introduction and Applications,

  2. Circular Singly Linked List Insertion<

  3. Circular Linked List Traversal

  4. Split a Circular Linked List into two halves

  5. Sorted insert for circular linked list


Doubly Linked List:



  1. Doubly Linked List Introduction and Insertion

  2. Delete a node in a Doubly Linked List

  3. Reverse a Doubly Linked List

  4. The Great Tree-List Recursion Problem.

  5. QuickSort on Doubly Linked List

  6. Merge Sort for Doubly Linked List


All Articles of Linked List

Quiz on Linked List

Coding Practice on Linked List

Recent Articles on Linked List


Stack:



  1. Introduction to Stack

  2. Infix to Postfix Conversion using Stack

  3. Evaluation of Postfix Expression

  4. Reverse a String using Stack

  5. Implement two stacks in an array

  6. Check for balanced parentheses in an expression

  7. Next Greater Element

  8. Reverse a stack using recursion

  9. Sort a stack using recursion

  10. The Stock Span Problem

  11. Design and Implement Special Stack Data Structure

  12. Implement Stack using Queues

  13. Design a stack with operations on middle element

  14. How to efficiently implement k stacks in a single array?

  15. Sort a stack using recursion


Quiz on Stack

All Articles on Stack

Coding Practice on Stack

Recent Articles on Stack


�


Queue:



  1. Queue Introduction and Array Implementation

  2. Linked List Implementation of Queue

  3. Applications of Queue Data Structure

  4. Priority Queue Introduction

  5. Deque (Introduction and Applications)

  6. Implementation of Deque using circular array

  7. Implement Queue using Stacks

  8. Find the first circular tour that visits all petrol pumps

  9. Maximum of all subarrays of size k

  10. An Interesting Method to Generate Binary Numbers from 1 to n

  11. How to efficiently implement k Queues in a single array?


Quiz on Queue

All Articles on Queue

Coding Practice on Queue

Recent Articles on Queue


�


Binary Tree:



  1. Binary Tree Introduction

  2. Binary Tree Properties

  3. Types of Binary Tree

  4. Handshaking Lemma and Interesting Tree Properties

  5. Enumeration of Binary Tree

  6. Applications of tree data structure

  7. Tree Traversals

  8. BFS vs DFS for Binary Tree

  9. Level Order Tree Traversal

  10. Diameter of a Binary Tree

  11. Inorder Tree Traversal without Recursion

  12. Inorder Tree Traversal without recursion and without stack!

  13. Threaded Binary Tree

  14. Maximum Depth or Height of a Tree

  15. If you are given two traversal sequences, can you construct the binary tree?

  16. Clone a Binary Tree with Random Pointers

  17. Construct Tree from given Inorder and Preorder traversals

  18. Maximum width of a binary tree

  19. Print nodes at k distance from root

  20. Print Ancestors of a given node in Binary Tree

  21. Check if a binary tree is subtree of another binary tree

  22. Connect nodes at same level


Quiz on Binary Tree

Quiz on Binary Tree Traversals

All articles on Binary Tree

Coding Practice on Binary Tree

Recent Articles on Tree


Binary Search Tree:












  1. Search and Insert in BST

  2. Deletion from BST

  3. Minimum value in a Binary Search Tree

  4. Inorder predecessor and successor for a given key in BST

  5. Check if a binary tree is BST or not

  6. Lowest Common Ancestor in a Binary Search Tree.

  7. Inorder Successor in Binary Search Tree

  8. Find k-th smallest element in BST (Order Statistics in BST)

  9. Merge two BSTs with limited extra space

  10. Two nodes of a BST are swapped, correct the BST

  11. Floor and Ceil from a BST

  12. In-place conversion of Sorted DLL to Balanced BST

  13. Find a pair with given sum in a Balanced BST

  14. Total number of possible Binary Search Trees with n keys

  15. Merge Two Balanced Binary Search Trees

  16. Binary Tree to Binary Search Tree Conversion


Quiz on Binary Search Trees

Quiz on Balanced Binary Search Trees

All Articles on Binary Search Tree

Coding Practice on Binary Search Tree

Recent Articles on BST


Heap:



  1. Binary Heap

  2. Why is Binary Heap Preferred over BST for Priority Queue?

  3. Binomial Heap

  4. Fibonacci Heap

  5. Heap Sort

  6. K?th Largest Element in an array

  7. Sort an almost sorted array/

  8. Tournament Tree (Winner Tree) and Binary Heap


All Articles on Heap

Quiz on Heap

Coding Practice on Heap

Recent Articles on Heap


Hashing:



  1. Hashing Introduction

  2. Separate Chaining for Collision Handling

  3. Open Addressing for Collision Handling

  4. Print a Binary Tree in Vertical Order

  5. Find whether an array is subset of another array

  6. Union and Intersection of two Linked Lists

  7. Find a pair with given sum

  8. Check if a given array contains duplicate elements within k distance from each other

  9. Find Itinerary from a given list of tickets

  10. Find number of Employees Under every Employee


Quiz on Hashing

All Articles on Hashing

Coding Practice on Hashing

Recent Articles on Hashing


�


Graph:


Introduction, DFS and BFS:



  1. Graph and its representations

  2. Breadth First Traversal for a Graph

  3. Depth First Traversal for a Graph

  4. Applications of Depth First Search

  5. Applications of Breadth First Traversal

  6. Detect Cycle in a Directed Graph

  7. Detect Cycle in a an Undirected Graph

  8. Detect cycle in an undirected graph

  9. Longest Path in a Directed Acyclic Graph

  10. Topological Sorting

  11. Check whether a given graph is Bipartite or not

  12. Snake and Ladder Problem

  13. Minimize Cash Flow among a given set of friends who have borrowed money from each other

  14. Boggle (Find all possible words in a board of characters)

  15. Assign directions to edges so that the directed graph remains acyclic


All Articles on Graph Data Structure

Quiz on Graph

Quiz on Graph Traversals

Quiz on Graph Shortest Paths

Quiz on Graph Minimum Spanning Tree

Coding Practice on Graph

Recent Articles on Graph


�


Advanced Data Structure:


Advanced Lists:



  1. Memory efficient doubly linked list

  2. XOR Linked List ? A Memory Efficient Doubly Linked List | Set 1

  3. XOR Linked List ? A Memory Efficient Doubly Linked List | Set 2

  4. Skip List | Set 1 (Introduction)

  5. Self Organizing List | Set 1 (Introduction)

  6. Unrolled Linked List | Set 1 (Introduction)


Segment Tree:



  1. Segment Tree | Set 1 (Sum of given range)

  2. Segment Tree | Set 2 (Range Minimum Query)

  3. Lazy Propagation in Segment Tree

  4. Persistent Segment Tree | Set 1 (Introduction)


All articles on Segment Tree

Trie:



  1. Trie | (Insert and Search)

  2. Trie | (Delete)

  3. Longest prefix matching ? A Trie based solution in Java

  4. Print unique rows in a given boolean matrix

  5. How to Implement Reverse DNS Look Up Cache?

  6. How to Implement Forward DNS Look Up Cache?


All Articles on Trie

Binary Indexed Tree:



  1. Binary Indexed Tree

  2. Two Dimensional Binary Indexed Tree or Fenwick Tree

  3. Binary Indexed Tree : Range Updates and Point Queries

  4. Binary Indexed Tree : Range Update and Range Queries


All Articles on Binary Indexed Tree

Suffix Array and Suffix Tree:



  1. Suffix Array Introduction

  2. Suffix Array nLogn Algorithm

  3. kasai?s Algorithm for Construction of LCP array from Suffix Array

  4. Suffix Tree Introduction

  5. Ukkonen?s Suffix Tree Construction ? Part 1

  6. Ukkonen?s Suffix Tree Construction ? Part 2

  7. Ukkonen?s Suffix Tree Construction ? Part 3

  8. Ukkonen?s Suffix Tree Construction ? Part 4,

  9. Ukkonen?s Suffix Tree Construction ? Part 5

  10. Ukkonen?s Suffix Tree Construction ? Part 6

  11. Generalized Suffix Tree

  12. Build Linear Time Suffix Array using Suffix Tree

  13. Substring Check

  14. Searching All Patterns

  15. Longest Repeated Substring,

  16. Longest Common Substring, Longest Palindromic Substring




All Articles on Suffix Tree

AVL Tree:












  1. AVL Tree | Set 1 (Insertion)

  2. AVL Tree | Set 2 (Deletion)

  3. AVL with duplicate keys


Splay Tree:



  1. Splay Tree | Set 1 (Search)

  2. Splay Tree | Set 2 (Insert)


B Tree:



  1. B-Tree | Set 1 (Introduction)

  2. B-Tree | Set 2 (Insert)

  3. B-Tree | Set 3 (Delete)


Red-Black Tree:



  1. Red-Black Tree Introduction

  2. Red Black Tree Insertion.

  3. Red-Black Tree Deletion

  4. Program for Red Black Tree Insertion




All Articles on Self-Balancing BSTs


�


K Dimensional Tree:



  1. KD Tree (Search and Insert)

  2. K D Tree (Find Minimum)

  3. K D Tree (Delete)


Others:




    1. Treap (A Randomized Binary Search Tree)

    2. Ternary Search Tree

    3. Interval Tree

    4. Implement LRU Cache

    5. Sort numbers stored on different machines

    6. Find the k most frequent words from a file

    7. Given a sequence of words, print all anagrams together

    8. Tournament Tree (Winner Tree) and Binary Heap

    9. Decision Trees ? Fake (Counterfeit) Coin Puzzle (12 Coin Puzzle)

    10. Spaghetti Stack

    11. Data Structure for Dictionary and Spell Checker?

    12. Cartesian Tree

    13. Cartesian Tree Sorting

    14. Sparse Set

    15. Centroid Decomposition of Tree

    16. Gomory-Hu Tree



Recent Articles on Advanced Data Structures.


Array:





      1. Search, insert and delete in an unsorted array

      2. Search, insert and delete in a sorted array

      3. Write a program to reverse an array

      4. Leaders in an array

      5. Given an array A[] and a number x, check for pair in A[] with sum as x

      6. Majority Element

      7. Find the Number Occurring Odd Number of Times

      8. Largest Sum Contiguous Subarray

      9. Find the Missing Number

      10. Search an element in a sorted and pivoted array

      11. Merge an array of size n into another array of size m+n

      12. Median of two sorted arrays

      13. Program for array rotation

      14. Reversal algorithm for array rotation

      15. Block swap algorithm for array rotation

      16. Maximum sum such that no two elements are adjacent

      17. Sort elements by frequency | Set 1

      18. Count Inversions in an array




All Articles on Array

Coding Practice on Array

Quiz on Array

Coding Practice on Array

Recent Articles on Array


�


Matrix:





      1. Search in a row wise and column wise sorted matrix

      2. Print a given matrix in spiral form

      3. A Boolean Matrix Question

      4. Print unique rows in a given boolean matrix

      5. Maximum size square sub-matrix with all 1s

      6. Print unique rows in a given boolean matrix

      7. Inplace M x N size matrix transpose | Updated

      8. Dynamic Programming | Set 27 (Maximum sum rectangle in a 2D matrix)

      9. Strassen?s Matrix Multiplication

      10. Create a matrix with alternating rectangles of O and X

      11. Print all elements in sorted order from row and column wise sorted matrix

      12. Given an n x n square matrix, find sum of all sub-squares of size k x k

      13. Count number of islands where every island is row-wise and column-wise separated

      14. Find a common element in all rows of a given row-wise sorted matrix




All Articles on Matrix

Coding Practice on Matrix

Recent Articles on Matrix.


�


Misc:





      1. Commonly Asked Data Structure Interview Questions | Set 1

      2. A data structure for n elements and O(1) operations

      3. Expression Tree




You can create a new DS topic and discuss it with other geeks using our portal PRACTICE. See recently added problems on Data Structures on PRACTICE.











My Personal Notes
arrow_drop_up