Linked List - for Computer Science and MCA students

Describe link list and its application in data structure.

A linked list is a basic data structure where each node contains two fields, data and address of next node. The address part of last node has NULL value.
struct Node
{
     int data;
     Node * next;
}

Here member of the structure node * next points to the structure itself. The main advantage of linked lists over arrays is that, the item of linked list need not be contiguous in memory.
link list node
The main Applications of Linked Lists are as follows:
  • For representing polynomials.
  • In Dynamic Memory Management.
  • In Symbol Tables.
  • For balancing parentheses.
  • Representing Sparse Matrix.

How to create link list? Give example.

#include<iostream>
#include<stdio.h>
usingnamespacestd;
struct Node
{
     int data;
     Node * link;
}*start;
voidcreateList(int item)
{
     Node *tmp,*q;
     tmp = (Node *)malloc(sizeof(Node));
     tmp->data = item;
     tmp->link = NULL;
     if(start==NULL)
     {
          start=tmp;
     }
     else
     {
          q = start;
          while(q->link! = NULL)
          {
               q = q->link;
          }
          q->link = tmp;
     }
}
voidshowList()
{
     Node *q;
     if(start==NULL)
     {
          cout<<"List is empty"<<endl;
     }
     else
     {
          q = start;
          cout<<"The element in the list are :"<<endl;
          while(q! = NULL)
          {
               cout<<q->data<<" ";
               q = q->link;
          }
          cout<<endl;
     }
}
void main()
{
     int n,i,item,ch;
     char choice;
     start = NULL;
     do
     {
          cout<<"Enter 1. for create list"<<endl;
          cout<<"Enter 2. for display list"<<endl;
          cout<<"Enter 3. for exit"<<endl;
          cout<<"Enter your choice \t"<<endl;
          cin>>ch;
          switch(ch)
          {
               case 1:
                    cout<<"Enter the no of items into the list";
                    cin>>n;
                    cout<<"Enter the items"<<endl;
                    for(i = 0; i<n; i++)
                    {
                         cin>>item;
                         createList(item);
                    }
                    break;
               case 2:
                    showList();
                    break;
               case 3:
                    exit(0);
                    break;
               default:
                    cout<<"Wrong choice"<<endl;
          }
          cout<<"Do you want to continue??";
          cin>>choice;
     }
     while(choice=='Y' || choice=='y');
     getch();
}

Write a program to sort given no. of items by using link list.

struct Node
{
     int data;
     Node * link;
}*start;
voidcreateList(int item)
{
     Node *tmp,*q;
     tmp = (Node *)malloc(sizeof(Node));
     tmp->data = item;
     tmp->link = NULL;
     if(start==NULL)
     {
          start=tmp;
     }
     else
     {
          q = start;
          while(q->link!=NULL)
          {
               q = q->link;
          }
          q->link = tmp;
     }
}
voidshowList()
{
     Node *q;
     if(start==NULL)
     {
          cout<<"List is empty"<<endl;
     }
     else
     {
          q = start;
          cout<<"The element in the list are :"<<endl;
          while(q!=NULL)
          {
               cout<<q->data<<" ";
               q = q->link;
          }
          cout<<endl;
     }
}
voidsortList(int n)
{
     int i, j, k, temp;
     Node *p, *q ;
     k = n ;
     for (i = 0; i<n - 1; i++, k--)
     {
          p = start;
          q = p ->link;
          for (j = 1; j<k; j++)
          {
               if ( p -> data > q -> data)
               {
                                        temp = p -> data ;
                    p -> data = q -> data ;
                    q -> data = temp ;
               }
               p = p ->link ;
               q = q ->link ;
          }
     }
     showList();
}
void main()
{
     int n,i,item,ch;
     char choice;
     start = NULL;
     do
     {
          cout<<"Enter 1. for create list"<<endl;
          cout<<"Enter 2. for sorted list of items"<<endl;
          cout<<"Enter 3. for exit"<<endl;
          cout<<"Enter your choice \t"<<endl;
          cin>>ch;
          switch(ch)
          {
          case 1:
               cout<<"Enter the no. of items into the list\t";
               cin>>n;
               cout<<"Enter the items"<<endl;
               for(i=0; i<n; i++)
               {
                    cin>>item;
                    createList(item);
               }
               break;
          case 2:
               sortList(n);
               break;
          case 3:
               exit(0);
               break;
          default:
               cout<<"Wrong choice"<<endl;
          }
          cout<<"Do you want to continue??";
          cin>>choice;
     }
     while(choice=='Y' || choice=='y');
     //getch();
}

Related Content

▲