Linked List Explanation

explanation of linked list: clisk here Linked List Explanation.

Adding nodes, inserting, deleting a node in a linked list using functions

program for�Adding nodes, inserting, deleting a node in a linked list using functions.

Simple Linked Program to create a linked list:

 

 

 

Here is a simple linked list program to create a linked list and display it:

Simple Linked Program to create a linked list:.

Linked List Explanation

What is a linked list exactly?

-> a linked list is a data structure consisting of a group of nodes which together represent a sequence.

A linked list consists of nodes which are linked together. Every node consists of two parts the data(or info) and the link part.

the data part or the info part contains our data and the link part contains the address of the next data element.

what is the use if i can use array for creating a list of certain elements?

yes you can create a list of elements using array but in array the elements are stored one after the after in continuos memory location, the problem arises when the data is stored randomly and we want to link that data. then  linked list comes into picture.

here is a short example:

consider i have to create a list of alphabets presents in my name i.e M,A,Y,U,R

but consider that M is stored at say memory location 1000, A is stored at 3276, Y at 6734, U at 7834 and R at 1235. Now how to link them?

I will create 5 nodes for this each containing the data part i.e the individual alphabet and the link part i.e the address of the next alphabet. we declare a start for storing the starting address i.e the address of M.

how it works?

the control will go to memory location 1000 from start i.e to ‘M’, the link of ‘M’ contains the address of ‘A’ so the control will jump to address 3276, now the link part of ‘A’  contains the address of ‘Y’ i.e 6734, the control will jump to ‘Y’ and so on. the link part of ‘R’ is empty i.e it is defined as NULL. so the control stops there and the linking is completed.

this is how it works.

hope so till now you have understood the basic idea behind linked list!

now comes the programming part,

In C we use structures for creating a linked list and in C++ we use classes and objects. lets concentrate on structures first.

A structure is basically collection of different data types. to know more about structures refer ‘Let Us C’. it is given very nicely.

how to declare a structure?

struct <structure_name>
{
	structure element1;
	structure element2;
	.......
}var1,var2;

or 

struct <structure_name>
{
	structure element1;
	structure element2;
	.......
};

struct <structure_name> var1,var2;
var1,var2... are called as structure variable.

Now the question arises why to use structures in linked list?

-> See we have to create nodes for linked list, the node contains data and link part,  for this data and link part we will have to define two variables as data and a pointer for link part,

but by using structures we can treat node as a single unit which contains data and link int it. so we will define a structure which contains data as a integer variable and link as a  pointer variable.

let’s define the structure:

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

the structure with name as node it contains two members data who’s data type is int and next which is  a pointer which points to the next node which is  again a structure, so if we are declare a pointer which points to int we declare it as int *ptr, now the pointer points to an integer value, in this structure we are declaring a pointer next which points to another structure so its data type should be struct node, so we have declared it as struct node *next.

following is a small code which creates a linked list, and adds nodes at the beg and at the end and at the end displays the linked list.

#include<stdio.h>
#include<conio.h>
#include<malloc.h>
int node_count=0;
struct node
{
	int data;
	struct node *next;
};
main()
{
	struct node *sp,*last,*temp,*newnode;
	int i,n,j,k,r=0,count=0;
	clrscr();
	printf("Enter the data of the first node: ");
	last=(struct node *)malloc(sizeof(struct node));
	scanf("%d",&last->data);
	last->next=NULL;
	sp=last;
	node_count++;
	//_________________ADDING A NODE AT THE BEG_____________________//
	printf("\n\nHow many nodes you want to add the beg: ");
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		newnode=(struct node *)malloc(sizeof(struct node));
		printf("\nenter the data: ");
		scanf("%d",&newnode->data);
		newnode->next=sp;
		sp=newnode;
		node_count++;
	}
	//_________________ADDING A NODE AT THE END_____________________//
	printf("\n\nHow many nodes you want to add the end: ");
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		newnode=(struct node *)malloc(sizeof(struct node));
		printf("\nenter the data: ");
		scanf("%d",&newnode->data);
		newnode->next=NULL;
		last->next=newnode;
		last=newnode;
		node_count++;
	}
	//_________________DISPLAYING ALL NODES_____________________//
	temp=sp;
	for(i=1;i<=node_count;i++)
	{
		printf("\n\nnode %d contains data %d address of next node: %u",i,temp->data,temp->next);
		temp=temp->next;
	}
	getch();
}

First we include header files #include<stdio.h> and #include<malloc.h>.

malloc.h is included because we are using  a inbuilt library function named malloc(); we will come to it later.

we declare and define the structure node as mentioned above.

in the main()  we declare four pointer to a structure variable i.e are *sp,*last,*temp,*newnode  and their datatype is struct node.

for creating a link list we first create a single node and then add nodes at the begining or at the end.

lets refer the first node as last, because in a linked list with only one node the first element can also be treated as the last element.

so creating a node we have to allocate some memory for that node this is done by the malloc() function.

the syntax for the malloc function is:

variable=(data type of variable)malloc(size of the the data type);

now we are allocating memory for a node i.e to the variable last therefore the syntax will be:

last=(struct node *)malloc(size of (struct node));

since the data type of last is struct node and the sizeof() function calculates the size of the data type i.e struct node.

now we have to input the data in that node. the data part is accessed by -> operator. i.e the value of data is stored in last->data. we accept it by scanf() function. as it is the first and the only node,  there is no node after that so the next part of the last is not pointing to any another node so the next part of the last should be NULL, we access the next part of the last, same like we accessed the data part. i.e last->next=NULL.

now we have created a last node, we need a start pointer also called as header to keep a track of the fist node, it always stores the address of the first node, the address of the first node is stored in last so we need to store this address in the staring pointer i.e sp it is done by sp=last;

now we have sp with address of the first node and the a single node named as last. to add more nodes we have two choices i.e we can either add it at the beginning of the list or at the end.

the algo for adding at the beginning is: we have to store the address of newnode in the sp, access the data of the newnode, the next part of the newnode should contain the address of the next node.

similarly for newnode we need some memory to be allocated. that is done by

newnode=(struct node *)malloc(sizeof(struct node));

currently the address of the first node is stored in sp and we inserting the newnode before the first node.

so the next part of the newnode should contain the address stored in sp

therefore newnode->next=sp; the newnode now becomes the first node do the address of the first node should be stored in the sp,

therefor sp=newnode. we repeat this algorithm for n number of times for n number of nodes using for.

now algo for adding the node at the end: currently the address of the last node is stored in last. we have to add newnode after the last node, as the newnode will become our last node, so  the next part of the newnode should be NULL

i.e newnode->next=NULL,  now the last contains the address of the node previous to the newnode so the next part of the last should contain the address of newnode i.e last->next=newnode.

now we redefine newnode as the last node by storing the address of newnode in the last i.e last=newnode.

now displaying the linked list!

Simple Linked Program to create a linked list:

#include<stdio.h>
#include<conio.h>
#include<malloc.h>
int node_count=0;
struct node
{
	int data;
	struct node *next;
};
main()
{
	struct node *sp,*last,*temp,*newnode;
	int i,n,j,k,r=0,count=0;
	clrscr();
	printf("Enter the data of the first node: ");
	last=(struct node *)malloc(sizeof(struct node));
	scanf("%d",&last->data);
	last->next=NULL;
	sp=last;
	node_count++;
	//_________________ADDING A NODE AT THE BEG_____________________//
	printf("\n\nHow many nodes you want to add the beg: ");
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		newnode=(struct node *)malloc(sizeof(struct node));
		printf("\nenter the data: ");
		scanf("%d",&newnode->data);
		newnode->next=sp;
		sp=newnode;
		node_count++;
	}
	//_________________ADDING A NODE AT THE END_____________________//
	printf("\n\nHow many nodes you want to add the end: ");
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		newnode=(struct node *)malloc(sizeof(struct node));
		printf("\nenter the data: ");
		scanf("%d",&newnode->data);
		newnode->next=NULL;
		last->next=newnode;
		last=newnode;
		node_count++;
	}
	//_________________DISPLAYING ALL NODES_____________________//
	temp=sp;
	for(i=1;i<=node_count;i++)
	{
		printf("\n\nnode %d contains data %d address of next node: %u",i,temp->data,temp->next);
		temp=temp->next;
	}
	getch();
}

Adding nodes, inserting, deleting a node in a linked list using functions

#include<stdio.h>
#include<malloc.h>
int node_count=0;
struct node
{
 int data;
 struct node *next;
};
//_________________FUNCTION FOR DISPLAYING A NODE_____________________//
void display(struct node *temp)
 {
  int i; for(i=1;i<=node_count;i++)
  {
   printf("\n\nnode %d contains data %d address of next node: %u",i,temp->data,temp->next);
   temp=temp->next;
  }
 }
//_________________FUNCTION FOR ADDING A NODE AT THE BEG______________//
struct node *add_at_start(struct node *temp)
 {
  struct node *new_node;
  new_node=(struct node*)malloc(sizeof(struct node));
  printf("\nEnter the data element: ");
  scanf("%d",&new_node->data);
  new_node->next=temp;
  node_count++;
  return new_node;
 }
 struct node *add_at_end(struct node *last)
 {
  struct node *new_node;
  new_node=(struct node*)malloc(sizeof(struct node));
  printf("\nEnter the data element: ");
  scanf("%d",&new_node->data);
  last->next=new_node;
  new_node->next=NULL;
  node_count++;
  return new_node;
 }
//_________________FUNCTION FOR INSERTING A NODE_____________________//
void insert_node(int n1,int n2,struct node *prev_node)
 {
 int i;
 struct node *new_node;
    if(n1<node_count&&n2<=node_count&&n1==n2-1)
     {
      for(i=1;i<=n1-1;i++)
      {
	prev_node=prev_node->next;
      }
      new_node=(struct node*)malloc(sizeof(struct node));
      printf("\nEnter the data element: ");
      scanf("%d",&new_node->data);
      new_node->next=prev_node->next;
      
      prev_node->next=new_node;
      node_count++;
     }
      }
//_________________FUNCTION FOR DELETING A NODE_____________________//
 void delete_node(int n1,struct node *prev_node)
 {
 int i;
 struct node *node_n1;
  if(n1<=node_count)
   {
    for(i=1;i<=n1-2;i++)
    {
     prev_node=prev_node->next;
    }
    node_n1=prev_node->next;
    prev_node->next=node_n1->next;
    node_count--;
   }
   }
void main()
{
 int ch,n1,n2,n,i;
 struct node *sp,*last;
 last=(struct node*)malloc(sizeof(struct node));
 printf("\nEnter data element of first node ");
 scanf("%d",&last->data);
 sp=last;
 last->next=NULL;
 node_count++;
	//_________________ADDING A NODE AT THE BEG_____________________//
	printf("\n\nHow many nodes you want to add the beg: ");
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		sp=add_at_start(sp);
	}
	//_________________ADDING A NODE AT THE END_____________________//
	printf("\n\nHow many nodes you want to add the end: ");
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		last=add_at_end(last);
	}
	//_________________INSERTING A NODE_____________________//
	printf("\n\nBetween which two node do you want to insert: ");
	scanf("%d%d",&n1,&n2);
	insert_node(n1,n2,sp);
	//_________________DELETING A NODE_____________________//
	printf("\n\nWhich Node do you want to delete: ");
	scanf("%d",&n1);
	delete_node(n1,sp);
	//_________________DISPLAYING ALL NODES_____________________//
	display(sp);
}

How to Reverse A Linked List?

Add this code to Reverse A linked List:

define header, current, result, temp with data type struct node * i.e

(where  header is the starting pointer of the linked list.)

 

struct node *header, *current, *temp, *result;

result=NULL;

current=header;
while(current!=NULL)
{
       temp=current->next;
       current->next=result;
       result=current;
       current=temp;
}
header=result;

A cricket Simulator in C by Sendhilkumar404

PROGRAMMING is an art, spellbinding everyone of us. As we advance towards the end of the semester, we expect an impulse that would drive everyone crazy about this art even when it is not a part of the curriculum.

Following Ankush in an attempt to exceed the application of programming knowledge, I have come up with a cric simulator. The simulator is purely an application of elementary CPP functions of cin and cout which are equivalent by all means to the scanf and printf used in C. The flexibility of code to simulate scores of all limited over formats could be appreciated .Suggestions for improving the code will be greatly valued.

I hope this inspires many of you to come up with such programs. Decoding C will encourage everyone who wants to try something of this sort.

click here to view the code: A cricket Simulator. by Sendhilkumar