Generic Template Classes to implement a Doubly Linked List

[haglerchristopher]

For most of my programming career, I have been using Java and Objective-c. The more I learned the more I want to move to a more powerful language, so I chose c++. I have been trying to implement a linked list using template classes but I haven't been really successful. I have been reading "Data Structures and Algorithms in C++" but the examples are not really that great. This is what I have so far and when I tired to compile it, I got a tone of errors. Can you guys take a look at the code and see if you can guide me in the right direction. Thanks in Advance.

#ifndef NODE_H
#define	NODE_H

#include <cstdlib>

template <typename T>
class Node {
public:
    Node(T object);
    Node(const Node& orig);
    virtual ~Node();
    
private:
    Node<T*> _next;
    Node<T*> _prev;
    T* _object;
    
    friend class List;
};

/*
 * Implementation of the Node class
 */
Node::Node(T object) {
    _object = object;
    _next = NULL;
}

Node::Node(const Node& orig) {
}

Node::~Node() {
    delete _object;
    delete _next;
    delete _prev;
}

template <typename T> Node<T*> Node::getNext() {
    return _next;
}

template <typename T> Node<T*> Node::getPrev() {
    return _prev;
}

template <typename T> T* Node::getObject() {
    return _object;
}

#endif	/* NODE_H */ 

#ifndef LIST_H
#define	LIST_H

#include <cstdlib>
#include "Node.h"

template <typename T>
class List {
public:
    List();
    List(const List& orig);
    virtual ~List();
    void front_insert(T object);
    void tail_insert(T object);
    T* find(T* object);
private:
    Node<T*> _head;
    Node<T*> _tail;
};

//make the head and tail point to each other
List::List() {
    _head->_next= _tail;
    _head->_prev = NULL;
    _tail->_prev = _head;
    _tail->_next = NULL;
}

template <typename T> T* List::find(T object) {
    
}

template <typename T> void List::front_insert(T* object) {
    if(_head == NULL) {
       _head->_next = new Node<object>(object);
    }
    else {
        Node* temp = _head;
        while(temp->_next != NULL) {
            temp = temp->_next;
        }
        temp->_next = new Node<object>(object);
        temp->_next->_prev = temp;
    }
}

template <typename T> void List::tail_insert(T* object) {
    
}

#endif	/* LIST_H */ 

I haven't implement all of the methods yet because I was trying to deal with all of the errors before they piled up. Thanks again.

Edit: I was looking at the code and realized that some of my pointers did not make sense. I am still learning about pointers. From what I have learned so far is: an * points to location in memory and a & is the memory address. So if I have a function that takes a parameter " void getObject(Object* new_Object)" I want to call that passing in a "&" I.E getObject(&myObject).

Edit again: Sorry guys right after posting I found this http://www.cplusplus.com/forum/general/13222/

[JLBorges]

Start with something like this:

#include <cassert>

// declare List. the compiler needs to know that it is a template
template < typename T > struct List ;

// node holds a *value* - a copy of (not a pointer to) an object
template < typename T > struct Node
{
    explicit Node( const T& v, Node* next_node = nullptr, Node* prev_node = nullptr )
             : value(v), next(next_node), prev(prev_node) {}
    private:
        T value ;
        Node* next ;
        Node* prev ;

    friend class List<T> ;
};

template < typename T > struct List
{
    // default constructor - constructs an empty list
    inline List() : head(nullptr), tail(nullptr), sz(0) { assert_invariant() ; }

    inline ~List() { assert_invariant() ; while( !empty() ) pop_back() ; }

    inline int size() const { assert_invariant() ; return sz ; }
    inline bool empty() const { return size() != 0 ; }

    // insert (copy of) object at the back of the list
    void push_back( const T& object ) ;

    // remove object at the back of the list
    void pop_back() ;


    // the invariant - must be always true for a well-formed List<>
    // the first member function that we write for any non-trivial class
    bool valid() const ;
    inline void assert_invariant() const { assert( valid() ) ; }

    private:
        Node<T>* head ;
        Node<T>* tail ;
        std::size_t sz ; // number of nodes
};

template < typename T > bool List<T>::valid() const
{
    if( sz == 0 )
        return head==nullptr && tail==nullptr ;

    else if( sz == 1 )
        return head!=nullptr && tail==head && head->prev==nullptr && head->next==nullptr ;

    else
    {
        if( head!=nullptr && tail!=nullptr && head!=tail
            && head->prev==nullptr && tail->next==nullptr )
        {
            std::size_t n1 = 0 ;
            for( Node<T>* t = head ; t != nullptr ; t = t->next ) ++n1 ;

            std::size_t n2 = 0 ;
            for( Node<T>* t = tail ; t != nullptr ; t = t->prev ) ++n2 ;

            return n1==sz && n1==n2 ;
        }
        else return false ;
    }
}

template < typename T > void List<T>::push_back( const T& object )
{
    assert_invariant() ;

    if( empty() ) head = tail = new Node<T>(object) ;

    else { tail->next = new Node<T>( object, nullptr, tail ) ; tail = tail->next ; }

    ++sz ;

    assert_invariant() ;
}

template < typename T > void List<T>::pop_back()
{
    assert( !empty() ) ;
    assert_invariant() ;

    if( size() == 1 ) { delete head ; head = tail = nullptr ; }

    else { tail = tail->prev ; delete tail->next ; tail->next = nullptr ; }

    --sz ;

    assert_invariant() ;
}

Take it up from there - add the other List<> operations one by one, testing each member function for correctness before you move on to the next one.

[haglerchristopher]

are there any advantages in using structures compared to a class or is about the same. A class in c++ is basically a structure that can contain functions right? Thanks for the reply.

[Peter87]

The only difference between a struct and a class is default visibility. struct use public by default and class use private by default.

[haglerchristopher]

I analyzed the code posted by JLBorges and i completely rewrote my linked list class. I have gotten it to compile and everything works as intended, but I am not sure if I have and kind of memory leaks or any security issues. If you don't mind can you guys analyze my code and let me know what to improve and what needs to be better?

#ifndef LIST_H
#define	LIST_H

#include <iostream>

template <typename E> class List {

private:   
    template <typename T> struct ListNode {
        T value;
        ListNode<T>* next; //pointer to the next ListNode in the List
        ListNode<T>* prev; //pointer to the previous ListNode in the List
        //template constructor for the structure
        ListNode(const T &object, ListNode<T> *nextNode = NULL, ListNode<T> *prevNode = NULL) {
            value = object;
            next = nextNode;
            prev = prevNode;
        } 
    };
    
    ListNode<E>* head; //root ListNode
    ListNode<E>* tail;
    
public:
    List();
    void insert(const E &object); //insert and object into the list
    void removeNode(E object); //remove a ListNode containing "object"
    void print(); 
};

template <typename E> List<E>::List() {
    head = NULL;
    tail = NULL;
}

template <typename E> void List<E>::insert(const E &object) {
    if(head == NULL)
        head = new ListNode<E>(object);
    else {
        ListNode<E> *temp = head;
        while(temp->next != NULL) { //iterate to the end of the list
            temp = temp->next;
        }
        temp->next = new ListNode<E>(object);
        temp->next->prev = temp;
    }
    
}

//for debugging purposes only
template <typename E> void List<E>::print() {
    ListNode<E> *temp = head;
    while(temp->next != NULL) {
        std::cout << temp->value;
        temp = temp->next;
    }
}

#endif	/* LIST_H */ 

My main class is really simple and I was just using it to test out the List class

#include <cstdlib>
#include "List.h"

using namespace std;

/*
 * 
 */
int main(int argc, char** argv) {
    List<string> *list = new List<string>();
    string s = "hello";
    string b = "world";
    list->insert(s);
    list->insert(b);
    list->print();
    return 0;
}

Edit: Is it possible to implement a generic list class without using templates and only using void pointers?
would it be more efficient or is it the same behind the scenes of the template class? I was reading about a discussion that I saw when searching for examples to help out with my code.

[JLBorges]

> I am not sure if I have and kind of memory leaks

You do have serious resource leaks.

And a bug plus a performance issue in insert()

[haglerchristopher]

Can you point out a resource leak and the proper way of preventing it. Sorry guys I know this gets annoying but I'm working on getting it better

[JLBorges]

> Can you point out a resource leak

You class acquires resources - with new ListNode<E>(object) - and never releases those resources.


> the proper way of preventing it.

The class requires a destructor.


And you need to either disable copy and assignment or ensure that if a List<T> is copied or assigned to, resources are managed correctly.

[haglerchristopher]

okay guys I have an updated version of the List class. I am trying to work on the destructors, but I am having a bit of bad luck. here is the code and then I will explain.

#ifndef LIST_H
#define	LIST_H

#include <cstdlib>

template <typename E> class List {

private:
    template <typename T> struct ListNode {
        T value;
        ListNode<T>* next;
        ListNode<T>* prev;

        //template constructor for the structure
        ListNode(const T &object, ListNode<T> *nextNode = NULL,
                 ListNode<T> *prevNode = NULL) : value(object),
                 next(nextNode), prev(prevNode) { }

        //delete the data contained in the node
        ~ListNode() {
           if(prev != 0) //Not NULL
           //  delete prev; //if I leave this line in, I receive a segmentation fault.
	   if(next != 0) //Not NULL
             delete next;
        }
    };

    ListNode<E>* head; //root ListNode
    ListNode<E>* tail;

public:
    List();
    ~List();
    void insertTail(const E &object); //insert and object at end of the list
    void insertHead(const E &object); //insert and object at front of the list
    void removeNode(E &object); //remove a ListNode containing "object"
    void toString();
};

template <typename E> List<E>::List() {
    head = NULL;
    tail = NULL;
}

template <typename E> void List<E>::insertTail(const E &object) {
    if(head == NULL)
        head = new ListNode<E>(object); //Only called when the list is first initialized
    else {
        ListNode<E> *temp = head;
        while(temp->next != NULL) { //iterate to the end of the list
            temp = temp->next;
        }
        temp->next = new ListNode<E>(object);
        temp->next->prev = temp; //prev equal to the address of temp
    }
}

template <typename E> List<E>::~List() {
    ListNode<E> *current = head;
    ListNode<E> *next;

    while(current->next != NULL) {
        next = current->next; //get the address of the next node so when current
        delete current;       //is deleted we can keep iterating through the list
        current = next;
    }
    head = 0; //set head to NULL
}

#endif	/* LIST_H */ 

A couple of thing I am not sure about.
1) For the list node constructor, it takes in an address of an object const T &object, so how do I delete this in the destructor. I assign it to T value which holds the address of the object passed in correct? I should be able to call delete value. When I do this the compiler tells me it expects a pointer, so I have tried *value, &value, and still no luck.

2)In the ListNode destructor if I try to delete prev i always receive a segmentation fault. That means I am trying to access bad memory or a null pointer. I check for null and it still happens. Maybe I am overlooking something. Also if I delete next and prev does it delete the next node, so when it returns to the List destructor will next have already been deleted.

3) Do i need to have my functions take parameters such as const E &object. Is it so that the address does not get changed? Why not just have it as const E *object.

thanks guys I know it is a lot of questions, and I really appreciate the help.

EDIT: I ran my code through the Netbeans debugger and for some reason my destructor for ListNode is being call recursively. That is why I am receiving a segmentation fault when I have delete prev included. Any clues as to why this is happening?

[haglerchristopher]

Bump

[naraku9333]

Deletions should be done only in List dtor. It doesn't make sense to me to have ListNode delete anything it didn't new. Just iterate through the list in List dtor deleting nodes as you go.

[Lowest0ne]

I've been making my own linked lists as well, and have run into similar issues. I know I don't know everything, but I guess I can help.

delete ListNode; will call the deconstructor within the node's object, you can't do it explicitly because then you're trying to delete the same thing twice.

The same thing is happening with your delete previous;. You already deleted the previous node. However, when you do this, the next node's previous still points to a memory location, so it isn't NULL. I didn't give my Node a destructor at all.

Maybe that helps?

For memory leaks, I like to put my creating/inserting/destructing in a while loop so that the list quickly goes in and out of scope. Then I open task manager and look at the memory my program is using. A memory leak is very apparent.

I found this extremely helpful:
http://www.stanford.edu/class/cs107l/handouts/04-Custom-Iterators.pdf

[haglerchristopher]

Thanks a lot. The comments are really helpful and I understand why previous was causing a segmentation fault. I will reply later when I'm not on my iPhone. Thanks

EDIT: @LowestOne I really appreciate your comment and thanks for the link