C program to implement Double Linked List in C

-

Doubly Linked List

Before going towards the doubly linked list, I hope that you have the knowledge about the Singly Linked List. If not, then click here.

Doubly Linked List is a variation of Linked list in which navigation is possible in both ways, either forward and backward easily as compared to Single Linked List. Following are the important terms to understand the concept of doubly linked list.
  • 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.
  • Prev − Each link of a linked list contains a link to the previous link called Prev.

Doubly Linked List Representation


As per the above illustration, following are the important points to be considered.
  1. Doubly Linked List contains a link element called first and last.
  2. Each link carries a data field(s) and two link fields called next and prev.
  3. Each link is linked with its next link using its next link.
  4. Each link is linked with its previous link using its previous link.
  5. The last link carries a link as null to mark the end of the list.

Basic Operations

Following are the basic operations supported by a list.
  • Insertion − Adds an element at the beginning of the list.
  • Deletion − Deletes an element at the beginning of the list.
  • Insert Last − Adds an element at the end of the list.
  • Delete Last − Deletes an element from the end of the list.
  • Insert After − Adds an element after an item of the list.
  • Delete − Deletes an element from the list using the key.
  • Display forward − Displays the complete list in a forward manner.
  • Display backward − Displays the complete list in a backward manner.
Let us check out the code :)


#include <stdio.h> 
#include <conio.h>
#include
typedef struct node
{
     struct node *prev;
     int data;
     struct node *next;
}node;
node *first, *last, *new1, *temp, *temp1, *temp2;
int ch,loc,value;

void create();
void clean();
void insert();
void insert_begin();
void insert_end();
void insert_pos();
void delete_end();
void delete_pos();
void delete_begin();
void display();

void main()
{

    clrscr();
    //first=NULL;
    while(1)
    {
		printf("\n***DOUBLE LINKED LIST OPERATIONS:****");
		printf("\n                MENU                             ");
		printf("\n---------------------------------------");
		printf("\n 1.Create     ");
		printf("\n 2.Display   ");
		printf("\n 3.Insert ");
		printf("\n 4. Delete");
		printf("\n 5.Exit       ");
		printf("\n--------------------------------------\n");
		printf("Enter your choice:\t");
		scanf("%d",&ch);
		switch(ch)
		{
			case 1:
					create();
					break;
			case 2:
					display();
					break;
			case 3:
					insert();
					break;
			case 4:
					clean();
					break;
			case 5:
					exit(0);
			default:
					printf("\n Wrong Choice:\n");
					break;
		}
	}

}

void display()
{
     temp=first;
     if(temp==NULL)
      {
	 printf("List is Empty");
      }
      printf("\nThe list of elements are:\n");
     while(temp!=NULL)
     {
	  printf("\t%d ",temp->data);
	  temp=temp->next;
     }
}

void create()
{
	struct node *temp,*new1;
	new1=(struct node *)malloc(sizeof(struct node));
	if(new1==NULL)
	{
		printf("\nOut of Memory Space:\n");
		exit(0);
	}
	printf("\nEnter the data value for the node:\t");
	scanf("%d",&new1->data);
	new1->prev=NULL;
	new1->next=NULL;
	if(first==NULL || last==NULL)
	{
		first=last=new1;
	}
	else
	{
		temp=first;
		while(temp->next!=NULL)
		{
			temp=temp->next;
		}
		temp->next=new1;
	}
}

void insert()
{
	int ch;
	printf("\n1. Insert at beginning \n2. Insert at last \n3. Insert at specific location");
	printf("\nEnter your choice:  ");
	scanf("%d",&ch);
	switch(ch)
	{
		case 1:
			insert_begin();
			break;
		case 2:
			insert_end();
			break;
		case 3:
			insert_pos();
			break;
		default:
			printf("Invalid choice");
	}
}

void insert_begin()
{
     struct node *new1;
     new1=(struct node *)malloc(sizeof(struct node));
     if(new1==NULL)
	{
		printf("\nOut of Memory Space:\n");
		return;
	}
     printf("\nEnter the data value for the node:\t" );
	scanf("%d",&new1->data);
	new1->prev =NULL;
	new1->next =NULL;
	if(first==NULL && last==NULL)
	{
		first=last=new1;
	}
	else
	{
		new1->next=first;
		first->prev=new1;
		new1->prev=NULL;
		first=new1;
	}
	display();
}



void insert_end()
{
     new1=(struct node *)malloc(sizeof(struct node));
     if(new1==NULL)
	{
		printf("\nOut of Memory Space:\n");
		return;
	}
	printf("\nEnter the data value for the node:\t" );
	scanf("%d",&new1->data);
	new1->next=NULL;
	new1->prev=NULL;
	if(first==NULL && last==NULL)
	{
		first=last=new1;
	}
	else
	{
		temp=first;
		while(temp->next!=NULL)
		{
			temp=temp->next ;
		}
		temp->next =new1;
		new1->prev=temp;
	}
	display();
}

void insert_pos()
{
	struct node *ptr,*temp;
	int i,pos;
	new1=(struct node *)malloc(sizeof(struct node));
	if(new1==NULL)
	{
		printf("\nOut of Memory Space:\n");
		return;
	}
	printf("\nEnter the position for the new node to be inserted:\t");
	scanf("%d",&pos);
	printf("\nEnter the data value of the node:\t");
	scanf("%d",&new1->data) ;
	new1->next=NULL;
	new1->prev=NULL;
	if(pos==0)
	{
		new1->next=first;
		first=new1;
	}
	else
	{
		for(i=0,temp=first;inext;
			if(temp==NULL)
			{
				printf("\nPosition not found:[Handle with care]\n");
				return;
			}
		}
		new1->next =temp->next;
		temp->next=new1;
		new1->prev=temp;
	}
	display();
}

void clean()
{
	int choice;
	printf("\n1. Delete from beginning \n2. Delete from last \n3. Delete specific location");
	printf("\nEnter your choice:   ");
	scanf("%d",&ch);
	switch(ch)
	{
		case 1:
			delete_begin();
			break;
		case 2:
			delete_end();
			break;
		case 3:
			delete_pos();
			break;
		default:
			printf("Invalid choice");
	}

}

void delete_begin()
{
	temp=first;
	if(first==NULL && last==NULL)
	{
		printf("\nList is Empty:\n");
		return;
	}
	else
	{
		first=first->next;
		first->prev=NULL;
		printf("\nThe deleted element is :%d\t",temp->data);
		free(temp);
	}
}

void delete_end()
{
	if(first==NULL && last==NULL)
	{
		printf("\nList is Empty:");
		exit(0);
	}
	else if(first->next==NULL)
	{
		temp=first;
		first=NULL;
		printf("\nThe deleted element is:%d\t",temp->data);
		free(temp);
	}
	else
	{
		temp=first;
		while(temp->next!=NULL)
		{
			//temp=ptr;
			temp=temp->next;
		}
		last=last->prev;
		//temp->link=NULL;
		printf("\nThe deleted element is:%d\t",temp->data);
		free(temp);
	}
}

void delete_pos()
{
	int i,pos;
	if(first==NULL && last==NULL)
	{
		printf("\nThe List is Empty:\n");
		exit(0);
	}
	else
	{
		printf("\nEnter the position of the node to be deleted:\t");
		scanf("%d",&pos);
		if(pos==0)
		{
			temp=first;
			first=first->next;
			first->prev=NULL;
			printf("\nThe deleted element is:%d\t",temp->data );
			free(temp);
		}
		else
		{
			temp=first;
			for(i=0;inext;
				if(temp==NULL)
				{
					printf("\nPosition not Found:\n");
					return;
				}
			}
			temp1=temp->prev;
			temp2=temp->next;
			temp1->next=temp2;
			temp2->prev=temp1;
			temp->link =ptr->link ;
			printf("\nThe deleted element is:%d\t",temp->data);
			free(temp);
		}
	}
}


























Happy Coding :)

Comments

Post a Comment

Popular posts from this blog

MultiSelection of Item in Recycler View

-
Image
Easiest Way to Implement Multi Selection of Item in Recycler View Hello friends, in this blog post I am going to show you that how one can make a multi selection functionality for items in the Recycler View So lets get started. First add the following dependencies to your project: dependencies { implementation fileTree(dir: 'libs', include: ['*.jar']) implementation"org.jetbrains.kotlin:kotlin-stdlib-jdk7:$kotlin_version" implementation 'androidx.appcompat:appcompat:1.0.2' implementation 'androidx.constraintlayout:constraintlayout:1.1.3' testImplementation 'junit:junit:4.12' androidTestImplementation 'androidx.test:runner:1.2.0' androidTestImplementation 'androidx.test.espresso:espresso-core:3.2.0' //Recycler View Dependency implementation 'androidx.recyclerview:recyclerview-selection:1.0.0' } Now in this project we have two XML layout file: For Main...
Read more

Upload Image From Android To Php Server

-
Image
Hello friends, in this tutorial we will learn how to upload an image from android to php server. Lets go for it. Prerequisites: Android Studio Xampp or Wamp Server (I am using Xampp here) Text Editor (I recommend to use Sublime) Structure of the Database: Firstly, we use our Android Studio to make our front part ready to capture the photo and get it ready to upload on the server. To get start with the actual code add the permissions and dependencies to make the project work properly. Add below permissions in the Manifests file. <uses-permission android:name="android.permission.INTERNET"></uses-permission> <uses-permission android:name="android.permission.READ_EXTERNAL_STORAGE"></uses-permission> And add the volley dependency in the build.gradle file of the App Module. implementation 'com.android.volley:volley:1.1.1' So, initially we make our layout for the Main Activity. Here is the layout co...
Read more

Merge Sort

-
Image
Merge Sort in C In  computer science ,  merge sort  (also commonly spelled  mergesort ) is an efficient, general-purpose,  comparison-based   sorting algorithm . Most implementations produce a  stable sort , which means that the implementation preserves the input order of  equal  elements in the sorted output. Mergesort is a  divide and conquer algorithm  that was invented by  John von Neumann  in 1945. Algorithm Conceptually, a merge sort works as follows: Divide the unsorted list into  n  sublists, each containing 1 element (a list of 1 element is considered sorted). Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.
Read more