Implementing Lists

CSCI 362: Data Structures

Prof. William Killian

• Lists are Circular, Doubly-Linked
  • Dummy header node

std::list<int> myList { 4, 9, 3, 2 };

#include <list>

std::list<int> l;
// some sequence of insertions
l.push_front (1);
l.push_back (99);
l

{ 1, 99 }

Node composition

template <typename T>
struct Node {
    T     data;
    Node* next;
    Node* prev;
    Node (T const& v = T(), Node* n = nullptr, Node* p = nullptr)
    : data (v), next (n), prev (p)
    { }
};

Iterators?

How can we implement an iterator?

template <typename T>
struct Iterator {
    Node<T>* nodePtr;
    
    Iterator (Node<T>* n);
    ~Iterator ();
    Iterator& operator++();
    Iterator operator++(int) const;
    Iterator& operator--();
    Iterator operator--(int) const;
    T* operator->();
    T& operator*();
    T const& operator*() const;
};

List?

template <typename T>
class List {
    Node<T> header;
    size_t  size;
public:
    List() : header (), size (0) {
        header.next = header.prev = &header;
    }
    ~List () {
        while (!empty()) pop_back();
    }
    void push_front(T const& v);
    void push_back(T const& v);
    void pop_front();
    void pop_back();
    bool empty() const;
    // insert...
    // erase...
    // iterator class from above ...
};

Pushing Values

template <typename T>
void List<T>::push_front (T const& v) {
    Node<T>* prev = &header;
    Node<T>* next = header.next;
    Node<T>* node = new Node (v, next, prev);
    prev->next = next->prev = node;
    ++size;
}

// alternatively, use insert

Board example: push_back

Insert

iterator insert (iterator i, T const& v) {
  Node<T>* next = i.nodePtr;
  Node<T>* prev = next->prev;
  Node<T>* node = new Node (v, next, prev);
  next->prev = prev->next = node;
  ++size;
  return iterator {node};
}

Erasing a Node

Assuming curr is the pointer to node we want to erase

curr->prev->next = curr->next;
curr->next->prev = curr->prev;
delete curr; // IMPORTANT!!!
--size;

Erase

iterator erase (iterator i) {
  Node<T>* curr = i.nodePtr;
  curr->prev->next = curr->next;
  curr->next->prev = curr->prev;
  delete std::exchange (curr, curr->next);
  --size;
  return iterator {curr};
}

Splice

// transfer all elements of other to "this" at pos
void splice (const_iterator pos, list& other) {
  if (other.empty())
    return;
  Node<T>* first = std::exchange (other.header.next, &(other.header));
  Node<T>* last = std::exchange (other.header.prev, &(other.header));
  size += std::exchange (other.size, 0);
  Node<T>* next = pos.nodePtr;
  Node<T>* prev = next->prev;
  next->prev = last;
  last->next = next;
  prev->next = first;
  first->prev = prev;
}

Bonus Assignment:

void
splice (const_iterator pos, list& other, const_iterator it);
// transfer single element (*it) of other to "this" at pos