Doubly Linked List in c++

 

A doubly linked list is a type of data structure that allows for the efficient traversal of a collection of elements in both directions. In this article, we will discuss the implementation of a doubly linked list in C++, as well as its advantages and use cases.

A doubly linked list consists of a series of nodes, each of which contains an element and pointers to the previous and next nodes in the list. The first and last nodes in the list are known as the head and tail, respectively. One of the key advantages of a doubly linked list is that it allows for easy traversal in both directions, as opposed to a singly linked list, which only allows for traversal in one direction.

To implement a doubly linked list in C++, we first need to define a class for the node. The node class should contain the following elements:

• A data element, which can be of any data type
• A pointer to the previous node in the list
• A pointer to the next node in the list

Here is an example implementation of the node class:

template <typename T>
 class Node {
 public:
        T data; 
 Node* prev;
 Node* next;
 };

Next, we need to define a class for the doubly linked list itself. The list class should contain the following elements:

• A pointer to the head of the list
• A pointer to the tail of the list
• A size variable to keep track of the number of elements in the list

Here is an example implementation of the list class:

template <typename T>
 class DoublyLinkedList {
 private:
 Node<T>* head;
 Node<T>* tail;
 int size;
 public:
 // constructor
        DoublyLinkedList() { 
 head = nullptr;
 tail = nullptr; 
 size = 0; 
 } 
 // other methods (insert, remove, etc.) 
};

Now that we have our classes defined, we can implement methods for inserting and removing elements from the list. For example, here is an implementation of the insert method:

template <typename T>
 void DoublyLinkedList<T>::insert(T data) {
 Node<T>* newNode = new Node<T>;
 newNode->data = data;
 newNode->prev = nullptr; 
 newNode->next = head;
 if (head != nullptr) {
        head->prev = newNode;
 }
    head = newNode;
 if (tail == nullptr) {
        tail = newNode;
 } 
size++; 
}

This method creates a new node with the given data and sets its next pointer to the current head of the list. It then sets the previous pointer of the current head to the new node, and updates the head pointer to the new node. If the tail pointer is null, it is also updated to the new node. The size variable is incremented to keep track of the number of elements in the list.

Similarly, here is an implementation of the remove method:

template <typename T>
 void DoublyLinkedList<T>::remove(T data) {
 Node<T>* curr = head;
 while (curr != nullptr) {
        if (curr->data