Data Structures & Algorithms part-5 ( Linked list)

Linked list content :

  1. What & why of linked list
  2. Types of linked list
  3. How is linked list represented in memory
  4. Common operations like Creating/Inserting/Deleting/Searching/etc
  5. Practical use of Linked List
  6. Pros and Cons of Linked List

1. What & why of linked list

Difference between Linked list vs Array

  1. Separate object : First and the most important difference between a linked list and an array is that each of the element over here a separate object in case of linked list but in case of an array these elements or cells are not a separate object, instead this entire array is a separate object . If we need to delete an object within a linked list, we can delete this object on the other hand if we need to delete a cell in array we can’t do this but we can delete value within the cell.
  2. Variable size : In case of linked list the number of nodes are note predefined . We can all this increase or decrease the number of nodes at run time. But in array we can’t either increase or decrease cells.
  3. Random access : The random access what that means is if you want to access cell number 3 we can access this directly in array with arr[3] but in case of linked list we can’t do that we always have to start from node number one and keep traversing till we find node 3

Components of linked list

In tail variable we store last variable address so that we couldn’t find last variable address repeatedly . when we traverse and find to last variable address time complexity will have O(n) on the other hand if we store last address in tail then time complexity will O(1)

2. Types of Linked List

  1. Single linked list
  2. Circular single linked list
  3. Double linked list
  4. Circular double linked list

Practical implementation of different types of Linked list

3. How is linked list represented in memory

4. Common operations for all types of linked list :

  • Creation of linked list
  • Insertion of linked list
  • Traversal of linked list
  • Searching in a linked list
  • Deletion of a node from a linked list
  • Deletion of linked list

Creation of linked list

step-1 : first we need to create a blank head reference . then create a blank tall reference and initialize both of them NULL.

step-2 : create a blank node and then we insert a value in it and reference part will be NULL.

step-3 : link head and tall to node which is node-1.

Insertion of linked list

Traversal of linked list

Searching in a linked list

Deletion of a node from a linked list

Deletion of entire single linked list

Circular linked list

Insertion in Circular linked list

insertion in circular linked list

Traversal of Circular linked list

Searching a node in Circular single linked list

Deletion of node from Circular single linked list

Deletion of entire Circular Single Linked List

Double Linked List

Creation of Double Linked List

Insertion in Double Linked List

Traversal of Double Linked List

Reverse Traversal of Double Linked List

Searching a node in Double linked list

Deletion of node from Double Linked List

Deletion of entire Double linked list

Circular Double Linked List

Insertion in Circular Double Linked List

Traversal of Circular Double Linked List

Reverse Traversal of Circular Double Linked List

Searching a node in Circular Double Linked List

Deletion of node from Circular double linked list

Deletion of entire circular double linked list