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.

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);
	
}

Translate »