Data Structures Tutorial

Data Structures Tutorial Asymptotic Notation Structure and Union Array Data Structure Linked list Data Structure Type of Linked list Advantages and Disadvantages of linked list Queue Data Structure Implementation of Queue Stack Data Structure Implementation of Stack Sorting Insertion sort Quick sort Selection sort Heap sort Merge sort Bucket sort Count sort Radix sort Shell sort Tree Traversal of the binary tree Binary search tree Graph Spanning tree Linear Search Binary Search Hashing Collision Resolution Techniques

Misc Topic:

Priority Queue in Data Structure Deque in Data Structure Difference Between Linear And Non Linear Data Structures Queue Operations In Data Structure About Data Structures Data Structures Algorithms Types of Data Structures Big O Notations Introduction to Arrays Introduction to 1D-Arrays Operations on 1D-Arrays Introduction to 2D-Arrays Operations on 2D-Arrays Strings in Data Structures String Operations Application of 2D array Bubble Sort Insertion Sort Sorting Algorithms What is DFS Algorithm What Is Graph Data Structure What is the difference between Tree and Graph What is the difference between DFS and BFS Bucket Sort Dijkstra’s vs Bellman-Ford Algorithm Linear Queue Data Structure in C Stack Using Array Stack Using Linked List Recursion in Fibonacci Stack vs Array What is Skewed Binary Tree Primitive Data Structure in C Dynamic memory allocation of structure in C Application of Stack in Data Structures Binary Tree in Data Structures Heap Data Structure Recursion - Factorial and Fibonacci What is B tree what is B+ tree Huffman tree in Data Structures Insertion Sort vs Bubble Sort Adding one to the number represented an array of digits Bitwise Operators and their Important Tricks Blowfish algorithm Bubble Sort vs Selection Sort Hashing and its Applications Heap Sort vs Merge Sort Insertion Sort vs Selection Sort Merge Conflicts and ways to handle them Difference between Stack and Queue AVL tree in data structure c++ Bubble sort algorithm using Javascript Buffer overflow attack with examples Find out the area between two concentric circles Lowest common ancestor in a binary search tree Number of visible boxes putting one inside another Program to calculate the area of the circumcircle of an equilateral triangle Red-black Tree in Data Structures Strictly binary tree in Data Structures 2-3 Trees and Basic Operations on them Asynchronous advantage actor-critic (A3C) Algorithm Bubble Sort vs Heap Sort Digital Search Tree in Data Structures Minimum Spanning Tree Permutation Sort or Bogo Sort Quick Sort vs Merge Sort

Types of Linked list

Single linked list 

A single linked list is a linked list in which all nodes are connected with each other in sequence. Each node of a singly linked list has two fields. The first field is used to store the data, and the second field is used to link or pointer to the next field.

Types of Linked list

Doubly linked list

The doubly linked list is also called a two-way list in which every node is divided into three fields.

  1. The first field of the linked list is called the previous pointer field, which holds the address of the previous element of the list.
  2. The second field of the linked list stores the information.
  3. The third field of the linked list is called next pointer, which points to the next element of the linked list.

Two pointer variables are used in the doubly linked list which contains the address of the first element of the list and the last element of the list. If the previous part of the first element of the linked list remains NULL, that it indicates that there is no other node behind this node. If the next part of the last element of the linked list remains NULL,it indicates that there is no node next to it. The doubly link list can be traversed in both directions.

Suppose user wants to store integer value in linked list. For this, the doubly linked list structure must be in memory, so the structure will define.

Node Structure:

struct node
 { 
int info; 
struct node * prev, *next;
};  

Insert a node at the beginning

This algorithm is for adding a new node at the beginning:

Step 1: Allocate the memory for the new node.   struct node* new = malloc(size of ( struct node)) 
Step 2: Enter the address of the head in a temporary variable.      struct node* temp= head 
Step 3: Insert the data item into the information part of the new node.      New -> info = item 
Step 4: NULL the previous part of the new node.         New -> prev = NULL 
Step 5: Enter the head address in the next part of the new node.          New -> next = head 
Step 6: It will check whether the head is NULL or not. If the head is NULL, then execute 
step7; otherwise, it will not. 
Step 7: Insert a new node in the head; therefore, the head will point to the new node. 
Step 8: Enter the address of the new node in the previous part of the head.     Head -> prev = new Step9: EXIT  

Function:

Insertatfirst (struct node ** head, int item)
{
struct node*new = malloc (sizeof (struct node));
new -> info = item;
new -> prev = NULL;
new -> next = head;
if (head = = NULL)
head = new;
else
{
head -> prev = new;
head = new;
}
}  

Traversing the Doubly Linked list

  • In order Traversal: For this, the following step is followed.

Step 1: The Linked list pointer will proceed until the head is NULL.

                                while (head != NULL)

Step 2: It will print every information part of the linked list and keep moving the head.

                                 print head -> Info

                                 head = head -> next

  • Reverse Order Traversal: For this, the following step is followed.

Step 1: The Linked list pointer will proceed until the tail is NULL.

                                while (tail != NULL)

Step 2: It will print every information part of the linked list and keep moving the tail.

                                 print tail -> Info

                                 tail = tail -> next

Delete a node at the beginning

If the doubly linked list is empty, then it will return the linked list; Otherwise, we will delete the node that indicates the head pointer. For this, the following step is followed.

Step 1: Take a temporary pointer, in which you will enter the address of the head.                     struct node *temp = head 
Step 2: You will check the head is NULL or not. If the head is NULL, then it will be returned.                     if (head = = NULL)    return 
Step 3: If the head is not NULL, then assign the next part of the head to the next head.                              head = head -> next       free (temp) 
Step 4: The head, which is pointing to the node, assign the NULL in its previous part.                           head -> prev = NULL 
Step 5: Exit  

Function:

deletefromfirst (struct node *head)
{
struct node *temp = head;
if (head = = NULL)
return;
head = head -> next;
free (temp);
head -> prev = NULL;
}  

Delete a node at the end

To delete the last node of the linked list, you will check three conditions.

  • If the doubly linked list is empty, then it will return the linked list.
  • If there is only one node in the linked list, you will delete it, and insert NULL in the head.
  • If there is more than one item in the linked list, it will reach the last node first and then delete the last node. For this, the following step is followed.
Step 1: Take a temporary pointer, in which you will enter the address of the head.   struct node *temp = head 
Step 2: You will check the head is NULL or not. If the head is NULL, then it will be returned.                       if (head = = NULL)    return 
Step 3: You will check the next node of the head is NULL or not. If the next node of the head is                     NULL, then you will repeat the steps from 4 to 6.   
Step 4: Insert the NULL in the head.      head=NULL 
Step 5: Free the temporary pointer.        free(t) 
Step 6: return 
Step 7: You will run the temp until the next part of temp is NULL.                                             while (temp -> next == NULL)                                             temp = temp -> next 
Step 8: Insert the NULL in the previous of the temp.    temp -> prev -> next = NULL 
Step 9: Free the temp       free(temp) 
Step 10: exit

Function:

deletefromlast (struct node *head)
{
struct node * temp = head;
if (head = = NULL)
return;
if (head -> next = = NULL)
{
head = NULL;
free (temp);
return;
}
while (temp -> next != NULL)
temp = temp -> next;
temp -> prev -> next = NULL;
free (temp);
}

Circular Linked List

Each node in a circular linked list is connected like a circle. There is no NULL value at the end of the circular linked list. In this, the last node stores the address of the first node, i.e., the first and last node are adjacent.

There are two types of circular linked list: 

  1. Single circular linked list
  2. Doubly circular linked list.

 



ADVERTISEMENT
ADVERTISEMENT