Featured Post

Trie implementation in C

Doubly Linked List in C++

Here's a simple implementation of doubly linked list using C++

//dll.hpp
class dnode
{
public:
    dnode();
    dnode *prev;
    int data;
    dnode *next;
    ~dnode();
};

class DLL
{
private:
    dnode *front;
    dnode *rear;
    dnode *newnode;
public:
    DLL();
    dnode* create_node(int data);
    void insertAtFront(int data);
    void insertAtRear(int data);
    void insertBefore(int data, dnode *node);
    void insertAfter(int data, dnode *node);
    void deleteFront();
    void deleteLast();
    void del(int data);
    dnode* search(int data);
    void display();
    ~DLL();
};



//dll.cpp
#include <iostream>
#include "dll.hpp"

using namespace std;

dnode::dnode()
{
    cout<<"dnode()"<<endl;
}

dnode::~dnode()
{
    cout<<"~dnode()"<<endl;
}

DLL::DLL()
{
    front = NULL;
    rear = NULL;
    cout<<"DLL()"<<endl;
}

dnode* DLL :: create_node(int data)
{
    newnode = new dnode;
    newnode->data = data;
    newnode->prev = NULL;
    newnode->next = NULL;
    return newnode;
}

void DLL::insertAtFront(int data)
{
    dnode* newnode = create_node(data);

    if(front == NULL)
    {
        front = newnode;
        rear = newnode;
    }
    else
    {
        newnode -> next = front;
        front -> prev = newnode;
        front = newnode;
    }
}

void DLL::insertAtRear(int data)
{
    dnode *prev,*ptr;
    dnode* newnode = create_node(data);

    if(front == NULL)
    {
        front = newnode;
        rear = newnode;
    }
    else
    {
        for(prev = front, ptr = front -> next ; ptr ; prev = ptr, ptr = ptr -> next);

        if(ptr == NULL)
        {
            prev -> next = newnode;
            newnode -> prev = prev;
            rear = newnode;
        }
    }
}

void DLL::insertBefore(int data, dnode *node)
{
    dnode *prev,*ptr;
    dnode* newnode = create_node(data);

    if(front == NULL)
    {
        front = newnode;
        rear = newnode;
    }
    else
    {
        node->prev->next = newnode;
        newnode -> prev = node -> prev;
        newnode -> next = node;
    }
}

void DLL::insertAfter(int data, dnode* node)
{
    dnode *prev,*ptr;
    dnode* newnode = create_node(data);

    if(front == NULL)
    {
        front = newnode;
        rear = newnode;
    }
    else
    {
        newnode -> next = node -> next;
        node->next = newnode;
        newnode -> prev = node;
    }

}

void DLL::deleteFront()
{
    dnode *temp;
    
    temp = front;
    front = front -> next;
    front -> prev = NULL;

    delete temp;
}

void DLL::deleteLast()
{
    dnode *temp;
    
    temp = rear;
    rear -> prev -> next = NULL;
    rear = rear -> prev;
    delete temp;
}

void DLL::del(int data)
{
  if(front == NULL)
  {
    cout<<"List is empty"<<endl;
    return;
  }

  dnode *searchNode;

  if((searchNode = search(data)) != NULL)
  {
    cout<<"SNData :"<<rear->data<<endl; 
    if(front == searchNode)
    {
      cout<<"front"<<endl;
      deleteFront();
    }
    else if(rear == searchNode)
    {
      cout<<"last"<<endl;
      deleteLast();
    }
    else
    {
      dnode *temp;
      temp = searchNode;

      searchNode -> prev -> next = searchNode -> next;
      searchNode -> next -> prev = searchNode -> prev;

      delete temp;
    }
  }
}

dnode* DLL::search(int data)
{
  dnode *prev,*ptr;
  for(ptr = front ; ptr ; ptr = ptr -> next)
  {
    if(ptr -> data == data)
      return ptr;
  }
    
  return NULL;
}


void DLL::display()
{
    dnode *ptr;

    if(front == NULL)
    {
        cout<<"List is empty"<<endl;
        return;
    }

    for(ptr = front ; ptr ; ptr = ptr ->next)
        cout<<"->"<<ptr->data;

    cout<<endl;
}

DLL::~DLL()
{
    while(front)
    {
        dnode* temp = front;
        front  = front ->next;
        delete temp;
    }
    cout<<"~DLL()"<<endl;
}

int main()
{
    DLL d1;

    d1.insertAtFront(4);
    d1.insertAtFront(2);
    d1.insertAtFront(23);
    d1.insertAtRear(12);
    d1.insertAtRear(27);
    d1.insertAtRear(42);
    d1.display();
    d1.deleteFront();
    d1.display();
    d1.deleteLast();
    d1.display();
    d1.del(27);
    d1.display();
}

Comments