INF205/lab_3/17_and_18/doubly-linked-list.cpp

#include "doubly-linked-list.h"

using namespace seq;

// return the size (number of items in the doubly linked list)
size_t DoublyLinkedList::size() const
{
   size_t count = 0;
   for(DoublyLinkedListNode* n = this->head; n != nullptr; n = n->get_next()) count++;
   return count;
}

// add an item at the end of the list
void DoublyLinkedList::enqueue(int value)
{
   DoublyLinkedListNode* new_node = new DoublyLinkedListNode;
   new_node->set_item(value);
   
   if(this->empty()) this->head = new_node;
   else
   {
      this->tail->set_next(new_node);
      new_node->set_prev(this->tail);  /** attachment in the doubly linked list goes both ways **/
   }
   this->tail = new_node;
}

// remove the head node and item
int DoublyLinkedList::dequeue()
{
   if(this->empty()) return 0;  // nothing there to remove
   DoublyLinkedListNode* successor = this->head->get_next();

   if(successor) successor->set_prev(nullptr);  /** we must detach the previous head node from its successor **/
   int outgoing = this->head->item;
   delete this->head;
   this->head = successor;  // successor of the previous head is the new head
   if(this->head == nullptr) this->tail = nullptr;  // catch special case: the list is now empty
   return outgoing;
}