Singly, Doubly and Circular Linked List

So far, we have seen the implementation of Linked List. The Link List we implemented in the Lined List article was actually Singly Lined List. There is slightly difference between Singly, Doubly and Circular Linked List. We will see the difference and the importance of each in detail in this article.

 Singly Linked List:

In singly linked list, we keep head node in our linked list class. This head node is actually the starting point of our linked list. As shown:

The above Figure shows the representation of Singly Linked List. We have a head node in our linked list class, it is the starting point of our linked list. Every node has some data and next pointer of type Node, that point to the next node of the list. Now I will tell you what is doubly linked list an why we need it.

Doubly Linked List:

In node of singly linked list, we have only one pointer of type node but in doubly linked list we have two pointers of type node. They are generally named as next and previous. The next pointer store the address of next node and previous pointer stores the pointer of previous node.

Why needed?

Lets take an example, we have to develop a browser or any application like paint or note pad. We want to provide functionality of undo and redo to our system. We can implement it using singly linked list but it will not be a good approach and it will be difficult and complicated to implement. The best way to implement this functionality is using doubly linked list. In doubly linked list, we can go the next node as well as previous node. We can put the required data which stores information about backward and forward operation in the data variable of our node.

Diagram:

Now we will see the code to implement Doubly Linked List.

Code:

Implementation of Node class:

#pragma once

template<class T>

class list;

template <class T>

class node

{

T data;

node* next;

node* previous;

public:

    friend class list<T>;

node(T element,node* n=0,node* p=0)

{

next = n;

previous = p;

data=element;

}

node<T>* get_next_node()const

{

return next;

}

node<T>* get_previous_node()const

{

return previous;

}

T get_data()const

{

return data;

}

};

Implementation of List class:

#pragma once

#include"node.h"

template <class T>

class list

{

node<T>* head;

node<T>* tail;

int count;

public:

list ()

{

head=new node<T>(0);

tail=new node<T>(0);

head->next=tail;

tail->previous=head;

count=0;

}

void insertAtStart(T const element)

{

node<T>* temp=new node<T>(element);

temp->next=head->next;

temp->previous=head;

head->next->previous=temp;

head->next=temp;

count++;

}

void insertAtEnd(T const element)

{

node<T>* temp=new node<T>(element);

temp->next=tail;

temp->previous=tail->previous;

tail->previous->next=temp;

tail->previous=temp;

count++;

}

void deleteAtStart()

{

if(head->next!=tail)

{

node<T>* temp=head->next;

head->next=temp->next;

temp->next->previous=head;

    delete temp;

count--;

}

}

void deleteFromEnd()

{

if(head->next!=tail)

{

node<T>* temp=tail->previous;

tail->previous=temp->previous;

temp->previous->next=tail;

    delete temp;

count--;

}

}

void print()const

{

node<T>* temp=head->next;

while(temp!=tail)

{

cout<<temp->data<<"  ";

temp=temp->next;

}

cout<<endl;

}

void reverse()

{

if(count>1)

{

node<T>* temp1=head->next;

node<T>* temp2=tail->previous;

if (count % 2 == 0)

{

for (int i = 0; i < count / 2; i++)

{

swap(temp1->data, temp2->data);

temp1 = temp1->next;

temp2 = temp2->previous;

}

}

else

{

for (int i = 0; i < count / 2+1; i++)

{

swap(temp1->data, temp2->data);

temp1 = temp1->next;

temp2 = temp2->previous;

}

}

}

}

node<T>* find(T const val)

{

node<T>* temp=head->next;

while(temp!=tail)

{

if(temp->data==val)

{

return temp;

}

temp=temp->next;

}

return nullptr;

}

bool remove(node<T>*ptr)

{

node<T>* temp=head->next;

for(;temp!=tail;temp=temp->next)

{

if(temp==ptr)

{

temp->next->previous=temp->previous;

temp->previous->next=temp->next;

    delete ptr;

count--;

return true;

}

}

return false;

}

bool insertBefore(T const v1, T const v2)

{

node<T>* temp=head->next;

while(temp!=tail)

{

if(temp->data==v2)

{

            node<T>* temp2=new node<T>(v1);

temp2->next=temp;

temp2->previous=temp->previous;

temp->previous->next=temp2;

temp->previous=temp2;

return true;

}

temp=temp->next;

}

return false;

}

node<T>* get_head()const

{

return head->next;

}

node<T>* get_tail()const

{

return tail;

}

int get_count()const

{

return count;

}

~list()

{

node<T>* temp=head;

while(temp!=nullptr)

{

head=head->next;

delete temp;

temp=head;

}

}

};

Implementation of main:

#include <iostream>

using namespace std;

#include"list.h"

int main()

{

list <int>my_list;

my_list.insertAtEnd(7);

my_list.insertAtEnd(6);

my_list.insertAtEnd(9);

my_list.insertAtStart(10);

my_list.insertAtEnd(11);

my_list.insertAtEnd(21);

node<int>* x=my_list.find(6);

my_list.remove(x);

my_list.insertBefore(99,11);

my_list.print();

my_list.reverse();

my_list.print();

cout<<endl<<endl;

list <int>my_list1;

my_list1.insertAtEnd(7);

my_list1.insertAtEnd(10);

my_list1.insertAtEnd(25);

my_list1.insertAtEnd(65);

my_list1.insertAtEnd(91);

my_list1.insertAtEnd(125);

my_list1.print();

cout << endl << endl;

list <int>my_list2;

my_list2.insertAtEnd(6);

my_list2.insertAtEnd(36);

my_list2.insertAtEnd(85);

my_list2.insertAtEnd(100);

my_list2.insertAtEnd(115);

my_list2.insertAtEnd(218);

my_list2.print();

cout << endl << endl;

system("pause");

return 0;

}

Happy coding😊