Linked lists

As Abstract Data Type

Operations:

• create (at the fixed size); destroy
• size, isEmpty
• iterate (forward for singly-linked list, bidirectional for double-linked lists)
• insert (by iterator) (after position, for singly-linked lists)
• remove (by iterator) (after position, for singly-linked lists)

Issues

Insert/remove for singly-linked lists

The simple implementation, where the iterator points to the node, makes it impossible to insert an element before the current position or to remove the element at the current position.

One solution is to make the iterator point to the next pointer of the previous element.

class forward_list {
    class iterator {
        Node** m_p;
        
        void operator++() {
            m_p = &((*m_p)->next);
        }
    }
    iterator begin() {
        iterator ret;
        ret.m_p = *m_first;
        return ret;
    }
    void insert(iterator it, T value) {
        Node* tmp = new Node;
        tmp->info = value;
        tmp->next = *(it.m_p);
        *(it.m_p) = tmp;
    }
    void remove(iterator it) {
        Node* tmp = *(it.m_p);
        *(it.m_p) = tmp->next;
        delete tmp;
    }
}

Another solution is to move values between nodes:

class forward_list {
    class iterator {
        Node* m_p;
        
    }
    void insert(iterator it, T value) {
        Node* tmp = new Node;
        tmp->info = it.m_p->value;
        it.m_p->value = value;
        tmp->next = it.m_p->next;
        it.m_p->next = tmp;
    }
    void remove(iterator it) {
        Node* tmp = *(it.m_p);
        *(it.m_p) = tmp->next;
        delete tmp;
    }
}