Question

!Must be written in C++!

Build a doubly linked list with these operations:
AddToHead(10); AddToHead(20); AddToTail(30); AddToTail(40);
Build a sorted doubly linked list with these operations:
Add(30), Add(20), Add(40), Add(15), Add(35);

Answer 1

Code

#include<iostream>
using namespace std;

// Node structure
struct Node {
  int data;
  Node *next, *prev;
  Node(int _data, Node *_next = NULL, Node *_prev = NULL) {
    data = _data;
    next = _next;
    prev = _prev;
  }
};

// Doubly linked list with head and tail
class DoublyLinkedList {
  Node *head, *tail;
  public:
    DoublyLinkedList() {
      head = tail = NULL;
    }
    void print() {
      cout << "\nList: [ ";
      Node *p = head;
      while (p != NULL) {
        cout << p -> data << " ";
        p = p -> next;
      }
      cout << "]\n";
    }
    // Add new node at head
    void AddToHead(int data) {
      Node *newNode = new Node(data);
      if (head == NULL) {
        // If the list is empty
        head = tail = newNode;
      } else {
        // Else, insert before head
        newNode -> next = head;
        head -> prev = newNode;
        head = newNode;
      }
    }
    // Add new node at tail
    void AddToTail(int data) {
      Node *newNode = new Node(data);
      if (head == NULL) {
        // If the list is empty
        head = tail = newNode;
      } else {
        // Else, insert after tail
        newNode -> prev = tail;
        tail -> next = newNode;
        tail = newNode;
      }
    }
    // Add new node in its sorted position (ascending order)
    void Add(int data) {
      Node *newNode = new Node(data);
      if (head == NULL) {
        // If the list is empty
        head = tail = newNode;
      } else if (head -> data >= data) {
        // If data is less than (or equal to) head's data, insert at head.
        AddToHead(data);
      } else if (tail -> data <= data) {
        // If data is more than (or equal to) tail's data, insert at tail
        AddToTail(data);
      } else {
        // Else, we have the case where new data needs to be inserted
        // somewhere in the list and not corners (head or tail).
        // We find the first node whose data is more than the new node's data
        // and insert new node just before that node.
        Node *p = head;
        while (p -> data < data) {
          p = p -> next;
        }
        // Insert new node before p
        newNode -> next = p;
        newNode -> prev = p -> prev;
        p -> prev -> next = newNode;
        p -> prev = newNode;
      }
    }
};

int main() {
  DoublyLinkedList simple, sorted;
  simple.AddToHead(10);
  simple.AddToHead(20);
  simple.AddToTail(30);
  simple.AddToTail(40);
  simple.print();
  sorted.Add(30);
  sorted.Add(20);
  sorted.Add(40);
  sorted.Add(15);
  sorted.Add(35);
  sorted.print();
  return 0;
}

Output