C++: Doubly Linked List using Template (Data Structure)

A doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. It consists of an attribute key and two other pointer attributes: next and prev.The two node links allow traversal of the list in either direction. While adding or removing a node in a doubly linked list requires changing more links than the same operations on a singly linked list, the operations are simpler and potentially more efficient (for nodes other than first nodes) because there is no need to keep track of the previous node during traversal or no need to traverse the list to find the previous node, so that its link can be modified. I would recommend you to read C++: Singly Linked List using Template (Data Structure) Because some of the methods used in the program are explained in this post.



Source: Wikipedia


#include <iostream>
template<class T>class DoublyLinkedList{  struct Node{  T data;  Node* next;  Node* prev;  Node(T val):data(val),next(nullptr),prev(nullptr){}  };  Node *head ,*tail;
  public:      DoublyLinkedList():head(nullptr),tail(nullptr){}
     ~DoublyLinkedList(){        Node *tmp = nullptr;          while (head){             tmp = head;             head = head->next;             delete tmp;          }          head =nullptr;        }
      DoublyLinkedList(const DoublyLinkedList<T> & dll) = delete;      DoublyLinkedList& operator=(DoublyLinkedList const&) = delete;      void insertFront(T val){         Node *node = new Node(val);          Node *tmp = head;          if (head == nullptr){              head = node;              tail=node;              }         else{            node->next=head;            head=node;            node->next->prev = node;             while (tmp->next != nullptr){               tmp = tmp->next;             }          tail=tmp;        }    }
      void insertBack(T val){         Node *node=new Node(val);           if(tail->next==nullptr){            tail->next=node;            tail=node;            }     }

     void deleteVal(T val){      Node* find = findVal(val);      Node *tmp = head;        if(tmp==find){          head=tmp->next;        }        else{           while(find != nullptr){              if(tmp->next==find){              tmp->next = find->next;              find->next->prev = tmp;              delete find;              return;              }            tmp=tmp->next;          }       }
    }
     template <class U>     friend std::ostream & operator<<(std::ostream & os, const DoublyLinkedList<U> & dll){      dll.display(os);      return os;     }
     private:
         Node *findVal(T n){    //returns node of the given number         Node *node = head;         while(node!=nullptr){            if(node->data==n)                 return node;         node=node->next;         }         std::cerr<<"No such element in the list \n";         return nullptr;       }
       void display(std::ostream& out = std::cout) const{        Node *node = head;        while(node!=nullptr){        out <<node->data << " ";        node=node->next;        }      }};int main(){  DoublyLinkedList<int> l1;  l1.insertFront(3);  l1.insertBack(5);  l1.insertBack(12);  l1.insertFront(6);  l1.insertBack(88);  std::cout<<l1<<"\n";  l1.deleteVal(12);   std::cout<<l1<<"\n";  return 0;}

Output:

If you don't know Templates then you should read this  C++: Understanding Template

 Follow us on
                              

                                                                  
                                                                  

Reference:



You may also like:
C++: Swapping Node LInks in Linked List
C++: Queue implementation using Linked List (Data Structure)
C++: Implementation of Queue using Array (Data Structure)
How do I learn data structures and algorithms from scratch?
C++: Insertion Sort using STL (Sorting)


Comments

Popular Posts

Top 10 Web Sites Every Programmer Should Visit Daily

C++: Huffman Coding using STL