Sitemap
Open in app

Sign in

Medium Logo
Write

Sign in

About Data Structures

Data Structure is a way to store and organize data so that it can be used efficiently.

Linked Lists-Single LL, Operations Of SingleLL, Applications of Single LL, Circular LL, Double LL

--

Dynamic Memory Allocation

  • Allocating and Freeing dynamic variables
  • Drawbacks of Arrays
  • Need for dynamic storage
  • Linked Lists

Consider the following array declaration

int marks[100];

Such a declaration would typically be used if 100 students marks are to be stored in memory. The moment we make this declaration 200 bytes one reserved in memory. For storing 100 integers in it. However, it may so happen that when we actually run the program we might be interested in storing only 60 students marks. Even in this case 200 bytes would get reserved in memory, which would result in wastage of memory.

Another possibility is that when you run the program you may need to store more than 100 student’s marks. In this case the array would fall short in size. Moreover, there is no way to increase or decrease the array size during execution of the program.

In other words when we use arrays static memory allocation takes place. We can allocate memory at the time of execution by the use of standard library functions malloc() and calloc(). Since these functions allocate memory during execution they are often known as Dynamic memory allocation functions.

Linked Lists

Linked List is a very common data structure often used to store similar data in memory. While the elements of an array occupy contiguous memory locations, those of a linked list are not constrained to be stored in adjacent locations. The individual elements are stored somewhere in memory, rather like a family dispersed, but still bound together. The order of the elements is maintained by explicit links between them.

Linked list is a collection of nodes. They are not in sequential order. We store the address of the variable in a separate node called ‘Head’. We should fill the last pointer with NULL. Then we will be able to access them in a sequential order with the help of pointers.

Observe that the linked list is a collection of elements called nodes, each of which stores two items of information.

One — — an element of the list and

two — -a link i.e., a pointer or an address that indicates explicitly the location of the node containing the successor of this list element.

In the figure the arrow represent the links.

  • Data part of each node consists of marks obtained by a student.
  • Next part is a pointer to the next node.
  • The NULL in the last node indicates that this is the last node in the list.

Node is a structure. NULL is a predefined symbolic constant.

What are the drawbacks of using arrays represent stacks and queues?

One major drawback is that a fixed amount of storage remains allocated to the stack or queue even when the structure is actually using a smaller amount of storage.

Linear Linked List

Figure shows a Linked List. Each item in the list is called a node and contain two fields, a data field and a next address field. The data field holds the actual element on the list. The next address field contains the address of the next node in the list. Such an address which is used to access a particular node, is known as a pointer. The entire linked list is accesses from an external pointer list, that points to the first node in the list. The next field of last node in the list contains a special value, known as NULL. The NULL pointer is used to signal the end of the list.

The list with no nodes on it is called the empty list or null list. List can be initialized to the empty list by the operation

list = NULL;

The node can be represented in C as follows

struct node
{
      int data;
      struct node * next;
};

A linked list is a dynamic data structure. The number of nodes on a list may vary dramatically as elements are inserted and removed.

Basic Operations

Following are the basic operations supported by a list.

  • Insertion − Adds an element to the list.
  • Deletion − Deletes an element from the list.
  • Display − Displays the complete list.
  • Search — Search for an element in List

Insertion Operation

Adding a new node in linked list is a more than one step activity. We shall learn this with diagrams here. First, create a node using the same structure and find the location where it has to be inserted.

Inserting a node to a linked list at front end:

struct node *temp

temp is a variable name of a node

  • temp ->data refers to the data portion of the node.
  • temp ->next refers to the next address portion and is therefore a pointer.

A linked list is a dynamic data structure. The number of nodes on a list may vary dramatically as elements are inserted and removed.

Adding nodes with elements 10,20,30

Assume that the linked list is a null list initially

temp = NULL;

To insert a node into linked list call insert_node() function which adds a node to the present linked list.

insert_node (10);

Algorithm for insert_node():

void insert_node(int ele)
{
    temp = malloc(sizeof(struct node));
    temp->data = ele
    temp->next = NULL    if (head == NULL)
    {
       head = curr = temp;
    }
    
    else
    {
        curr->next = temp;
        curr = temp
    }
}

This function inserts a node to the existing linked list. The malloc function allocates space for one node called temp.

  • temp -> data field will be filled with ele.
  • temp -> next field will be filled with NULL.

If the supplied list head/curr[Linked List] is NULL then the node temp will be the first node of the linked list. Otherwise the node temp will be added to the front of the already existing linked list. Through,

curr  -> next = temp;

Now temp is the first node of the linked list. Linked list will be referred by the pointer pointed to the first node of the linked list.

Removing a node from the linked list:

void del(int p)
{
    int i;
    if(p == 1)
    {
        temp = head;
        head=head->next;
        free(temp);
    }
    else if(p==length())
    {
       for(temp=head;temp->next!=curr;temp=temp->next)
            temp->next=NULL;
       free(curr);
       curr=temp;
    }
    else
    {
        temp=head;
        for(i=1;i<=(p-2);i++)
            temp=temp->next;
        temp1=temp->next;
        temp->next=temp1->next;
        free(temp1);
    }
}

This function deletes a node at the specified position of a linked list. Let us assume that we have a linked list of 4 nodes. Let us try to delete the node at first position.

After deleting the first node list may contain only 3 nodes and the first node should be pointed by the pointed list, because the whole list should be referred by the pointer list, which is the original node of the list.

Step by step procedure for deleting the node at first position of the linked list:

Implementation of all the Operations of a Linked List:

#include<stdio.h>
struct node
{
    int data;
    struct node *next;
};
struct node *head=NULL,*temp,*curr,*temp1;void create(int data)
{temp = malloc(sizeof(struct node));
    // Initialize data into temp data field
    temp->data = data;// Put NULL pointer reference into temp link
    temp->next = NULL;if(head == NULL)
        head = curr = temp;else
    {
        curr->next = temp;
         curr = temp;
    }}
void insert(int ele,int p)
{
    int i;
    temp = malloc(sizeof(struct node));
    temp->data = ele;    if(p==1)
    {
        temp->next=head;
        head=temp;
    }
    if(p==length()+1)
    {
        curr->next = temp;
        temp->next=NULL;
        curr=temp;
    }
    else
    {
        temp1=head;
        for(i=1;i<=p-2;i++)
            temp1=temp1->next;temp->next=temp1->next;
        temp1->next=temp;
    }
}void search(int ele)
{
    int flag=0;
    curr = head; // Initialize current
    while (curr != NULL)
    {
          if (curr->data == ele)
          {
              flag=1;
              break;
          }
          curr = curr->next;
    }
    if(flag == 1)
        printf("True\n");
    else
        printf("False\n");
}void del(int p)
{
    int i;
    if(p == 1)
    {
        temp = head;
        head=head->next;
        free(temp);
    }
    else if(p==length())
    {
       for(temp=head;temp->next!=curr;temp=temp->next)
            temp->next=NULL;
       free(curr);
       curr=temp;
    }
    else
    {
        temp=head;
        for(i=1;i<=(p-2);i++)
            temp=temp->next;
        temp1=temp->next;
        temp->next=temp1->next;
        free(temp1);
    }
}
int length()
{
    int i=0;
    for(temp=head;temp!=NULL;temp=temp->next,i++);
    return i;
}void display()
{for(temp=head;temp!=NULL;temp=temp->next)
        printf("%d->",temp->data);printf("NULL\n");
}void main()
{
    int ch,ele,p;
    printf("1.Create \n2.Delete Element at a specified position \n3.Insert element at a Specific position\n4.Display\n5.Length of the List\n6.Search\n");
    while(1)
    {
        printf("Enter Choice\n");
        scanf("%d",&ch);
        switch(ch)
        {
        case 1:
            printf("Enter Element to be created\n");
            scanf("%d",&ele);
            create(ele);
            break;
        case 2:
            printf("Enter the position to delete");
            scanf("%d",&p);
            del(p);
            break;
        case 3:
            printf("Enter element and position\n");
            scanf("%d%d",&ele,&p);
            insert(ele,p);
            break;
        case 4:
            display();
            break;
        case 5:
            printf("Length of the List %d",length());
            break;
        case 6:
            printf("Enter Search Element");
            scanf("%d",&ele);
            search(ele);
            break;
        default:
            exit(0);
        }
    }
}

Output:

1.Create
2.Delete Element at a specified position
3.Insert element at a Specific position
4.Display
5.Length of the List
6.Search
Enter Choice
1
Enter Element to be created
12
Enter Choice
1
Enter Element to be created
13
Enter Choice
3
Enter element and position
15 1
Enter Choice
4
15->12->13->NULL
Enter Choice
2
Enter the position to delete 3
Enter Choice
4
15->12->NULL
Enter Choice
6
Enter Search Element12
True
Enter Choice
7

Reverse a linked list

Given pointer to the head node of a linked list, the task is to reverse the linked list. We need to reverse the list by changing the links between nodes.

Program to reverse a Linked List:

#include<stdio.h>
struct node
{
    int data;
    struct node *next;
};
struct node *head=NULL,*temp,*curr,*temp1;void create(int data)
{    temp = malloc(sizeof(struct node));
    // Initialize data into temp data field
    temp->data = data;    // Put NULL pointer reference into temp link
    temp->next = NULL;if(head == NULL)
        head = curr = temp;else
    {
        curr->next = temp;
         curr = temp;
    }}
void del(int p)
{
    int i;
    if(p == 1)
    {
        temp = head;
        head=head->next;
        free(temp);
    }
    else if(p==length())
    {
       for(temp=head;temp->next!=curr;temp=temp->next)
            temp->next=NULL;
       free(curr);
       curr=temp;
    }
    else
    {
        temp=head;
        for(i=1;i<=(p-2);i++)
            temp=temp->next;
        temp1=temp->next;
        temp->next=temp1->next;
        free(temp1);
    }
}
void rev()
{struct node *n,*p;
    curr=temp=head;
    n=NULL;
    p=NULL;
    while(curr != NULL)
    {
        p=n;
        n=curr->next;
        curr->next=p;
        p=curr;
        curr=n;}
    head=p;
}int length()
{
    int i=0;
    for(temp=head;temp!=NULL;temp=temp->next,i++);
    return i;
}
void display()
{     for(temp=head;temp!=NULL;temp=temp->next)
        printf("%d->",temp->data);
}void main()
{
    int ch,ele,p;
    printf("1.Create \n2.Delete \n3..Display\n 4.Reverse The List\n");
    while(1)
    {
        printf("Enter Choice\n");
        scanf("%d",&ch);
        switch(ch)
        {
        case 1:
            printf("Enter Element to be created\n");
            scanf("%d",&ele);
            create(ele);
            break;
        case 2:
            printf("Enter the position to delete\n");
            scanf("%d",&p);
            del(p);
            break;
        case 3:
            display();
            printf("NULL\n");
            break;
        case 4:
            rev();
            break;
        default:
            exit(0);
        }
    }
}

Output:

1.Create
2.Delete
3.Display
4.Reverse The List
Enter Choice
1
Enter Element to be created
12
Enter Choice
1
Enter Element to be created
13
Enter Choice
1
Enter Element to be created
14
Enter Choice
1
Enter Element to be created
15
Enter Choice
2
Enter the position to delete1
Enter Choice
3
13->14->15->NULL
Enter Choice
4
Enter Choice
3
15->14->13->NULL
Enter Choice
5

Applications of Linked List:

  1. Sparse matrix representation
  2. Polynomial Representation

Sparse Matrix:

Sparse matrix is a matrix in which most of the elements are zeros.

Eg:

In above example matrix, there are only 6 non-zero elements ( those are 9, 8, 4, 2, 5 & 2) and matrix size is 5 X 6. We represent this matrix as shown in the above image. Here the first row in the right side table is filled with values 5, 6 & 6 which indicates that it is a sparse matrix with 5 rows, 6 columns & 6 non-zero values. The second row is filled with 0, 4, & 9 which indicates the non-zero value 9 is at the 0th-row 4th column in the Sparse matrix. In the same way, the remaining non-zero values also follow a similar pattern.

Implementation of Sparse Matrix using LinkedLists:

#include<stdio.h>
struct node
{
    int row;
    int column;
    int data;
    struct node *next;
};
struct node *head=NULL,*temp,*curr=NULL;
void main()
{
    int a[10][10],m,n,i,j;
    printf("Enter Size of the matrix\n");
    scanf("%d %d",&m,&n);
    printf("Enter the values in the sparse matrix");
    for(i=0;i<m;i++)
        for(j=0;j<n;j++)
         scanf("%d",&a[i][j]);    for(i=0;i<m;i++)
        for(j=0;j<n;j++)
        {
            if(a[i][j]!=0)
            {                temp=malloc(sizeof(struct node));
                temp->row=i;
                temp->column=j;
                temp->data=a[i][j];
                temp->next=NULL;
                if(head==NULL)
                    head=curr=temp;
                else
                {
                    curr->next=temp;
                    curr=temp;
                }
            }
        }        printf("Representation in Linked List\n");
         for(temp=head;temp!=NULL;temp=temp->next)
            printf("[%d %d]:%d\n",temp->row,temp->column,temp->data);}

Output:

Enter Size of the matrix
5
6
Enter the values in the sparse matrix
0 0 0 0 9 0
0 8 0 0 0 0
4 0 0 2 0 0
0 0 0 0 0 5
0 0 2 0 0 0Representation in Linked List
[0 4]:9
[1 1]:8
[2 0]:4
[2 3]:2
[3 5]:5
[4 2]:2

Representation of Polynomial using Linked List:

A polynomial object is a homogeneous ordered list of pairs <exponent,coefficient>, where each coefficient is unique. Operations include returning the degree, extracting the coefficient for a given exponent, addition, multiplication, evaluation for a given input.

#include<stdio.h>
struct node
{
    int coeff;
    int exp;
    struct node *next;
};
struct node *head=NULL,*temp,*curr=NULL,*temp1;
void main()
{
    int i,n;
    printf("Enter no. of terms in the polynomial equation\n ");
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        temp=malloc(sizeof(struct node));
        scanf("%d %d",&temp->coeff,&temp->exp);
        temp->next=NULL;
        if(head==NULL)
            head=curr=temp;
        else
        {
            curr->next=temp;
            curr=temp;
        }
    }
    printf("The polynomial equation is");
    for(temp=head;temp!=NULL;temp=temp->next)
        printf("%dx^%d+",temp->coeff,temp->exp);
    printf("0");}

Output:

Enter no. of terms in the polynomial equation
3
5 2
4 1
3 0
The polynomial equation is5x^2+4x^1+3x^0+0

Adding two polynomials using Linked List

Given two polynomial numbers represented by a linked list. Write a function that add these lists means add the coefficients who have same variable powers.

For Example,

Input:
     1st number = 5x2 + 4x1 + 2x0
     2nd number = -5x1 - 5x0
Output:
        5x2-1x1-3x0
Input:
     1st number = 5x3 + 4x2 + 2x0
     2nd number = 5x^1 - 5x^0
Output:
        5x3 + 4x2 + 5x1 - 3x0

Implementation For Addition of two polynomials using LinkedLists:

// C++ program for addition of two polynomials using Linked Lists#include <bits/stdc++.h>
using namespace std;// Node structure containing power and coefficient of variablestruct node {
      int coeff;
      int pow;
      struct node *next;
};
struct node **temp;// Function to create new node
void create(int x, int y, struct node** temp)
{
    struct node *r, *z;
    z = *temp;
    if (z == NULL) {
       r = (struct node*)malloc(sizeof(struct node));
       r->coeff = x;
       r->pow = y;
       *temp = r;
       r->next = (struct node*)malloc(sizeof(struct node)); 
       r = r->next;
       r->next = NULL;
    }     else {
        r->coeff = x;
        r->pow = y; 
        r->next = (struct node*)malloc(sizeof(struct node));
        r = r->next;
        r->next = NULL;
      }
}// Function Adding two polynomial numbers
void polyadd(struct node* poly1, struct node* poly2,struct node* poly)
{
     while (poly1->next && poly2->next) { 
            // If power of 1st polynomial is greater then 2nd, then store 1st as it is and move its pointer
          if (poly1->pow > poly2->pow) {
                poly->pow = poly1->pow;
                poly->coeff = poly1->coeff;
                poly1 = poly1->next;
           }
        // If power of 2nd polynomial is greater then 1st, then store 2nd as it is and move its pointer
           else if (poly1->pow < poly2->pow) {
                poly->pow = poly2->pow;
                poly->coeff = poly2->coeff;
                poly2 = poly2->next;
           }
       // If power of both polynomial numbers is same then add their coefficients
           else {
                poly->pow = poly1->pow;
                poly->coeff = poly1->coeff + poly2->coeff; 
                poly1 = poly1->next;
                poly2 = poly2->next;
           }
      // Dynamically create new node
      poly->next= (struct node*)malloc(sizeof(struct node));
      poly = poly->next;
      poly->next = NULL;
   }   while (poly1->next || poly2->next) {
          if (poly1->next) {
              poly->pow = poly1->pow;
              poly->coeff = poly1->coeff; 
              poly1 = poly1->next;
          }          if (poly2->next) {
              poly->pow = poly2->pow;
              poly->coeff = poly2->coeff;
              poly2 = poly2->next;
          }          poly->next = (struct node*)malloc(sizeof(struct node));
          poly = poly->next;
          poly->next = NULL;
      }
   }
// Display Linked list
void show(struct node* node)
{
     while (node->next != NULL) {         printf("%dx^%d", node->coeff, node->pow);
         node = node->next; 
         if (node->coeff >= 0) {
               if (node->next != NULL)
                        printf("+");
         }
     }
}// Driver code
int main()
{
   struct node *poly1 = NULL, *poly2 = NULL, *poly = NULL;
   // Create first list of 5x^2 + 4x^1 + 2x^0
   create(5, 2, &poly1);
   create(4, 1, &poly1);
   create(2, 0, &poly1);
   // Create second list of -5x^1 - 5x^0
   create(-5, 1, &poly2);
   create(-5, 0, &poly2);
   printf("1st Number: ");
   show(poly1);
   printf("\n2nd Number: ");
   show(poly2);
   poly = (struct node*)malloc(sizeof(struct node));
   // Function add two polynomial numbers
   polyadd(poly1, poly2, poly);
  // Display resultant List
   printf("\nAdded polynomial: ");
   show(poly);
   return 0;
}

Output:

1st Number: 5x^2+4x^1+2x^0
2nd Number: -5x^1-5x^0
Added polynomial: 5x^2-1x^1-3x^0

Multiply two polynomials

Given two polynomials represented by two arrays, write a function that multiplies given two polynomials.

For example,

Input:  A[] = {5, 0, 10, 6} 
        B[] = {1, 2, 4} 
Output: prod[] = {5, 10, 30, 26, 52, 24}

The first input array represents "5 + 0x^1 + 10x^2 + 6x^3"
The second array represents "1 + 2x^1 + 4x^2" 
And Output is "5 + 10x^1 + 30x^2 + 26x^3 + 52x^4 + 24x^5"

A simple solution is to one by one consider every term of first polynomial and multiply it with every term of second polynomial. Following is algorithm of this simple method.

multiply(A[0..m-1], B[0..n01])
1) Create a product array prod[] of size m+n-1.
2) Initialize all entries in prod[] as 0.
3) Traverse array A[] and do following for every element A[i]
...(3.a) Traverse array B[] and do following for every element B[j]
          prod[i+j] = prod[i+j] + A[i] * B[j]
4) Return prod[].

Implementation:

#include <bits/stdc++.h>
using namespace std;
// A[] represents coefficients of first polynomial
// B[] represents coefficients of second polynomial
// m and n are sizes of A[] and B[] respectively
int *multiply(int A[], int B[], int m, int n)
{
   int *prod = new int[m+n-1];// Initialize the porduct polynomial
   for (int i = 0; i<m+n-1; i++)
     prod[i] = 0;// Multiply two polynomials term by term// Take ever term of first polynomial
   for (int i=0; i<m; i++)
   {
     // Multiply the current term of first polynomial
     // with every term of second polynomial.
     for (int j=0; j<n; j++)
         prod[i+j] += A[i]*B[j];
   }return prod;
}// A utility function to print a polynomial
void printPoly(int poly[], int n)
{
    for (int i=0; i<n; i++)
    {
       cout << poly[i];
       if (i != 0)
        cout << "x^" << i ;
       if (i != n-1)
       cout << " + ";
    }
}// Driver program to test above functions
int main()
{
    // The following array represents polynomial 5 + 10x^2 + 6x^3
    int A[] = {5, 0, 10, 6};// The following array represents polynomial 1 + 2x + 4x^2
    int B[] = {1, 2, 4};
    int m = sizeof(A)/sizeof(A[0]);
    int n = sizeof(B)/sizeof(B[0]);cout << "First polynomial is n";
    printPoly(A, m);
    cout << "nSecond polynomial is n";
    printPoly(B, n);int *prod = multiply(A, B, m, n);cout << "nProduct polynomial is n";
    printPoly(prod, m+n-1);return 0;
}

Output:

First polynomial is n5 + 0x^1 + 10x^2 + 6x^3n
Second polynomial is n1 + 2x^1 + 4x^2n
Product polynomial is n5 + 10x^1 + 30x^2 + 26x^3 + 52x^4 + 24x^5

Advantages and Disadvantages of Linked List

Advantages of Linked List:

  • Dynamic Data Structure — Linked list is a dynamic data structure so it can grow and shrink at runtime by allocating and deallocating memory. So there is no need to give initial size of linked list.
  • Insertion and Deletion — Insertion and deletion of nodes are really easier. Unlike array here we don’t have to shift elements after insertion or deletion of an element. In linked list we just have to update the address present in next pointer of a node.
  • No Memory Wastage — As size of linked list can increase or decrease at run time so there is no memory wastage. In case of array there is lot of memory wastage, like if we declare an array of size 10 and store only 6 elements in it then space of 4 elements are wasted. There is no such problem in linked list as memory is allocated only when required.
  • Implementation — Data structures such as stack and queues can be easily implemented using linked list.

Disadvantages of Linked List:

  • Memory Usage — More memory is required to store elements in linked list as compared to array. Because in linked list each node contains a pointer and it requires extra memory for itself.
  • Traversal — Elements or nodes traversal is difficult in linked list. We can not randomly access any element as we do in array by index. For example if we want to access a node at position n then we have to traverse all the nodes before it. So, time required to access a node is large.
  • Reverse Traversing — In linked list reverse traversing is really difficult. In case of doubly linked list its easier but extra memory is required for back pointer hence wastage of memory.

Double Linked List

A Doubly Linked List (DLL) contains an extra pointer, typically called previous pointer, together with next pointer and data which are there in singly linked list.

Double Linked List

Following is representation of a DLL node in C language.

/* Node of a doubly linked list */struct node {
      int data;
      struct node* next; // Pointer to next node in DLL
      struct node* prev; // Pointer to previous node in DLL
};

Insertion and Deletion of a node in DLL

#include<stdio.h>
struct node
{
    int data;
    struct node *prev,*next;
};struct node *head=NULL,*temp,*curr;void create(int ele)
{temp = malloc(sizeof(struct node));
    // Initialize data into temp data field
    temp->data = ele;// Put NULL pointer reference into temp link
    temp->next = NULL;if(head == NULL)
    {
         curr = head = temp;
         head->prev=NULL;
    }
    else
    {
        curr->next = temp;
        temp->prev=curr;
        curr = temp;
    }
}void del(struct node** head_ref, struct node* del)
{
    /* base case */
    if (head_ref == NULL || del == NULL)
        return;/* If node to be deleted is head node */
    if (*head_ref == del)
        *head_ref = del->next;/* Change next only if node to be
    deleted is NOT the last node */
    if (del->next != NULL)
        del->next->prev = del->prev;/* Change prev only if node to be
    deleted is NOT the first node */
    if (del->prev != NULL)
        del->prev->next = del->next;/* Finally, free the memory occupied by del*/
    free(del);
    return;
}void main()
{
    int ch,ele;
    while(1)
    {
        printf("Enter Choice\n");
        scanf("%d",&ch);
        switch(ch)
        {
        case 1:
            printf("Enter Element to be created\n");
            scanf("%d",&ele);
            create(ele);
            break;
        case 2:
            for(temp=head;temp!=NULL;temp=temp->next)
                printf("%d->",temp->data);
            printf("NULL\n");
            break;
        case 3:
            del(&head, head); /*delete first node*/
            //deleteNode(&head, head->next); /*delete middle node*/
            //deleteNode(&head, head->next); /*delete last node*/
            break;
        default:
            exit(0);
        }
    }
}

Output:

Enter Choice
1
Enter Element to be created
12
Enter Choice
1
Enter Element to be created
13
Enter Choice
1
Enter Element to be created
14
Enter Choice
2
12->13->14->NULL
Enter Choice
3
Enter Choice
2
13->14->NULL
Enter Choice
7

Circular Linked List

Circular Linked list is a linked list in which last node always points to the first node.

  • Advantage: We can visit any node from any position.
  • Disadvantage: There is a possibility of getting into infinite loop.
Circular Linked List

An Example for deleting a node in CLL:

Input : 2->5->7->8->10->(head node)
        data = 5
Output : 2->7->8->10->(head node)

Input : 2->5->7->8->10->(head node)
         7
Output : 2->5->8->10->2(head node)

Implementation of Circular Linked List

#include<stdio.h>
struct node
{
    int data;
    struct node *next;
};struct node *head=NULL,*temp,*curr;void create(int ele)
{temp = malloc(sizeof(struct node));
    // Initialize data into temp data field
    temp->data = ele;if(head == NULL)
    {
         curr = head = temp;
    }
    else
    {
        curr->next = temp;
        curr = temp;
    }
    curr->next=head;}void deleteNode(struct node* head, int key)
{
    if (head == NULL)
        return;// Find the required node
    struct node *curr = head, *prev;
    while (curr->data != key)
    {
        if (curr->next == head)
        {
            printf("\nGiven node is not found"
                   " in the list!!!");
            break;
        }prev = curr;
        curr = curr->next;
    }// Check if node is only node
    if (curr->next == head)
    {
        head = NULL;
        free(curr);
        return;
    }// If more than one node, check if
    // it is first node
    if (curr == head)
    {
        prev = head;
        while (prev->next != head)
            prev = prev->next;
        head = curr->next;
        prev->next = head;
        free(curr);
    }// check if node is last node
    else if (curr->next == head && curr == head)
    {
        prev->next = head;
        free(curr);
    }
    else
    {
        prev->next = curr->next;
        free(curr);
    }
}void main()
{
    int ch,ele;
    while(1)
    {
        printf("Enter Choice\n");
        scanf("%d",&ch);
        switch(ch)
        {
        case 1:
            printf("Enter Element to be created\n");
            scanf("%d",&ele);
            create(ele);
            break;
        case 2:
            for(temp=head;temp->next!=head;temp=temp->next)
                printf("%d->",temp->data);
            printf("%d\n",temp->data);
            break;
        case 3:
            printf("Enter element to be deleted");
            scanf("%d",&ele);
            deleteNode(head, ele);
            break;
        default:
            exit(0);
        }
    }
}

Output:

List Before Deletion: 10 8 7 5 2
List After Deletion: 10 8 5 2

Stack — Using Linked List

Implementing a stack using single linked list

All the single linked list operations perform based on Stack operations LIFO(last in first out) and with the help of that knowledge we are going to implement a stack using single linked list.

A stack can be easily implemented through the linked list. In stack Implementation, a stack contains a top pointer. which is “head” of the stack where pushing and popping items happens at the head of the list. first node have null in link field and second node link have first node address in link field and so on and last node address in “top” pointer.

The main advantage of using linked list over an arrays is that it is possible to implements a stack that can shrink or grow as much as needed. In using array will put a restriction to the maximum capacity of the array which can lead to stack overflow. Here each new node will be dynamically allocate. so overflow is not possible.

Stack Operations:

  1. push() : Insert the element into linked list nothing but which is the top node of Stack.
  2. pop() : Return top element from the Stack and move the top pointer to the second node of linked list or Stack.
  3. peek(): Return the top element.
  4. display(): Print all element of Stack.

Implementation of stack using Linked List:

#include<stdio.h>
struct node
{
    int data;
    struct node *next;
};
struct node *head=NULL,*temp,*top,*temp1;void push(int data)
{temp = malloc(sizeof(struct node));
    if (!temp)
    {
        printf("\nHeap Overflow");
        exit(1);
    }// Initialize data into temp data field
    temp->data = data;// Put top pointer reference into temp link
    temp->next = top;// Make temp as top of Stack
    top = temp;
}
void pop()
{
    if(top == NULL)
        printf("Linked list is empty");
    else
    {
       // Top assign into temp
        temp = top;
        // Assign second node to top
        top = top->next;
        // Destroy connection between first and second
        temp->next = NULL;
        // Release memory of top node
        free(temp);
    }
}
void display()
{
    // Check for stack underflow
    if (top == NULL)
    {
        printf("\nStack Underflow");
        exit(1);
    }
    else
    {
        temp = top;
        while (temp != NULL)
        {// Print node data
            printf("%d->",temp->data );// Assign temp link to temp
            temp = temp->next;
        }
    }
}
void main()
{
    int ch,ele,p;
    printf("1.push 2.pop 3.display 4.exit\n");
    while(1)
    {
        printf("Enter Choice\n");
        scanf("%d",&ch);
        switch(ch)
        {
        case 1:
            printf("Enter Element to be created\n");
            scanf("%d",&ele);
            push(ele);
            break;
        case 2:
            pop();
            break;
        case 3:
            display();
            printf("NULL");
            break;
        default:
            exit(0);
        }
    }
}

Output:

1.push 2.pop 3.display 4.exit
Enter Choice1Enter Element to be created12
Enter Choice1Enter Element to be created13
Enter Choice1Enter Element to be created14
Enter Choice2
Enter Choice3
13->12->NULL
Enter Choice2
Enter Choice1Enter Element to be created15
Enter Choice3
15->12->NULL
Enter Choice

Queue — Using Linked List

In a Queue data structure, we maintain two pointers, front and rear. The front points the first item of queue and rear points to last item.

enQueue() This operation adds a new node after rear and moves rear to the next node.

deQueue() This operation removes the front node and moves front to the next node.

Implementation:

#include <stdio.h>
#include <stdlib.h>// A linked list (LL) node to store a queue entry
struct QNode {
    int key;
    struct QNode* next;
};// The queue, front stores the front node of LL and rear stores the
// last node of LL
struct Queue {
    struct QNode *front, *rear;
};// A utility function to create a new linked list node.
struct QNode* newNode(int k)
{
    struct QNode* temp = (struct QNode*)malloc(sizeof(struct QNode));
    temp->key = k;
    temp->next = NULL;
    return temp;
}// A utility function to create an empty queue
struct Queue* createQueue()
{
    struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue));
    q->front = q->rear = NULL;
    return q;
}// The function to add a key k to q
void enQueue(struct Queue* q, int k)
{
    // Create a new LL node
    struct QNode* temp = newNode(k);// If queue is empty, then new node is front and rear both
    if (q->rear == NULL) {
        q->front = q->rear = temp;
        return;
    }// Add the new node at the end of queue and change rear
    q->rear->next = temp;
    q->rear = temp;
}// Function to remove a key from given queue q
void deQueue(struct Queue* q)
{
    // If queue is empty, return NULL.
    if (q->front == NULL)
        return;// Store previous front and move front one node ahead
    struct QNode* temp = q->front;q->front = q->front->next;// If front becomes NULL, then change rear also as NULL
    if (q->front == NULL)
        q->rear = NULL;free(temp);
}// Driver Program to test anove functions
int main()
{
    struct Queue* q = createQueue();
    enQueue(q, 10);
    enQueue(q, 20);
    deQueue(q);
    deQueue(q);
    enQueue(q, 30);
    enQueue(q, 40);
    enQueue(q, 50);
    deQueue(q);
    printf("Queue Front : %d \n", q->front->key);
    printf("Queue Rear : %d", q->rear->key);
    return 0;
}

Output:

Queue Front : 40
Queue Rear : 50
Linked Lists
Double Linked Lists
Circular Ll
Stacks Using Ll
Queues Using Ll

--

--

About Data Structures
About Data Structures

Published in About Data Structures

9 followers
Last published Feb 21, 2021

Data Structure is a way to store and organize data so that it can be used efficiently.

Pravallika Devireddy
Pravallika Devireddy

Written by Pravallika Devireddy

33 followers
10 following

No responses yet

Help

Status

About

Careers

Press

Blog

Privacy

Rules

Terms

Text to speech