HiveBrain v1.2.0
Get Started
← Back to all entries
patterncppMinor

Linked list implemented as classes, not imperative code

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
implementedimperativeclassescodelistlinkednot

Problem

As an update to previous code I've submitted:

Improvements this time are mainly having everything moved to a class, before I plough on and add more functionality (I've come back to C++ after a few years away and this is a revision exercise).

#include 
#include "LinkedList.h"

class LinkedList
{
public:
    LinkedList(void);
    ~LinkedList(void);
    void traverseList();
    int length();
    void push(int data);

private:
    struct node{
    int data;
    node *pointee;
    };

    node *head;
    node *last;
    int count;
};

LinkedList::LinkedList(void)
{
        head = new node();
    last = new node();
    head->data = 0;
    head->pointee = last;
    last->data = 0;
    last->data = NULL;
    count = 2;
}

LinkedList::~LinkedList(void)
{
}

/*
    To be replaced with an iterator and an overloaded print operator for output
*/
void LinkedList::traverseList(){
    for(node *iterator = LinkedList::head ; iterator ; iterator = iterator->pointee)
    {
        std::cout data data = data;
    newNode->pointee = NULL;
    last = newNode;
    ++count;
}

int main(){

    LinkedList list;

    for(int i=1 ; i<4 ; i++)
    {
        list.push(i);
    }

    int length = list.length();
    std::cout << length << std::endl;
    list.traverseList();
    return 0;
}

Solution

Since we have no clean implementations:

The thing to notice is that the push_back() and erase() become trivial if you use a sentinal. This is because you do not need to test for NULL in any part of the code.

Node(Node* after)
    {
        prev          = after;
        next          = after->next;
        prev->next    = this;
        next->prev    = this;
    }
    ~Node()
    {
        prev->next  = next;
        next->prev  = prev;
    }

    iterator push_back(T const& value)
    {
        tail    = new ValueNode(value, tail);

        // If new succeeded then increment count
        ++count;
        return iterator(tail);
    }

    void erase(iterator const& i)
    {
        // Get the value we will set as tail if the delete works
        Node*   newTail = (tail == i.node)
                            ? i.node->prev
                            : tail;
        delete i.node;
        // Delete worked now we can update the state.
        tail    = newTail;
        --count;
    }


Here is the whole code

#ifndef THORS_ANVIL_UTILITY_LINKED_LIST
#define THORS_ANVIL_UTILITY_LINKED_LIST

#include 
#include 

template
class LinkedList
{
    struct Node
    {
        Node*   prev;
        Node*   next;
        Node(Node* after)
        {
            prev          = after;
            next          = after->next;
            prev->next    = this;
            next->prev    = this;
        }
        ~Node()
        {
            prev->next  = next;
            next->prev  = prev;
        }
        void swap(Node& rhs) throw()  { std::swap(prev, rhs.prev); std::swap(next, rhs.next);}
    };
    struct ValueNode: Node
    {
        ValueNode(T const& value, Node* after)
            : Node(after)
            , data(value)
        {}
        T       data;
    };

    Node    head;
    Node*   tail;
    int     count;

    public:
        struct Iterator: std::iterator
        {
            Iterator(Node* node): node(node){}

            T&       operator*()        {return  static_cast(node)->data;}
            T*       operator->()       {return &static_cast(node)->data;}
            T const& operator*()  const {return  static_cast(node)->data;}
            T const* operator->() const {return &static_cast(node)->data;}

            Iterator& operator++()     /*prefix*/  { node = node->next; return *this;}
            Iterator& operator--()     /*prefix*/  { node = node->prev; return *this;}
            Iterator  operator++(int)  /*postfix*/ { Iterator result(*this);this->operator++(); return result;}
            Iterator  operator--(int)  /*postfix*/ { Iterator result(*this);this->operator--(); return result;}

            bool operator !=(Iterator const& rhs) const    { return node != rhs.node;}
            bool operator ==(Iterator const& rhs) const    { return !(*this != node);}

            mutable Node*   node;
        };

        LinkedList()
            : tail(&head)
            , count(0)
        {}

        ~LinkedList()
        {
            clear();
        }

        void clear()
        {
            while(head.next != &head)
            {
                Node*   old = head.next;
                head.next   = head.next->next;
                --count;
                delete old;
            }
        }

        LinkedList(LinkedList const& copy)
            : tail(&head)
            , count(0)
        {
            std::for_each(copy.head->next, copy.head, std::bind1st(std::mem_fun(&LinkedList::push_back), this));
        }
        LinkedList& operator=(LinkedList rhs)
        {
            rhs.swap(*this);
            return *this;
        }
        void swap(LinkedList& rhs) throw()
        {
            std::swap(head,     rhs.head);
            std::swap(tail,     rhs.tail);
            std::swap(count,    rhs.count);
        }

        bool    isEmpty()   const { return &head == tail; }
        size_t  size()      const { return count; }

        typedef Iterator           iterator;
        typedef Iterator const     const_iterator;

        iterator push_back(T const& value)
        {
            tail    = new ValueNode(value, tail);
            ++count;
            return iterator(tail);
        }

        void erase(iterator const& i)
        {
            Node*   newTail = (tail == i.node)
                                ? i.node->prev
                                : tail;
            tail    = newTail;
            --count;
            delete i.node;
        }

        iterator begin()                {return iterator(head.next);}
        const_iterator begin() const    {return iterator(head.next);}
        iterator end()                  {return iterator(&head);}
        const_iterator end() const      {return iterator(&head);}
};
#endif


Then Main

```
#include
#include

int main()
{
LinkedList list;
list.push_back(5);
LinkedList::iterator item = list.push_back(7);
for(LinkedList::iterator loop = list.begin(); loop != list.end(); ++loop)
{
std::co

Code Snippets

Node(Node* after)
    {
        prev          = after;
        next          = after->next;
        prev->next    = this;
        next->prev    = this;
    }
    ~Node()
    {
        prev->next  = next;
        next->prev  = prev;
    }

    iterator push_back(T const& value)
    {
        tail    = new ValueNode(value, tail);

        // If new succeeded then increment count
        ++count;
        return iterator(tail);
    }

    void erase(iterator const& i)
    {
        // Get the value we will set as tail if the delete works
        Node*   newTail = (tail == i.node)
                            ? i.node->prev
                            : tail;
        delete i.node;
        // Delete worked now we can update the state.
        tail    = newTail;
        --count;
    }
#ifndef THORS_ANVIL_UTILITY_LINKED_LIST
#define THORS_ANVIL_UTILITY_LINKED_LIST

#include <algorithm>
#include <functional>

template<typename T>
class LinkedList
{
    struct Node
    {
        Node*   prev;
        Node*   next;
        Node(Node* after)
        {
            prev          = after;
            next          = after->next;
            prev->next    = this;
            next->prev    = this;
        }
        ~Node()
        {
            prev->next  = next;
            next->prev  = prev;
        }
        void swap(Node& rhs) throw()  { std::swap(prev, rhs.prev); std::swap(next, rhs.next);}
    };
    struct ValueNode: Node
    {
        ValueNode(T const& value, Node* after)
            : Node(after)
            , data(value)
        {}
        T       data;
    };

    Node    head;
    Node*   tail;
    int     count;

    public:
        struct Iterator: std::iterator<std::input_iterator_tag, T, ptrdiff_t, const T*, const T&>
        {
            Iterator(Node* node): node(node){}

            T&       operator*()        {return  static_cast<ValueNode*>(node)->data;}
            T*       operator->()       {return &static_cast<ValueNode*>(node)->data;}
            T const& operator*()  const {return  static_cast<ValueNode*>(node)->data;}
            T const* operator->() const {return &static_cast<ValueNode*>(node)->data;}

            Iterator& operator++()     /*prefix*/  { node = node->next; return *this;}
            Iterator& operator--()     /*prefix*/  { node = node->prev; return *this;}
            Iterator  operator++(int)  /*postfix*/ { Iterator result(*this);this->operator++(); return result;}
            Iterator  operator--(int)  /*postfix*/ { Iterator result(*this);this->operator--(); return result;}

            bool operator !=(Iterator const& rhs) const    { return node != rhs.node;}
            bool operator ==(Iterator const& rhs) const    { return !(*this != node);}

            mutable Node*   node;
        };

        LinkedList()
            : tail(&head)
            , count(0)
        {}

        ~LinkedList()
        {
            clear();
        }

        void clear()
        {
            while(head.next != &head)
            {
                Node*   old = head.next;
                head.next   = head.next->next;
                --count;
                delete old;
            }
        }

        LinkedList(LinkedList const& copy)
            : tail(&head)
            , count(0)
        {
            std::for_each(copy.head->next, copy.head, std::bind1st(std::mem_fun(&LinkedList::push_back), this));
        }
        LinkedList& operator=(LinkedList rhs)
        {
            rhs.swap(*this);
            return *this;
        }
        void swap(LinkedList& rhs) throw()
        {
            std::swap(head,     rhs.head);
            std::swap(tail,     rhs.tail);
            std::swap(count,    rhs.count);
        }

        bool    isEmpty()   const { return &head == tail; }
        size_t  
#include <LinkedList.h>
#include <iostream>

int main()
{
    LinkedList<int> list;
    list.push_back(5);
    LinkedList<int>::iterator item = list.push_back(7);
    for(LinkedList<int>::iterator loop = list.begin(); loop != list.end(); ++loop)
    {
        std::cout << *loop << "\n";
    }
    list.erase(item);
    for(LinkedList<int>::iterator loop = list.begin(); loop != list.end(); ++loop)
    {
        std::cout << *loop << "\n";
    }
}
after                                        
      #########                         #########   
   -->#  Next #------------------------>#  Next #----
      #       #                         #       #
   ---#Prev   #<------------------------#Prev   #<---
      #########                         #########    

                       NewNode(this)
                       #########
                       #   Next#
                       #Prev   #
                       #########
after
      #########                         #########   
   -->#  Next #------------------------>#  Next #----
      #       #                         #       #
   ---#Prev   #<------------------------#Prev   #<---
      #########   |                     #########    
                  |
                  |    (this)
                  |    #########
                  |    #   Next#
                  -----#Prev   #
                       #########

Context

StackExchange Code Review Q#9230, answer score: 7

Revisions (0)

No revisions yet.