code snippets wiki / refactory.org

A wiki for useful code snippets

Bugs? Suggestions?

38-107-191-111 create/login

Template Linked List With Iterators

Your work won't be attributed to you because you aren't logged in. Login using OpenID or an existing username, or create a username (no email required) before posting.

LanguagesComma separated. Like ruby, rails or java, swing

KeywordsComma separated. Like file, network

Mark as stub

SnippetWrap code in [code=language][/code] - Use WikiText markup outside of [code] tags

+++ Description
This is a template implementation of a singly linked list that strives to be compatible with C++'s standard template library by implementing a compatible iterator class.

The class itself if implemented in a header file, below the header file will be a program designed to informally test the linked list class.

+++ LinkedListTemplate.hpp
This file implements the linked list and the iterator classes.
[code=cpp]#ifndef LINKED_LIST_TEMPLATE_CLASS_HPP
#define LINKED_LIST_TEMPLATE_CLASS_HPP
#pragma once

#include <iterator>

//This class will be referenced in the LinkedList class so it need to be declared before it can be used...
//    it uses the LinkedList class in its implementation so it can not be defined first.
template<typename T, typename T_REF, typename T_PTR> class LinkedListIterator;

//We want the LinkedList Class to work for multiple different types of objects...
//So we will create a template
template <typename T>
class LinkedList {
    //This will simplify things when we need to refer to the current class's type...
    typedef LinkedList<T> _ThisType;
    
    // First let us define the inner classes use: 
    //     LinkedListNode - protected (because the LinkedList Class and its decendants are the only classes that should use it)
    //     LinkedListIterator - public because other classes will use it to interact with the linked list.
    protected:
    //inner class... Associate an element with a pointer to the next element...
    struct LinkedListNode {
        T data;
        LinkedListNode *next;

//Constructors useful for initializing members
        explicit LinkedListNode(const T &element) : data(element), next(NULL) { } //Make sure that next defaults to NULL...
        LinkedListNode(const T &element, LinkedListNode *nxt) : data(element), next(nxt) { } //Make sure that next defaults to NULL...
        //Special function for appending a node to the current node.
        LinkedListNode& insertNext(LinkedListNode *nxt) { 
            if (nxt!=NULL) {
                LinkedListNode *temp = next;
                next = nxt;
                nxt->next = temp;
            }
            return *this;
        }
        //get the data 
        operator T() { return data; }        
    };

public:
    
    //Define the iterator class as friend (much easier than making it nested...)
    // note that these definitions illistrate why the iterator template uses three parameters.
    friend class LinkedListIterator<T, T&, T*>;
    friend class LinkedListIterator<T, const T&, const T*>; //Here we want the reference and pointers to be const, but not the data!
    
    //define some friendly names for various versions of the iterator class
    typedef LinkedListIterator<T, T&, T*> iterator;
    typedef LinkedListIterator<T, const T&, const T*> const_iterator;
    
    //Allow access to the the template type.. 
    typedef T value_type; 
    typedef unsigned int size_t;
    
    protected:
    //Each linked list has a root node pointer...
    LinkedListNode *root;
    //Keeping track of the last node will speed some operations up...
    LinkedListNode *lastNode;

//Private function to update the lastNode
    void setLastNode() { 
        if(lastNode == NULL) { lastNode = root; }
        while(lastNode->next) { lastNode = lastNode->next; }
    }
    
    public:
    //Default constructor... set root to null!
    LinkedList() : root(NULL), lastNode(NULL) { }
    
    //constructor to initialize with a given number of nodes using value_type's default constructor.
    explicit LinkedList(size_t size) : root(NULL), lastNode(NULL) {
        for(size_t i=0; i < size; ++i) {
            push_top(value_type());
        }
    }
    
    //constructor to initialize with a given number of nodes with a default value.
    //   value_type must have a copy constructor... is this constructor necessary?
    LinkedList(size_t size, value_type defValue) : root(NULL), lastNode(NULL) {
        for(size_t i=0; i < size; ++i) {
            push_top(value_type(defValue));
        }
    }
    
    //Deconstructor... We need to scroll though the list and "delete" any nodes we find.
    ~LinkedList() {
        LinkedListNode *ptr = root;
        while (ptr) {
            //********* Debugging line *************
            //std::cout << "killing: " << ptr->data << (ptr->next ? "-->next": "-->NULL") << std::endl;
            root = ptr->next;
            delete ptr;
            ptr = root;
        }
        
    }
    
    //Note that if you need a deconstructor, you generally also need a copy constructor and an assignment operator...
    // This is a copy constructor that will make a copy of a LinkedList by coping over all of the data...
    LinkedList(const LinkedList<T>& rhs) { 
        LinkedListNode *ptr = rhs.root;
        if(ptr) {
            root = new LinkedListNode(ptr->data);
            ptr = ptr->next;
            lastNode = root;
            //****** debug ****
            //std::cout <<"(copy) created: " <<root->data << (ptr->next ? "-->next": "-->NULL") << std::endl;
            while(ptr) {
                lastNode->next = new LinkedListNode(ptr->data);
                lastNode = lastNode->next; 
                //****** debug****
                //std::cout <<"(copy) created: " <<thisptr->data << (ptr->next ? "-->next": "-->NULL") <<std::endl;
                ptr = ptr->next;
            }
        }
    }
    
    //If you need a copy constructor, you also need an assignment operator...
    // This will delete the current contents of the list, and copy over the data from the other list...
    _ThisType &operator=(const LinkedList<T>& rhs) {
        //self-assignment is ignored...
        if (&rhs == this) { return *this; }
        //first of all, get rid of any data currently in the list...
        while (pop_top()) { /* do nothing */ }
        //Next construct a new list from the data in the rhs...
        LinkedListNode *ptr = rhs.root;
        if(ptr) {
            root = new LinkedListNode(ptr->data); 
            //****** debug ****
            //std::cout <<"(assign) created: " <<root->data <<std::endl;
            ptr = ptr->next;
            lastNode = root;
            while(ptr) {
                lastNode->next = new LinkedListNode(ptr->data);
                lastNode = lastNode->next; 
                //****** debug****
                //std::cout <<"(assign) created: " <<thisptr->data << (ptr->next ? "-->next": "-->NULL") <<std::endl;
                ptr = ptr->next;
            }
        }
        return *this;   
    }
    
   
    // Add elements to the top/front of the list (i.e. create a new root element)
    _ThisType &push_top(value_type element = value_type()) {
        //first check if root is null... if it is then this is where we add the element....
        if (!root) {
            root = new LinkedListNode(element);
            lastNode = root;
        } else { // else we create a new root and push everything else down the line...
            LinkedListNode *temp = root;
            root = new LinkedListNode(element, temp);
        }
        return *this;
    }

// Add elements to the bottom/back of the list (i.e. append a new node)
    // Scroll though the list looking for the place where "next" is NULL
    _ThisType &push_back(value_type element = value_type()) {
        //first check if root is null... if it is then this is where we add the element....
        if (!root) {
            root = new LinkedListNode(element);
            lastNode = root;
        } else { // else we need to look for ptr->next == null...
            lastNode->insertNext(new LinkedListNode(element));
            lastNode = lastNode->next;
        }
        return *this;
    }

bool pop_top() {
        if(root) {
            LinkedListNode* temp = root;
            root = root->next; //node is no longer part of the list...
            delete temp;
            if (root == NULL) { lastNode = NULL; }
            return true;
        }
        return false;
    }

bool pop_top(int n) {
        bool retVal = true;
        while (n-- > 0 && retVal) { retVal = pop_top(); }
        return retVal;
    }
    
    bool pop_back() {
        if(root) {
            if(root==lastNode) { 
                delete root;
                root = NULL;
                lastNode = NULL;
                return true;
            }
            LinkedListNode* ptr = root;
            while(ptr->next != lastNode) { ptr = ptr->next; } //after this loop ptr will be the second to last node
            //lastNode is the last node, ptr is the next-to-last node...
            ptr->next = NULL;
            delete lastNode;
            lastNode = ptr;
            return true;
        }
        return false;
    }

bool pop_back(int n) {
        bool retVal = true;
        while (n-- > 0 && retVal) { retVal = pop_back(); }
        return retVal;
    }

//inserts
    _ThisType& insertAfter(iterator here, const value_type &item) {
        if (here) {
            LinkedListNode* newNode = new LinkedListNode(item, here.current_node->next);
            if (here.hasParent()) {
                if (here.current_node == here.getPtrToParent()->lastNode) { here.getPtrToParent()->lastNode = newNode; }
            }
            here.current_node->next = newNode;
        } else {
            if (here.hasParent()) { here.getPtrToParent()->push_back(item); } else { push_back(item); }
        }
        return *this;
    }
    
    _ThisType& insert(iterator here, const value_type &item) {
        //std::cout << "parent: " << here.parent << " list: " << this << std::endl;
        if (!here) { 
            if (here.hasParent()) { 
                here.getPtrToParent()->push_back(item); 
            } else { 
                push_back(item); 
            }
        } else {
            if (here.getPtrToParent() == this) { //does this belong to the current list? If we 
                if (here.current_node == root) { 
                    push_top(item); 
                } else {
                    LinkedListNode* ptr = root;
                    while(ptr->next!=here.current_node) { ptr=ptr->next; } //find the node before here.current_node
                    ptr->next = new LinkedListNode(item, here.current_node); // insert the node
                    if(ptr==lastNode) { lastNode = lastNode->next; }
                }
            } else {
                if(here.hasParent()) { here.getPtrToParent()->insert(here, item); } else { push_back(item); }
            }
        }
        return *this;
    }

_ThisType &operator+=(const _ThisType &list) {
        const_iterator theEnd = list.end();
        for(const_iterator iter = list.begin(); iter != theEnd; ++iter) {
            push_back(*iter);
        }
        return *this;
    }

iterator find(const value_type &item) {
        iterator iter = begin();
        iterator theEnd = end();
        for(; iter!=theEnd; ++iter) {
            if(*iter == item) { return iter; }
        }
    }

const_iterator find(const value_type &item) const {
        const_iterator iter = begin();
        const_iterator theEnd = end();
        for(; iter!=theEnd; ++iter) {
            if(*iter == item) { return iter; }
        }
    }
    
    bool isEmpty() const { return root == NULL; }
    iterator begin()  { return iterator(root, *this); }
    iterator end()    { return NULL; }
    iterator last()   { return iterator(lastNode, *this); }
    const_iterator begin() const { return const_iterator(root, *this); }
    const_iterator end() const   { return NULL; }
    const_iterator last() const  { return const_iterator(lastNode, *this); }
};

template<typename T, typename T_REF, typename T_PTR>
class LinkedListIterator: public std::iterator<std::forward_iterator_tag, T> {
    friend class LinkedList<T>;
    typedef typename LinkedList<T>::LinkedListNode ListNode;
    typedef LinkedListIterator<T, T_REF, T_PTR> _ThisType;
    ListNode *current_node;
    LinkedList<T> *parent;
    
    public:
    typedef T value_type;       
    LinkedListIterator() : current_node(NULL), parent(NULL) { }
    LinkedListIterator(ListNode* node) : current_node(node), parent(NULL) { }
    LinkedListIterator(ListNode* node, const LinkedList<T>& parentList) : current_node(node), parent(const_cast<LinkedList<T>*>(&parentList)) { }
    LinkedListIterator(const _ThisType& iter) : current_node(iter.current_node), parent(iter.parent) { }
    
    bool operator==(const _ThisType& rhs) const {
        return current_node == rhs.current_node;
    }

bool operator!=(const _ThisType& rhs) const {
        return current_node != rhs.current_node;
    }
    
    _ThisType& operator++() {
        if(current_node!=NULL) {
            current_node = current_node->next;
        }
        return *this;
    }

_ThisType operator++(int) {
        //we want to ensure the iter++ operator returns the current value, and THEN updates...
        _ThisType temp = *this; //so we create a temp and assign the current iterator
        if(current_node!=NULL) {
            current_node = current_node->next; //increment this.
        }
        return temp; //return the copy...
    }
    
    
    T_REF operator*() const { return current_node->data; }
    T_PTR operator->() const { return &(operator*()); }
    
    bool isValid() { return current_node!=NULL; }
    bool isLast() { return (current_node!=NULL) ? current_node->next == NULL : true; }
    operator void*() { return current_node; }
    
    LinkedList<T> *getPtrToParent(){ return parent; }
    bool hasParent() { return parent!=NULL; }
    void setParent(const LinkedList<T>& parentList) { 
        if (this->parent != &parentList) {
            this->parnet = &parentList;
            current_node = parentList.begin();
        }
    }
    
};

#endif
[/code]

++++ TestCode.cpp
This file contains code used to informally test the LinkedList class and interators.
[code]#include <iostream>
#include <string>
#include "LinkedListTemplate.hpp"

template<typename T>
std::ostream& operator<<(std::ostream& out, const LinkedList<T> &list) {
    typename LinkedList<T>::const_iterator iter = list.begin();
    typename LinkedList<T>::const_iterator theEnd = list.end();
    if (iter==theEnd) { 
        out << "NULL"; 
    } else {
        while(!iter.isLast()) {
            out << *iter++ << " --> ";
        }
        out << *iter << " --> NULL.";
    }
    return out;
}

int main() {
    //Lets make sure things work with another type...
    LinkedList<int> listOfInts;
    LinkedList<int> listOfInts2;
    listOfInts.push_back(1).push_back(2).push_back(3).push_back(4);
    std::cout << "List of ints: " << listOfInts << std::endl;
    //Lets make sure the assignment operator works...
    listOfInts2 = listOfInts;
    std::cout << "Assignment: " << listOfInts2 << std::endl;
    listOfInts2.pop_back(); 
    listOfInts2.pop_top();
    std::cout << "remove First and Last: " << listOfInts2 << std::endl;
    LinkedList<int> listOfInts3;
    listOfInts3.push_top(1).push_top(2).push_top(3).push_top(4);
    std::cout << "push top: " << listOfInts3 << std::endl;
    listOfInts3.pop_top();
    std::cout << "pop top: " << listOfInts3 << std::endl;

listOfInts3.pop_back();
    std::cout << "pop back: " << listOfInts3 << std::endl;
    listOfInts3.insertAfter(listOfInts3.begin(), 8);
    std::cout << "insertAfter begin(): " << listOfInts3 << std::endl;
    listOfInts3.insertAfter(listOfInts3.end(), 10);
    std::cout << "insertAfter end(): " << listOfInts3 << std::endl;

listOfInts3.insert(listOfInts3.begin(), 5);
    std::cout << "insert begin(): " << listOfInts3 << std::endl;
    listOfInts3.insert(++listOfInts3.begin(), 6);
    std::cout << "insert ++begin(): " << listOfInts3 << std::endl;

listOfInts3 += listOfInts2;
    std::cout << "insert ++begin(): " << listOfInts3 << std::endl;

return 0;
}
[/code]

Log message

Human?

public snippets

This is a community-maintained collection of reusable code snippets. Contribute something without logging in, or improve existing contributions. All code is dedicated to the public domain unless otherwise specified.

All user-contributed content is dedicated to the public domain unless otherwise specified.

Refactory.org, its owners and contributers shall not be held liable for any damages resulting from your usage of any content herein. Your usage of this website constitutes agreement to these terms.

Created by Aaron Hall - email / twitter