Double Linked List

double_linked_list.cpp

#include <iostream>

using namespace std;

struct Node {
  int value;
  Node* next;
  Node* prev;
};

class DoubleLinkedList
{
  public:
    DoubleLinkedList();
    ~DoubleLinkedList();

    void AddNode(Node* node);
    void DelNode(Node* node);

    void PrintNodes();
    void PrintNodesFromTail();

  protected:
    Node *head;
    Node *tail;
};

DoubleLinkedList::DoubleLinkedList()
{
  this->head = new Node();
  this->tail = new Node();

  this->head->value = -1;
  this->head->next = tail;
  this->head->prev = NULL;

  this->tail->value = -1;
  this->tail->next = NULL;
  this->tail->prev = head;
}

DoubleLinkedList::~DoubleLinkedList()
{
  Node* curr = this->head->next;
  while (curr != this->tail)
  {
    Node* temp = curr->next;
    this->DelNode(curr);
    curr = temp;
  }

  // Remove the head and tail node.
  if (this->head != NULL)
    delete this->head;
  if (this->tail != NULL)
    delete this->tail;
}

void DoubleLinkedList::AddNode(Node* newNode)
{
  // Append the newly created node.
  Node* temp = this->head;
  while (temp->next != this->tail)
    temp = temp->next;

  newNode->next = temp->next;
  newNode->prev = temp;
  temp->next->prev = newNode;
  temp->next = newNode;
}

void DoubleLinkedList::DelNode(Node* node)
{
  Node *prev = this->head;
  Node *curr = prev->next;

  // Find the node to be deleted.
  while (curr != NULL && curr != node)
  {
    prev = curr;
    curr = curr->next;
  }

  // No such node in the list.
  if (curr == NULL)
  {
    cout << "No such node in the list" << endl;
    return;
  }

  Node *next = curr->next;
  prev->next = next;
  if (next != NULL)
    next->prev = prev;

  curr->next = NULL;
  curr->prev = NULL;
  delete curr;
}

void DoubleLinkedList::PrintNodes()
{
  Node* temp = this->head;
  while (temp != NULL)
  {
    cout << temp->value << endl;
    temp = temp->next;
  }
}

void DoubleLinkedList::PrintNodesFromTail()
{
  Node* temp = this->tail;
  while(temp != NULL)
  {
    cout << temp->value << endl;
    temp = temp->prev;
  }
}

int main(int argc, char* argv[])
{
  DoubleLinkedList doubleLinkedList;

  Node* newNode_1 = new Node();
  newNode_1->value = 1;
  newNode_1->next = NULL;
  newNode_1->prev = NULL;

  Node* newNode_2 = new Node();
  newNode_2->value = 2;
  newNode_2->next = NULL;
  newNode_2->prev = NULL;

  Node *newNode_3 = new Node();
  newNode_3->value = 3;
  newNode_3->next = NULL;
  newNode_3->prev = NULL;

  doubleLinkedList.AddNode(newNode_1);
  doubleLinkedList.AddNode(newNode_2);
  doubleLinkedList.AddNode(newNode_3);

  doubleLinkedList.PrintNodes();

  cout << "Print from tail to head" << endl;
  doubleLinkedList.PrintNodesFromTail();

  cout << "After removed 1" << endl;
  doubleLinkedList.DelNode(newNode_1);
  doubleLinkedList.PrintNodes();

  cout << "After removed 2" << endl;
  doubleLinkedList.DelNode(newNode_2);
  doubleLinkedList.PrintNodes();

  cout << "After removed 3" << endl;
  doubleLinkedList.DelNode(newNode_3);
  doubleLinkedList.PrintNodes();

  cout << "Delete a non-exists node in list" << endl;
  Node *newNode_4 = new Node();
  newNode_4->value = 4;
  newNode_4->prev = NULL;
  newNode_4->next = NULL;

  doubleLinkedList.DelNode(newNode_4);
  doubleLinkedList.PrintNodes();

  return 0;
}