Home » Interview Questions » LinkedList Interview Questions » Create a Doubly Linked List

Create a Doubly Linked List


()

Write a program to Create a doubly linked list

A double linked list contains an extra pointer to its previous node. So, it contains pointer to next, previous and its value.

Examples

Doubly linked list

 

Adding element at end of the list

Add in front of the list

Add in between nodes of the list

Algorithm

Create a doubly linked list structure which contains the value of the node, pointer to next node and pointer to previous node.

Step 1 : Creating a function which takes the pointer and value as arguments and add them in the list where ever you want.
Step 2 : allocate a node by creating a new node. Initializing structure of new node as a node of linked list.
Step 3 : put the data into the node.
a)    node->data = given data.
Step 4 :
a)    Make next of new node as head and previous as null if you want to create a node in front.
b)    If you want to add a node at last, make next of new node be null.
i)    If linked list is empty, then make the new node as head.
j)    If linked list is not empty, traverse till the last node by moving pointers and change the next of last node to the new node.
k)    Make last node as previous of the new node.
c)    If you want to add a node in between, make next of the new node as next of previous node. make previous of new node to next node. New node`s previous is previous node, make next of previous node as new node.
Step 5 : call the function on given nodes.

READ  Merge Two Sorted Lists Leetcode

C++ Program

#include <bits/stdc++.h>
using namespace std;

struct DLL{
	int data;
	DLL *next;
	DLL *prev;
};

void insertAtBeginning(struct DLL **head, int X)
{
	struct DLL * curr = new DLL;
	curr->data = X;
	curr->prev = NULL;
	curr->next = *head;
	if(*head != NULL)
	(*head)->prev = curr;
	*head = curr;
	
}

void display(struct DLL**head)
{
	struct DLL*temp=*head;
	while(temp!=NULL)
		{
			if(temp->next!=NULL)
			cout<<temp->data<<" ->";
			else
			cout<<temp->data;
			
			temp=temp->next; //move to next node
		}
		//O(number of nodes)
	cout<<endl;
}


int main()
{
	struct DLL *head = NULL;
	insertAtBeginning(&head,6);
	insertAtBeginning(&head,16);
	insertAtBeginning(&head,15);
	insertAtBeginning(&head,50);
	insertAtBeginning(&head,1);
	insertAtBeginning(&head,23);
	cout<<"Current list is :- \n";
	display(&head);
	
}

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions