Llist-b91/Llist.cpp

#include "Llist.h"

void Llist::append(ElementType d){
  Node *n = new Node(d);

  // in case of empty list
  if (!head) {
    head = n;
  }
  // otherwise, non empty list...
  else {
    tail->next = n;
  }
  tail = n;
  length++;
}

void Llist::prepend(ElementType d) {
  Node *n = new Node(d, head);
  
  head = n;
  // in case of empty list the tail = head = n
  if (length == 0) tail = n;

  length++;
}

void Llist::display(ostream &out) const {
  Node *p = head;
  while(p) {
    out << p->data << " ";
    p = p->next;
  }
}

void Llist::insertAfter(Node *p, ElementType d) {
  Node *n;

  // p == NULL is interpreted as prepending
  if (p == NULL) {
    n = new Node(d, head);
    head = n;
    if (!tail) tail = n;
  }
  else {
    n = new Node (d, p->next);
    p->next = n;
    if (tail == p) tail = n;
  }
  length++;
}

Node* Llist::search(ElementType d) const {
  Node *p = head;
  while(p) {
    if (p->data == d) return p;
    p = p->next;
  }
  return NULL;
}

ostream& operator<< (ostream &out, const Llist& L) {
  L.display(out);
  return out;
} 

void Llist::printRev() const {
  printRev(head); 
}

void Llist::printRev(Node *p) const {
  if (p != NULL) {
    printRev(p->next);
    cout << p->data << endl;
  } 
}

void Llist::removeAfter(Node *cur) {
  Node *suc;

  // cur == NULL is interpreted as removing the first
  // node of the list
  if (cur == NULL and head != NULL) {
    suc = head->next;
    delete head;
    head = suc;
    // in case the removed node was the only node
    if (suc == NULL) tail = NULL;
  }
  else if (cur->next != NULL) {
    suc = cur->next->next;
    delete cur->next;
    cur->next = suc;    
    // if the removed node was the last, update the tail pointer
    if (suc == NULL) tail = cur;
  }
  length--;
}

// Assignment operator:
// 1. empty the list of the invoking object
// 2. traverse the list of the parameter appending each
//    node data to the invoking object

Llist& Llist::operator=(const Llist &L) {
  if (this != &L) {
    while(head != NULL) removeAfter(NULL);
    Node *cur = L.head;
    while (cur != NULL) {
      append(cur->data);
      cur = cur->next;
    }
  }
  return *this;
}

Llist::Llist(const Llist &L) {
  head = tail = NULL;
  length = 0;
  if (this != &L) {
    Node *cur = L.head;
    while (cur != NULL) {
      append(cur->data);
      cur = cur->next;
    }
  }
}

Llist::~Llist() {
  while(head != NULL) removeAfter(NULL);
}