What is Linked List in Data Structure with example ?

  • A linked list is a sequence of data structures, which are connected together through links.
  • Linked List is a sequence of links which contains objects. Each link contains a connection to another link. Linked list is the second most-used data structure after array.
    • Link − Each link of a linked list can store a data called an element.
    • Next − Each link of a linked list contains a link to the next link called Next.
    • LinkedList − A Linked List contains the connection link to the first link called First.
  • A linked list consists of nodes where each node contains a data field and a reference(link) to the next node in the list.
Linked List in Data Structure

Types of Linked Lists

  • Singly linked list
  • Doubly linked list
  • Circular linked list

Singly linked list

Singly Linked List

Doubly linked list

  • A doubly linked list is a list that has two references, one to the next node and another to previous node.
Doubly linked list

Circular linked list

  • Another important type of a linked list is called a circular linked list where last node of the list points back to the first node (or the head) of the list.
Circular linked list

Doubly Circular linked list

  • Circular doubly linked list is a type of data structure in which a node contain pointers to its previous node as well as the next node.
  • Circular doubly linked list doesn’t contain NULL in any of the node.
  • The last node contains the address of the first node of the list. The first node also contain address of the last node in its previous pointer.
Doubly Circular linked list

Sample Code:

#include<stdio.h>
#include <stdlib.h>
int main()
{
   struct node
   {
      int num;
      struct node *ptr;
   };
   typedef struct node NODE;
   NODE *head, *first, *temp=0;
   int count = 0;
   int choice = 1;
   first = 0;
   while(choice)
   {
      head =(NODE*) malloc(sizeof(NODE));
      printf("Enter the data item: ");
      scanf("%d", &head-> num);
      if(first != 0)
      {
         temp->ptr = head;temp = head;
      }
      else
      {
         first = temp = head;
      }
      fflush(stdin);
      printf("Do you want to continue(Type 0 or 1)?\n\n");
      scanf("%d", &choice);
   }
   temp->ptr = 0;
   temp = first; /* reset temp to the beginning*/
   printf("\n Status of the linked list is\n");
   while(temp!=0)
   {
      printf("%d=>", temp->num);
      count++;
      temp = temp -> ptr;
   }
   printf("NULL\n");
   printf("No. of nodes in the list = %d\n", count);
   return 0;
}

Output:

Enter the data item: 10
Do you want to continue <Type 0 or 1>?
1
Enter the data item: 20
Do you want to continue<Type 0 or 1>?
1
Enter the data item: 30
Do you want to continue<Type 0 or 1>?
0
Status of the Linked List is
10=>20=>30=>NULL
No.of nodes in the list = 3

Advantages of Linked List

  • Linked list is dynamic in nature which allocates the memory when required.
  • In linked list, stack and queue can be easily executed.
  • It reduces the access time.
  • Insert and delete operation can be easily implemented in linked list.

Disadvantages of Linked List

  • Reverse traversing is difficult in linked list.
  • Linked list has to access each node sequentially; no element can be accessed randomly.
  • In linked list, the memory is wasted as pointer requires extra memory for storage.

Categorized in:

Data Structure

Tagged in:

, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,