CS Code

Coding, quiz & more

Types of Linked List

In this tutorial, we are going to learn the Linked List Types and their implementation.

Types of Linked List are

  • Singly Linked List
  • Doubly Linked List
  • Singly Circular Linked List
  • Doubly Circular Linked List

1) Singly Linked List

We have covered Singly Linked List in previous tutorials. Visit Linked List Data Structure and Operations On Linked List to learn more about Singly Linked List.

2) Doubly Linked List

Doubly Linked List

There is additional pointer to the previous node so we can go in both directions i.e. forward and backward.

Node Representation: 


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

Operations on Doubly Linked List

  • Insert
    • Insert At Start
    • Insert At End
    • Insert By Position
    • Insert By Data
  • Delete
    • Delete At Start
    • Delete At End
    • Delete By Position
    • Delete By Data
  • Traverse/Display : Traversing means visiting every node of the linked list at once.

Insert Operation:

Insert At Start:

We are using two pointer

  1. Starting pointer(st) (also called head) and
  2. End pointer(end) (point to end node of doubly linked list)
  • Allocate memory for new node using malloc()
  • Store data in the node
  • If starting pointer is null(i.e. Linked List is empty) then point starting pointer to new node
  • If Linked List is not null then point new node of next pointer to starting pointer, pre of starting pointer to new node and starting pointer to new node like mentioned in code below.
void insert_at_start()
{
	struct node *new;
	new=(node *)malloc(sizeof(struct node));
	
	if(new==NULL)  //error while allocating memory using malloc
	{
		printf("\nError:\nOverflow\n\n");
		return 0;
	}

	printf("\nEnter Data:  ");
	scanf("%d",&new->data);
	

	if(st==NULL) //st is starting pointer
	{
		st=new;
		end=new;
		new->pre=NULL;
		new->nxt=NULL;
	}
	else
	{
		new->pre=NULL;
		new->nxt=st;
		st->pre=new;
		st=new;
	}
}
Insert At End:

This operation is similar to insert at start operation because we have used two pointers st (point at start) and end(point at end) pointer.

void insert_at_end()
{
	struct node *new;
	new=(node *)malloc(sizeof(struct node));
	
	if(new==NULL)  //error while allocating memory using malloc
	{
		printf("\nError:\nOverflow\n\n");
		return 0;
	}

	printf("\nEnter Data:  ");
	scanf("%d",&new->data);
	
	if(st==NULL)
	{
		st=new;
		end=new;
		new->pre=NULL;
		new->nxt=NULL;
	}
	else
	{
		end->nxt=new;
		new->nxt=NULL;
		new->pre=end;
		end=new;
	}
}
Insert By Data
void insert_by_data()
{
	struct node *new;
	new=(node *)malloc(sizeof(struct node));
	
	if(new==NULL)  //error while allocating memory using malloc
	{
		printf("\nError:\nOverflow\n\n");
		return 0;
	}

	
	int data;
	printf("\nEnter data at which you want to insert:");
	scanf("%d",&data);
	
	if(st==NULL)
	{
		printf("\nLisked List is empty.\n");
		return 0;
	}
	
	if(st->data==data)  // if data found at start of DLL
	{
		insert_at_start();
		return 0;
	}

	t=st;
	
	while(t->data!=data && t!=NULL)
	{
		t=t->nxt;
	}
	if(t->data==data)  // if match found in DLL
	{
		
		printf("\nEnter Data to insert:  ");	
		scanf("%d",new->data);
		
		new->nxt=t;
		new->pre=t->pre;
		t->pre->nxt=new;
		t->pre=new;
	}
	else
		printf("\nData Not Found.\n");
}
Insert At Location
void insert_at_location()
{	
	struct node *new,*t;
	
	int loc,counter=1,temp;

	printf("\nEnter Location at which you want to insert new data:");
	scanf("%d",&loc);
	
        t=st;
	
	if(loc==1)   //if location is 1 then insert data at 1st position
	{
		insert_at_start();
		return 0;
	}
	
	new=(struct node *)malloc(sizeof(struct node));
	
	if(new==NULL)
	{
		printf("\nOverflow\n");
		return 0;
	}
		
	
	while(counter!=loc && t->nxt!=NULL)
	{
		counter++;
		t=t->nxt;
	}
	
	if(counter==loc) //if location found
	{
		printf("\nEnter Data to insert:  ");
		scanf("%d",&new->data);
		
		new->nxt=t;
		new->pre=t->pre;
		t->pre->nxt=new;
		t->pre=new;
	}
	else
		printf("\nLocation Not Found.\n");
}

Delete Operation

Delete At Start
  • Store first node in a temporary struct node pointer
  • If there is only one node in Doubly Linked List, then make st and end pointer to null and free the node.
  • If there are more than 1 nodes in DLL(Doubly Linked List) then point the start pointer to next of start pointer and make pre of starting pointer NULL.
  • Free the temporary node.
void delete_at_start()
{
	
	if(st==NULL)
	{
		printf("\n\nError:\nUnderflow\n");
		return 0;
	}
	
	struct node *t;

	t=st;
	if(st->nxt==NULL)
	{
		printf("\nDeleted Data : ",t->data);
				
		st=NULL;
		end=NULL;
		free(t);
	}
	else
	{
		printf("\nDeleted Data : ",t->data);
		
		st=st->nxt;
		st->pre=NULL;
		free(t);
	}
}
Delete At End

Its similar to delete at start operation. Check the code below.

void delete_at_end()
{
	
	if(st==NULL)
	{
		printf("\n\nError:\nUnderflow\n");
		return 0;
	}
	
	struct node *t;
	t=end;
	if(st->nxt==NULL)
	{
		printf("\nDeleted Data : ",t->data);

		st=NULL;
		end=NULL;
		free(t);
	}
	else
	{
		printf("\nDeleted Data : ",t->data);

		end=end->pre;
		end->nxt=NULL;
		free(t);
	}
}
Delete By Data

Procedure is same like we used in insert by data operation. First find the data from the linked list and then perform delete operation as mentioned below.

void delete_by_data()	
{
			
	if(st==NULL)
	{
		printf("\n\nError:\nUnderflow\n");
		return 0;
	}
	
	struct node *t,*temp;
	t=st;
	
	int data;
	printf("\nEnter data at which you want to Delete:");
	scanf("%d",&data);
	
	if(st->data==data)
	{
		delete_at_start();
		return 0;
	}
	
	while(t->data!=data && t->nxt!=NULL)
	{
		t=t->nxt;
	}
	temp=t;
	t=st;
	
	while(t->nxt!=NULL)
	{
		t=t->nxt;
	}
	if(t->data == data)  // if data is present in the last node
	{
		delete_at_end();
		return 0;
	}
	if(temp->data == data)
	{
		printf("\nDeleted Data : ",t->data);

		t->pre->nxt = t->nxt;
		t->nxt->pre = t->pre;
	}
	else
		printf("\nData Not Found.\n");
		
}
Delete At Location
void delete_at_location()
{
			
	if(st==NULL)
	{
		printf("\n\nError:\nUnderflow\n");
		return 0;
	}
	
	struct node *t;
	t=st;
	
	int loc,counter=1,temp;
	printf("\nEnter Location:");
	scanf("%d",&loc);
	
	if(loc==1)
	{
		delete_at_start();
		return 0;
	}
	
	while(counter!=loc && t->nxt!=NULL)
	{
		counter++;
		t=t->nxt;
	}
	temp=counter;
	counter=1;
	t=st;
	while(t->nxt!=NULL)
	{
		counter++;
		t=t->nxt;
	}
	if(counter==loc)
	{
		
		delete_at_end();
		return 0;
	}
	if(temp==loc)
	{
		printf("\nDeleted Data : ",t->data);
		
		t->pre->nxt = t->nxt;
		t->nxt->pre = t->pre;
	}
	else
		printf("\nLocation Not Found\n");
}

Traverse/Display

  • If Doubly Linked List is empty then print/return DLL is empty.
  • Visit from start to end of the linked list and print the data.
void display()
{
	if(st==NULL)
	{
		printf("\nLinked List Is Empty\n\n");
		return 0;
	}
	
	struct node *t;
	
	t=st;
	while(t!=NULL)
	{
		printf("%d: Data\n",i,t->data);		
		i++;
		t=t->nxt;
	}
}
			
	
//Task: display data from end of the DLL to start of the Doubly Linked  List.

Singly Circular Linked List

A circular linked list is a type of a linked list in which the last element of the linked list points to the first element. This forms a circular ring or circular loop.

For singly Circular linked list, the next pointer of last node points to the first node i.e head(or starting pointer).

Doubly Circular Linked List

In the doubly circular linked list, prev pointer of the first node points to the last node and next pointer of last node points to the first node.

‹ Operations On Linked List
›

Back to top