Doubly Linked List | Data Structure
image source: medium.com
***Table of contents***
1. Doubly Linked List Structure.
2. Creating a Doubly Linked List with the given size.
3. Printing the Doubly Linked List.
4. Length of the Linked List.
5. Insertion of a node at Linked List.
6. Deletion of all nodes containing a particular value from the Linked List.
7. Reversing the Doubly Linked List.
CODE in C/C++:
#include<bits/stdc++.h>
using namespace std;
//1.Doubly Linked List structure
typedef struct Node{
Node* prev;
int data;
Node* next;
}Node;
//2.
/**
* @brief Creates a Doubly Linked List with given size.
*
* @param n - the length of the Linked List
* @return Node*
*/
Node* Create_DLL(int n){
Node* head=nullptr,*tail=nullptr;
int data;
while (n--)
{
cin>>data;
if(!head){
head = (Node*)malloc(sizeof(Node));
head->data = data;
head->prev = head->next = nullptr;
tail = head;
continue;
}
Node* t = (Node*)malloc(sizeof(Node));
t->data = data;
t->prev = tail;
t->next = nullptr;
tail->next = t;
tail = t;
}
return head;
}
//3. Prints the linked list
void Display(Node* head){
if(!head){
cout<<endl;
return;
}
cout<<head->data<<" ";
Display(head->next);
}
//4.
/**
* @brief Returns the doubly linked list's length
*
* @param head
* @return int
*/
int length(Node* head){
int l = 0;
Node* cur = head;
while(cur){
++l;
cur = cur->next;
}
return l;
}
//5.
/**
* @brief Inserts a node in the linked list
*
* @param head
* @param data
* @param pos
* @return Node*
*/
Node* InsertNodeAtDLL(Node* head, int data, int pos){
Node* t = (Node*) malloc(sizeof(Node));
t->data = data;
if(pos<=0){
t->prev = nullptr;
t->next = head;
head->prev = t;
head = t;
return head;
}
else if(pos>0 and pos<length(head)){
Node* q=head,*p=head;
for(int i=1; i<=pos; ++i){
q = p;
p = p->next;
}
if(p){
t->prev = q;
t->next = p;
q->next = t;
p->prev = t;
}
}
else{
Node* q=head,*p=head;
while (p->next)
{
p = p->next;
}
t->next = nullptr;
t->prev = p;
p->next = t;
}
return head;
}
//6.
/**
* @brief Deletes all the nodes from the Linked list with the given value.
*
* @param head
* @param data
* @return Node*
*/
Node* DeleteNodeFromDLL(Node* head, int data){
Node* p = head,*q=head;
while(p){
if(p->data==data && p==q){
head = head->next;
p = q = head;
continue;
}
else if(p->data==data){
if(p->next){
q->next = p->next;
p->next->prev = q;
p = q;
}
else{
q->next = nullptr;
}
}
q = p;
p = p->next;
}
return head;
}
//7.
/**
* @brief Reverses the Doubly Linked List
*
* @param head
* @return Node*
*/
Node* ReverseDLL(Node* head){
Node* t,*p;
while(head){
t = head->next;
head->next = head->prev;
head->prev = t;
head = head->prev;
if(head!=nullptr and head->next==nullptr){
p = head;
}
}
return p;
}
int main()
{
int n;
cout<<"Enter the length of the Linked List: ";
cin>>n;
Node* head = Create_DLL(n);
Display(head);
int val,pos;
cout<<"Enter the value to insert: ";
cin>>val;
cout<<"Enter the position to insert: ";
cin>>pos;
head = InsertNodeAtDLL(head, val, pos);
Display(head);
cout<<"Enter the data you want to delete: ";
cin>>val;
head = DeleteNodeFromDLL(head,val);
Display(head);
head = ReverseDLL(head);
Display(head);
free(head);
return 0;
}
Posts
No comments