Everything You Need to Know About Data Structures
- This article covers the data structure topics which is important to ace a data structure interview.
- The study materials mainly include tutorialspoint, techiedelight, and G4G.
- The code snippets are written in C/C++.
Highlights
- Big-O summary: bigocheatsheet
- Inserting and deleting element of array
- Height, depth and level of a tree.
Table of Contents
- Arrays
- String
- Linked Lists
- Stack
- Queue
- Trees
- Heap
- Hashing
- Graph
- Matrix
Arrays
Basic concepts
- Array is a container which can hold a fix number of items and these items should be of the same type. Each position in the array has an index, starting at 0.
- Arrays are extremely efficient in accessing values because all the elements are stored in contiguous spaces in memory. This way, the computer knows exactly where to look to find the information.
- When you define the size of the array (no matter fill the array or not), all of that space in memory is “reserved”, thus it is not memory-efficient. Arrays are recommended when you know how many elements required beforehand.
Operations
- Traverse − print all the array elements one by one.
- Insertion − Adds an element at the given index.
- If the array is not full: move all the elements located to the right of the insertion slot, one index to the right.
- If the array is full: you need to create a new, larger array and manually copy all the elements into this new array.
- Inserting at the end of the array is very efficient, constant time O(1).
int array[10] = {1,2,3,4};
int position = 2; //position where to insert
int value = 0; //value to insert
int n = 4; // current number of elements
for (int c = n - 1; c >= position; c--)
array[c+1] = array[c]; //move elements from left to right, 3->4, 2->3
array[position] = value;
//array now is 1,2,0,3,4- Deletion − Deletes an element at the given index.
- You can’t just delete the element and leave that space empty
- You have to move the elements that come after the element that you want to delete one index the left.
- Removing at the end of the array is very efficient because you only delete the last element.
int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
// delete 3 (index 2)
for (int i = 2; i < 8; ++i)
array[i] = array[i + 1]; // move elements from right to left- Search − Searches an element using the given index or by the value
- If you know where it’s located, use the index.
- If you don’t know the index and your data is sorted, you can use Binary Search to optimize the search.
- If you don’t know the index and your data is not sorted, you will need to search through every element in the array.
- Update − Updates an element at the given index.
Strings
Basic concepts
- String is a sequence of characters that is treated as a single data item and terminated by null character
'\0'. - C language does not support strings as a data type. A string is actually one-dimensional array of characters in C language.
char name1[6] = "Study"; // '\0' added automatically
char name2[10] = {'L','e','s','s','o','n','s','\0'}; // '\0' must be added explicitlycout << sizeof(name1); //6
cout << sizeof(name2); //10
cout << name1; //Study
cout << name2; //Lessons
Linked Lists
Basic concepts
- A linked list is a sequence of data structures, which are connected together via links. Linked list can be visualized as a chain of nodes, where every node points to the next node.e.g:
- Following are the various types of linked list.
- Simple Linked List − Item navigation is forward only.
- Doubly Linked List − Items can be navigated forward and backward.
- Circular Linked List − Last item contains link of the first element as next and the first element has a link to the last element as previous.
Representation in C++
struct Node {
int val; //or int data;
Node *next;
Node(int x) : val(x), next(NULL) {}
};Difference between array and linked list
- Array means contiguous memory. It can exist in any memory section be it Data or Stack or Heap. Linked List means non-contiguous linked memory. It can exist in any memory section be it Heap or Data or Stack.
- Random access is not allowed in linked list, so we cannot do binary search with linked lists.
- Extra memory space for a pointer is required with each element of the list.
- Arrays have better cache locality that can make a pretty big difference in performance.
- Linked list has dynamic size and it is ease for operations of insertion/deletion
Basic Operations
Note: Once it is needed to change the head, there are 3 ways to implement: Ref
- Make head pointer global
- Return head pointer
- (Recommended) Use Double Pointer: This approach follows the simple C rule: if you want to modify local variable of one function inside another function, pass pointer to that variable. So we can pass pointer to the head pointer to modify the head pointer in our function where the head will change.
- Insertion − Adds an element at the given position of the list.
- To insert at the head, let
temp1point to the head, change head to the new node. - To insert at other position, let temp2 points to the previous of n,
//1,2,3,4 insert(5, 3) = > 1,2,5,3,4
void insert(Node **pointerToHead, int data, int n) (position starts with 1)
{
Node *temp1 = (Node*)malloc(sizeof(Node)); // or new Node();
temp1->data = data;
temp1->next = NULL;
if (n == 1){ // works even if head is empty
temp1->next = *pointerToHead;
*pointerToHead = temp1;
return;
}
Node *temp2 = *pointerToHead;
for (int i = 0; i < n - 2; i++){ // find the previous position of n, set temp2 to element 2
temp2 = temp2->next;
}
temp1->next = temp2->next; // temp2->next is element 4
temp2->next = temp1; // set new node as next element of element 2
}- Deletion − Deletes an element at the given position (or key) of the list
- To delete the head, let
temp1point to the head, change head to point to the next element of head, deletetemp1. - To delete the non-head element, let
temp1point to the n-1th node, lettemp2point to the next oftemp1, lettemp1point to the next oftemp2, deletetemp2.
// 1,2,3,4 Delete(3) => 1,2,4 (position starts with 1)
void delete(Node **pointerToHead, int n)
{
Node* temp1 = *pointerToHead;
if (n == 1){
*pointerToHead = temp1->next;
free(temp1); // or delete temp1;
return;
}
int i = 0;
for (int i = 0; i < n - 2; i++){ // temp1 points to n-1 th node, element 2
temp1 = temp1->next;
}
Node *temp2 = temp1->next;
temp1->next = temp2->next;
free(temp2); // or delete temp2; in C++
}- Print − Print the complete list.
void printList(Node *node){
while(node != NULL){
cout << node->data << " ";
node = node->next;
}
cout << endl;
}- Search − Searches an element using the given key, it can be implemented with the similar code as
printList()above.
Stack
Basic concepts
- Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).
- There are mainly two ways to implement a stack.
- Using array: Easy to implement. Memory is saved as pointers are not involved. It is not dynamic. It doesn’t grow and shrink depending on needs at runtime.
- Using linked list: It can grow and shrink according to the needs at runtime. It requires extra memory due to involvement of pointers.
Basic Operations
Get Larry | Peng Yang’s stories in your inbox
Join Medium for free to get updates from this writer.
Note: arrays are used to implement the stack here.
- Class declaration
#define MAX 1000
class Stack
{
int top;
public:
int a[MAX]; //Maximum size of Stack
Stack() { top = -1; } // [-1, MAX-1]
bool push(int x);
int pop();
int top();
bool isEmpty();
bool isFull();
};- Push(): Adds an item in the stack. If the stack is full, then it is said to be an Overflow condition.
bool Stack::push(int x)
{
if (top >= (MAX-1)) // or simply, (top == MAX-1)
{
cout << "Stack Overflow";
return false;
}
else
{
a[++top] = x;
cout << x << " pushed into stack\n";
return true;
}
}- Pop(): Removes an item from the stack. The items are popped in the reversed order in which they are pushed. If the stack is empty, then it is said to be an Underflow condition.
int Stack::pop()
{
if (top < 0) // or simply call isEmpty()
{
cout << "Stack Underflow";
return 0;
}
else
{
int x = a[top--];
return x;
}
}- Top (or Peek): Returns top element of stack.
int Stack::top() {
if (isEmpty()) return 0;
return a[top];
}- isEmpty(): Returns true if stack is empty, else false.
bool Stack::isEmpty(){
return (top < 0);
}- (Only in array implementation) isFull() − check if stack is full.
bool isFull() {
if(top == MAX-1)
return true;
else
return false;
}Queues
Basic concepts
- A Queue is a linear structure which follows a particular order in which the operations are performed. The order is First In First Out (FIFO).
- A queue can also be implemented using arrays and linked lists.
Basic Operations
Note: see detailed implementation here.
- enqueue() : add (store) an item to the queue.
- dequeue() : remove (access) an item from the queue.
- peek() : Gets the element at the front of the queue without removing it.
- isEmpty() : Checks if the queue is empty.
- (Only in array implementation) isFull() : Checks if the queue is full.
C++ STL
- C++ STL provides std::queue (
include <queue>) templated class which is restricted to only enqueue and dequeue operations, it also provides std::list which has push_back and pop_front operations with LIFO semantics.
Trees
Basic concepts
- Binary tree has a special condition that each node can have a maximum of two children. A binary tree has the benefits of both an ordered array and a linked list as search is as quick as in a sorted array and insertion or deletion operation are as fast as in linked list.
- Height, depth and level of a tree.
- Height of a node (node->leaf): The height of a node is the number of edges on the longest downward path between that node and a leaf. Height of leaf node is 0. Height of the root is 1 (In some books it is 0).
- Height of a tree (root->leaf) is the number of edges on the longest downward path between the root and a leaf. The height of a tree is the height of its root. Height of a tree with single node is considered as 1.
- Depth (node->root): The depth of a node is the number of edges from the node to the tree’s root node. Depth of root node is 0.
- Level (node->root + 1 or Depth +1): The level of a node is defined by 1 + the number of connections between the node and the root. It starts from 1 and the level of the root is 1.
- If there are
Nnodes, there will be exactlyN-1links or edges. - Properties of binary tree.
- The maximum number of nodes at level ‘l’ of a binary tree is
2^(l-1).1, 2, 4, 8 … 2^(l-1). - Maximum number of nodes in a binary tree of height ‘h’ is
2^h -1.1 + 2 + 4 + .. + 2^(h-1) = 2^h-1.
- Types of binary tree.
- Binary Search Tree (BST) exhibits a special behavior. A node’s left child must have a value less than its parent’s value and the node’s right child must have a value greater than its parent value.
Representation in C++
struct Node {
int val; // or int data;
Node *left;
Node *right;
Node(int x) : val(x), left(NULL), right(NULL) {}
};Basic operations (BST)
- Insert − Inserts an element in a tree/create a tree.
Node* insert(Node *root, int data) {
{
if(root == NULL) {
Node *newNode = new Node;
newNode->left = newNode->right = NULL;
newNode->data = data;
return newNode;
}
if(data > root->data){
root->right = insert(root->right, data);
}else if (data < root->data){
root->left = insert(root->left, data);
} // return the (unchanged) node pointer
return root;
}
- Search − Searches an element in a tree.
Node* search(Node *root, int key)
{
// Base Cases: root is null or key is present at root
if (root == NULL || root->data == key)
return root;
// Key is greater than root's key
if (root->data < key)
return search(root->right, key);
// Key is smaller than root's key
return search(root->left, key);
}- Delete − Deletes an element in a tree.
/* Given a binary search tree and a key,
this function deletes the key and returns the new root */
Node* deleteNode(Node *root, int key)
{
// base case
if (root == NULL) return root;
if (key < root->data)
root->left = deleteNode(root->left, key);
else if (key > root->data)
root->right = deleteNode(root->right, key);
// if key is same as root's key
// then This is the node to be deleted
else
{
// node with only one child or no child
if (root->left == NULL)
{
Node *temp = root->right;
free(root); // or delete root;
return temp;
}
else if (root->right == NULL)
{
Node *temp = root->left;
free(root); // or delete root;
return temp;
}
// node with two children:
// Get the inorder successor (smallest
// in the right subtree)
Node *temp = minValueNode(root->right);
// Copy the inorder successor's content to this node
root->data = temp->data;
// Delete the inorder successor
root->right = deleteNode(root->right, temp->data);
}
return root;
}- Preorder Traversal − Traverses a tree in a pre-order manner.
void preorder (Node *root){
if(root == NULL) return;
cout << root->data;
preorder(root->left);
preorder(root->right);
}- Inorder Traversal − Traverses a tree in an in-order manner.
void inorder (Node *root){
if(root == NULL) return;
inorder(root->left);
cout << root->data;
inorder(root->right);
}- Postorder Traversal − Traverses a tree in a post-order manner.
void postorder (Node *root){
if(root == NULL) return;
postorder(root->left);
postorder(root->right);
cout << root->data;
}Heap
Basic concepts
- A Heap is a special Tree-based data structure in which the tree is a complete binary tree. Heaps can be of two types:
- Max-Heap: The value of the root node must be greatest among the keys present at all of its children. The same property must be recursively true for all sub-trees in that Binary Tree.
- Min-Heap: The value of the root node must be minimum among the keys present at all of its children. The same property must be recursively true for all sub-trees in that Binary Tree.
- getMini(): It returns the root element of Min Heap. O(1).
- extractMin(): Removes the minimum element from MinHeap. O(Logn). It needs to maintain the heap property (by calling heapify()) after removing root.
- decreaseKey(): Decreases value of key. O(Logn). We need to traverse up to fix the violated heap property.
- insert(): Inserting a new key. O(Logn). We add a new key at the end of the tree. We need to traverse up to fix the violated heap property.
- delete(): Deleting a key. O(Logn). We replace the key to be deleted with minus infinite by calling decreaseKey(). After decreaseKey(), the minus infinite value must reach root, so we call extractMin() to remove the key.
Hashing
- Hashing is an important Data Structure which is designed to use a special function called the Hash function which is used to map a given value with a particular key for faster access of elements. The efficiency of mapping depends of the efficiency of the hash function used.
- Hash Function: A hash function maps a big number or string to a small integer that can be used as index in hash table. Given a collection of items, a hash function that maps each item into a unique slot is referred to as a perfect hash function.
- A hash table is a collection of items which are stored in such a way as to make it easy to find them later. Each position of the hash table, often called a slot, can hold an item and is named by an integer value starting at 0.
- The item to be passed to hash function is called key and the returned value of the hash function is called hash code.
- When two items hash to the same slot, we must have a systematic method for placing the second item in the hash table. This process is called collision resolution. Following are the ways to handle collisions:
- Chaining: The idea is to make each cell of hash table point to a linked list of records that have same hash function value. Chaining is simple, but requires additional memory outside the table.
2. Open Addressing: It tries to find the next open slot or address in the hash table and store the record there. e.g: Linear Probing: we linearly probe for next slot.
- Following are the basic primary operations of a hash table.
- Search − Searches an element in a hash table.
- Insert − Inserts an element in a hash table.
- delete − Deletes an element from a hash table.
Graph
Basic concepts, Terminology and Representations, Link
- A graph is a pictorial representation of a set of objects where some pairs of objects are connected by links. The interconnected objects are represented by points termed as vertices (also called nodes), and the links that connect the vertices are called edges (also called arcs).
- Weight: Edges may be weighted to show that there is a cost to go from one vertex to another.
- Adjacency − Two nodes or vertices are adjacent if they are connected to each other through an edge.
- Path: A path in a graph is a sequence of vertices that are connected by edges.
- Cycle: A cycle in a directed graph is a path that starts and ends at the same vertex
- Edges may be one-way or two-way. If the edges in a graph are all one-way, we say that the graph is a directed graph or a digraph.
- There are two well-known implementations of a graph, the adjacency matrix, and the adjacency list.
- Adjacency matrix: each of the rows and columns represent a vertex in the graph. The value that is stored in the cell at the intersection of row
vand columnwindicates if there is an edge from vertexvto vertexw.
2. Adjacency list
- Following are basic primary operations of a Graph
- Add Vertex − Adds a vertex to the graph.
- Add Edge − Adds an edge between the two vertices of the graph.
- Display Vertex − Displays a vertex of the graph.
- Depth First Traversal − Traverses a graph in a depthward motion and uses a stack to remember to get the next vertex to start a search.
- Breadth First Traversal − Traverses a graph in a breadthward motion and uses a queue to remember to get the next vertex to start a search.








