marq

Dr. Charles Simonyi is the Father of Modern Microsoft Excel                                           JavaScript was originally developed by Brendan Eich of Netscape under the name Mocha, later LiveScript, and finally renamed to JavaScript.                                           The word "Biology" is firstly used by Lamarck and Treviranus                                           Hippocrates (460-370 bc) is known as father of medicine.                                           Galene, 130-200 is known as father of Experimental Physology                                           Aristotle (384-322 BC) is known as Father of Zoology because he wrote the construction and behavior of different animals in his book "Historia animalium"                                           Theophrastus(370-285 BC) is known as father of Botany because he wrote about 500 different plants in his book "Historia Plantarum".                                           John Resig is known as Father of Jquery -                                          HTML is a markup language which is use to design web pages. It was invented in 1990 by Tim Berners-Lee.                                                                The Google was founded by Larry Page and Sergey Brin.                                                                Rasmus Lerdorf was the original creator of PHP. It was first released in 1995.                                                               Facebook was founded by Mark Zuckerberg                                                               Bjarne Stroustrup, creator of C++.                                                                Dennis Ritchie creator of C                                                                                                                              James Gosling, also known as the "Father of Java"                                          At 11.44%, Bihar is India's fastest growing state                                          Father of HTML -Tim Berners Lee                                          orkut was created by Orkut Büyükkökten, a Turkish software engineer                    Photoshop: It came about after Thomas Knoll, a PhD student at the University of Michigan created a program to display grayscale images on a monochrome monitor which at the time was called 'Display'.

Linked List

A linked list is a data structure which consists of data record in a sequence such that each data record have a field of data as well as link reference to its connected node. It do not provide the random access to any of its member data as it is form of a indexing and the connected node is pre-defined.

There are mainly three kinds of linked lists:

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

Singly link list:

In the singly link list each node have two fields one for data and other is for link reference of the next node. The node have null only to the last node of the link field. This can be seen in the following picuture.
Fig: Singly Link List

Doubly link list:

In the doubly link list each node have three field two fields for link which is the reference to next and previous and one for data record. The node have null only to the first node of previous and last node at the next. This can be seen in the following picture.
Fig: Doubly Link List

Circular link list:

If talking about singly circular link list each node have two fields one for data record and other for link reference to the next node. The last node has link reference to the first node. There in no null present in the link of any node.
Fig: Singly circular link list





In this example you will see how to create a node and insert data record in singly link list. 

Code:

# include <stdio.h>
# include <stdlib.h>
struct node
{
int data;
struct node *link;
};
struct node *insert(struct node *p , int num)
{
struct node *temp;
 if(p==NULL)
 {
 p=(struct node *)malloc(sizeof(struct node));

 if(p==NULL)
 {
 printf("Error Occurred\n");
 exit(0);
 }
          p-> data = num;
   p-> link = NULL;
  }
  else
  {
  temp = p;
 while (temp-> link != NULL)
 temp = temp-> link;
 temp-> link = (struct node *)malloc(sizeof(struct node));
 if(temp -> link == NULL)
 {
  printf("Error Occurred\n");
  exit(0);
 }
 temp = temp-> link;
 temp-> data = num;
 temp-> link = NULL;
 }
 return (p);
}
void printlist ( struct node *p  )
{
 printf("The data values of your list are\n");
 while (p!= NULL)
 {
 printf("%d\t",p-> data);
 p = p-> link;
 }
}
void main()
{
 int n;
 int x;
 struct node *start = NULL ;
 printf("Enter number of nodes you want to create \n");
 scanf("%d",&n);
 while ( n-- > 0 )
 {
 printf( "Enter data values for each node\n");
 scanf("%d",&x);
 start = insert ( start , x );
 }
 printf("The created single link list is\n");
 printlist ( start );
}

Output:


=========================================================================
Doubly Linked List



This tutorial demonstrate how to implement doubly linked list. 

Code:

#include <stdio.h>
#include <conio.h>
#include <malloc.h>

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

main()
{
int choice,n,m,po,i;
start=NULL;
while(1)
{
printf("1.Create List\n");
printf("2.Add at begining\n");
printf("3.Add after\n");
printf("4.Delete\n");
printf("5.Display\n");
printf("6.Count\n");
printf("7.Reverse\n");
printf("8.exit\n");
printf("Enter your choice : \n");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("How many nodes you want : ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter the element : ");
scanf("%d",&m);
create_list(m);
}
break;
case 2:
printf("Enter the element : ");
scanf("%d",&m);
addatbeg(m);
break;
case 3:
printf("Enter the element : ");
scanf("%d",&m);
printf("Enter the position after which this 

element is inserted : ");
scanf("%d",&po);
addafter(m,po);
break;
case 4:
printf("Enter the element for deletion : ");
scanf("%d",&m);
del(m);
break;
case 5:
display();
break;
case 6:
count();
break;
case 7:
rev();
break;
case 8:
exit();
default:
printf("Wrong choice\n");
}/*End of switch*/
   }/*End of while*/
}/*End of main()*/

create_list(int num)
{
struct node *q,*tmp;
tmp= malloc(sizeof(struct node));
tmp->info=num;
tmp->next=NULL;
if(start==NULL)
{
tmp->prev=NULL;
start->prev=tmp;
start=tmp;
}
else
{
q=start;
while(q->next!=NULL)
q=q->next;
q->next=tmp;
tmp->prev=q;
}
}/*End of create_list()*/

addatbeg(int num)
{
struct node *tmp;
tmp=malloc(sizeof(struct node));
tmp->prev=NULL;
tmp->info=num;
tmp->next=start;
start->prev=tmp;
start=tmp;
}/*End of addatbeg()*/

addafter(int num,int c)
{
struct node *tmp,*q;
int i;
q=start;
for(i=0;i<c-1;i++)
{
q=q->next;
if(q==NULL)
{
printf("There are less than %d 

elements\n",c);
return;
}
}
tmp=malloc(sizeof(struct node) );
tmp->info=num;
q->next->prev=tmp;
tmp->next=q->next;
tmp->prev=q;
q->next=tmp;
}/*End of addafter() */

del(int num)
{
struct node *tmp,*q;
if(start->info==num)
{
tmp=start;
start=start->next;  /*first element deleted*/
start->prev = NULL;
free(tmp);
return;
}
q=start;
while(q->next->next!=NULL)
{
if(q->next->info==num)     /*Element deleted in 

between*/
{
tmp=q->next;
q->next=tmp->next;
tmp->next->prev=q;
free(tmp);
return;
}
q=q->next;
}
if(q->next->info==num)    /*last element deleted*/
{ tmp=q->next;
free(tmp);
q->next=NULL;
return;
}
printf("Element %d not found\n",num);
}/*End of del()*/

display()
{
struct node *q;
if(start==NULL)
{
printf("List is empty\n");
return;
}
q=start;
printf("List is :\n");
while(q!=NULL)
{
printf("%d ", q->info);
q=q->next;
}
printf("\n");
}/*End of display() */

count()
{ struct node *q=start;
int cnt=0;
while(q!=NULL)
{
q=q->next;
cnt++;
}
printf("Number of elements are %d\n",cnt);
}/*End of count()*/

rev()
{
struct node *p1,*p2;
p1=start;
p2=p1->next;
p1->next=NULL;
p1->prev=p2;
while(p2!=NULL)
{
p2->prev=p2->next;
p2->next=p1;
p1=p2;
p2=p2->prev; /*next of p2 changed to prev */
}
start=p1;
}/*End of rev()*/


===========================================

Code:

# include <stdio.h>
# include <stdlib.h>
struct dnode
{
int data;
struct dnode *prev, *next;
};

struct dnode *insert(struct dnode *p , struct dnode **q, int n)
{
struct dnode *temp;

 if(p==NULL)
 {
  p=(struct dnode *)malloc(sizeof(struct dnode));
  if(p==NULL)
  {
  printf("Error Occurred\n");
  exit(0);
  }
   p->data = n;
   p-> prev = p->next =NULL;
   *q =p;
  }
  else
  {
  temp =  (struct dnode *)malloc(sizeof(struct dnode));

 if(temp == NULL)
 {
  printf("Error Occurred\n");
  exit(0);
 }
   temp->data = n;
   temp->prev = (*q);
   temp->next = NULL;
   (*q)->next = temp;
   (*q) = temp;
 }
   return (p);
}

void printnode( struct dnode *p  )
{
 printf("All data of created list is\n");
 while (p!= NULL)
 {
  printf("%d\t",p-> data);
  p = p->next;
 }
}

void main()
{
 int n;
 int x;
 struct dnode *start = NULL ;
 struct dnode *end = NULL;
 printf("Enter the number of nodes to be created \n");
 scanf("%d",&n);
 while ( n-- > 0 )
 {
 printf( "Enter the data values for each node\n");
 scanf("%d",&x);
 start = insert ( start , &end,x );
 }
 printnode( start );
}

Output:




================================================================
======

Circular Linked List

Description:

In the circular linked list the link of lat node is connected to the first node.

Code:

# include <stdio.h>
# include <stdlib.h>
struct node
{
int data;
struct node *link;
};
struct node *insert(struct node *p , int n)
{
struct node *temp;

 if(p==NULL)
 {
  p=(struct node *)malloc(sizeof(struct node));
  if(p==NULL)
  {
   printf("Error Occurred\n");
   exit(0);
  }
   p-> data = n;
   p-> link = p;
  }
  else
  {
 temp = p;
 while (temp-> link != p)
 temp = temp-> link;
 temp-> link =  (struct node *)malloc(sizeof(struct node));
 if(temp -> link == NULL)
  {
  printf("Error Occurred\n");
  exit(0);
  }
  temp = temp-> link;
  temp-> data = n;
  temp-> link = p;
   }
   return (p);
}
void printlist ( struct node *p  )
{
  struct node *temp;
  temp = p;
  printf("The data in the list are :\n");
  if (p!= NULL)
  {  do
   {
   printf("%d\t",temp-> data);
   temp=temp->link;
   }while(temp!=p);
  }
  else
  printf("The link is empty \n");
}
void main()
{
 int num;
 int value;
 struct node *start = NULL ;
 printf("Enter the number of nodes to be created \n");
 scanf("%d",&num);
 while ( num-- > 0 )
 {
 printf( "Enter the data to be placed in a node\n");
 scanf("%d",&value);
 start = insert ( start , value );
 }
  printlist ( start );
}

Output:


Count number of nodes

This tutorial demonstrate how to count the number of nodes present in the linked list.

Code:

# include <stdio.h>
# include <stdlib.h>
struct node
{
int data;
struct node *link;
};
struct node *insert(struct node * , int);
int countnode(struct node*);
void printlist (struct node *);

struct node *insert(struct node *p , int n)
{
 struct node *temp;
 if(p==NULL)
 {
  p=(struct node *)malloc(sizeof(struct node));
  if(p==NULL)
  {
   printf("Error Occurred\n");
     exit(0);
  }
   p-> data = n;
   p-> link = NULL;
  }
  else
  {
  temp = p;
  while (temp-> link!= NULL)
   temp = temp-> link;
temp-> link =  (struct node *)malloc(sizeof(struct node));
  if(temp -> link == NULL)
  {
   printf("Error Occurred\n");
   exit(0);
  }
  temp = temp-> link;
  temp-> data = n;
  temp-> link = NULL;
   }
   return (p);
}


void printlist ( struct node *p  )
{
 printf("The data in the list are\n");
 while (p!= NULL)
 {
  printf("%d\t",p-> data);
  p = p-> link;
 }
}

int  countnode (struct node *p )
{
 int count=0;
 while (p != NULL)
 {
   count ++;
   p = p->link;
 }
  return(count);
}


void main()
{
 int n;
 int x;
 struct node *start = NULL ;
 printf("Enter number of nodes to be created \n");
 scanf("%d",&n);
 while ( n-- > 0 )
 {
  printf( "Enter the data for node\n");
  scanf("%d",&x);
  start = insert ( start ,x);
 }
 printlist ( start );
 n = countnode(start);
 printf("\nThe number of nodes in a list are: %d\n",n);
}

Output:



Split a list into two equal size list


Description:

In this example it has mainly three function one for inserting data into list another for printing the list and last one for split of list. 

Code:

# include <stdio.h>
# include <stdlib.h>
struct node
{
int data;
struct node *link;
};

void splitlist(struct node *p, struct node **q, int n)
     {
      struct node *temp;
 int  i =1;
 temp = p;
 while( i < n)
 {
  temp  =  temp->link;
  i++;
 }
 *q = temp->link;
 temp->link  =  p;
 temp = *q;
  while(temp->link != p)
  temp = temp ->link;
  temp->link = *q;
 }


struct node *insertnode(struct node *p , int n)
{
struct node *temp;
 if(p==NULL)
 {
 p=(struct node *)malloc(sizeof(struct node));
  if(p==NULL)
  {
  printf("Error\n");
  exit(0);
  }
  p-> data = n;
  p-> link = p;
 }
  else
 {
 temp = p;
 while (temp-> link != p)
 temp = temp-> link;
 temp-> link =(struct node *)malloc(sizeof(struct node));
 if(temp -> link == NULL)
 {
  printf("Error\n");
  exit(0);
 }
 temp = temp-> link;
 temp-> data = n;
 temp-> link = p;
 }
 return (p);
}
void printlist ( struct node *p  )
{
struct node *temp;
temp = p;
printf("The data values in the list are\n");
  if(p!= NULL)
   do
   {
   printf("%d\t",temp->data);
   temp=temp->link;
   } while (temp!= p);

  else
   printf("empty list\n");
 }

void main()
{
 int n,num;
 int x;
 struct node *start1 = NULL ;
 struct node *start2=NULL;
 printf("Enter the number of node for each splited list \n");
 scanf("%d",&n);
 num = n;
 n*=2; /* this is done to have data multiple of two
  so that it split into two equal parts. */
 while ( n-- > 0 )
 {
 printf( "\nEnter data to be placed in node\n");
 scanf("%d",&x);
 start1 = insertnode ( start1 , x );
 }
 printlist ( start1 );
 splitlist(start1,&start2,num);
 printf("\nFirst list is:\n");
 printlist(start1);
 printf("\nSecond list is:\n");
 printlist(start2);

}


No comments:

Post a Comment