Sign in to follow this  
Followers 0
jaberwacky

Critique my LinkedList Class

27 posts in this topic

#1 ·  Posted (edited)

Yes, I'm a masochist.

I finally got around to doing something I've wanted to do for a long time now. I finally just focused my attention and 'got 'r' done!' Simple to you they may be but the concept behind linked lists has eluded me for a long time. I'd like to know what could have been done better or just any advice you could give me. Ultimately I'm just proud of my self because I stopped putting this off for so long.

OK, plans:

1) Improve the exception handling .

2) Implement iterators.

3) Improve operator overloading.

4) More methods such as: push_front, insert, erase, etc.

Main.cpp

#include <iostream>
#include "Linked List.h"

using namespace std;

template <typename T> void display_list ( LinkedList<T>& );

void display_list_size ( unsigned int );

int main()
{
    const int Length = 10;

    LinkedList<int> MyList;

    cout << "Initialize list:\n";

    for ( int i = 1; i <= Length; i++ )
    {
        /// MyList.push_back ( i )
        MyList = i;

        cout << "push_back: " << MyList.at ( i - 1 ) << '\n';
    }

    display_list_size ( MyList.size() );

    display_list ( MyList );

    cout << "\npop_back:" << endl;
    MyList.pop_back();

    display_list_size ( MyList.size() );

    display_list ( MyList );

    cout << "\nClear: " << endl;
    MyList.clear();

    display_list_size ( MyList.size() );

    cin.get();

    return 0;
}

/// ---------------------------------------------------------------------------

template <typename T> void display_list ( LinkedList<T> &MyList )
{
    const unsigned int Size = MyList.size();

    cout << "\nDisplay list:\n";

    for ( unsigned int i = 1; i <= Size; i++ )
    {
        cout << "MyList.at(" << i - 1 << "): " << MyList.at ( i - 1 ) << '\n';
    }
}

/// ---------------------------------------------------------------------------

void display_list_size ( unsigned int Size )
{
    cout << "\nSize: " << Size << '\n';
}

/// ---------------------------------------------------------------------------

Node.h

#ifndef Node_h
#define Node_h

using namespace std;

template <class T> class Node
{
    public:
        Node ( const T &Data ) : Cargo ( Data ), Next ( NULL ), Prev ( NULL ) {};
        Node ( T &Data ) : Cargo ( Data ), Next ( NULL ), Prev ( NULL ) {};
        ~Node();

        Node<T> operator ++ ();
        Node<T> &operator == ( const Node<T> &rhs ) const;

        T Cargo;
        Node<T> *Next;
        Node<T> *Prev;
} ;

/// ---------------------------------------------------------------------------

template <class T> Node<T>::~Node()
{
    Cargo = NULL;
    Next = NULL;
    Prev = NULL;
}

/// ---------------------------------------------------------------------------

template <class T> Node<T> Node<T>::operator ++ ()
{
    cout << "Paging Dr.++\n";

    return ( *this );
}

/// ---------------------------------------------------------------------------

template <class T> Node<T> &Node<T>::operator == ( const Node<T> &rhs ) const
{
    cout << "Paging Dr.==\n";

    if ( this.Cargo == rhs.Cargo )
    {
        cout << "Equal\n";
    }

    return ( *this );
}

/// ---------------------------------------------------------------------------

#endif

LinkedList.h

#include <stdexcept>
#include <exception>
#include "Node.h"

using namespace std;

template <class T> class LinkedList
{
    public:
        LinkedList();
        ~LinkedList();

        Node<T> * Back;
        Node<T> * Front;
        unsigned int Length;

        LinkedList<T> &operator = ( const Node<T> & );
        LinkedList<T> &operator == ( const Node<T> & );

        T at ( const unsigned int );
        Node<T> begin();
        void clear();
        Node<T> end();
        bool isempty();
        void pop_back();
        void pop_front();
        void push_back ( const T );
        unsigned int size();
} ;

/// ---------------------------------------------------------------------------

template <class T> LinkedList<T>::LinkedList()
    : Back ( NULL ), Front ( NULL ), Length ( 0 )
{}

/// ---------------------------------------------------------------------------

template <class T> LinkedList<T>::~LinkedList()
{
    clear();
}

/// ---------------------------------------------------------------------------

template <class T> LinkedList<T> &LinkedList<T>::operator = ( const Node<T> &rhs )
{
    try
    {
        push_back ( rhs.Cargo );
    }
    catch ( ... )
    {
        cerr << "Exception unknown.\n";
    }

    return ( *this );
}

/// ---------------------------------------------------------------------------

template <class T> LinkedList<T> &LinkedList<T>::operator == ( const Node<T> &rhs )
{
    cout << "Paging Dr.==\n";

    return ( *this );
}

/// ---------------------------------------------------------------------------

template <class T> T LinkedList<T>::at ( const unsigned int Index )
{
    T Cargo = 0;

    try
    {
        if ( isempty() ) throw 1;

        if ( Index > Length ) throw 2;

        Node<T> * MyNode = Front;

        for ( unsigned int i = 1; ( i <= Index ) && ( MyNode != NULL ); i++ )
        {
            MyNode = MyNode->Next;
        }

        Cargo = MyNode->Cargo;

        MyNode = NULL;
    }
    catch ( int e )
    {
        switch ( e )
        {
            case 1:
                cerr << "\nIndex is out of bounds.\n";
                break;

            case 2:
                cerr << "\nList is Empty.\n";
                break;
        }
    }

    return Cargo;
}

/// ---------------------------------------------------------------------------

template <class T> Node<T> LinkedList<T>::begin()
{
    return Front;
}

/// ---------------------------------------------------------------------------

template <class T> void LinkedList<T>::clear()
{
    while ( !isempty() )
    {
        pop_back();
    }
}

/// ---------------------------------------------------------------------------

template <class T> Node<T> LinkedList<T>::end()
{
    return Back;
}

/// ---------------------------------------------------------------------------

template <class T> bool LinkedList<T>::isempty()
{
    if ( Back == NULL )
    {
        return true;
    }
    else
    {
        return false;
    }
}

/// ---------------------------------------------------------------------------

template <class T> void LinkedList<T>::pop_back()
{
    if ( !isempty() )
    {
        if ( Length != 1 )
        {
            Node<T> *TailNode = Back->Prev;
            TailNode->Next = NULL;
            delete Back;
            Back = TailNode;
        }
        else
        {
            Back = NULL;
            Front = NULL;
        }

        --Length;
    }
}

/// ---------------------------------------------------------------------------

template <class T> void LinkedList<T>::pop_front()
{
    if ( !isempty() )
    {
        if ( Length != 1 )
        {
            Node<T> * NextNode = Front->Next;
            delete Front;
            Front = NextNode;
        }
        else
        {
            Back = NULL;
            Front = NULL;
        }

        --Length;
    }
}

/// ---------------------------------------------------------------------------

template <class T> void LinkedList<T>::push_back ( const T Data )
{
    try
    {
        Node<T> * NewNode = new Node<T> ( Data );

        if ( isempty() )
        {
            Front = NewNode;
            Back = NewNode;
        }
        else
        {
            Back->Next = NewNode;
            NewNode->Prev = Back;
            Back = NewNode;
        }

        ++Length;

        NewNode = NULL;
    }
    catch ( bad_alloc &e )
    {
        cerr << "Error: Out of memory. =(\n";
    }
}

/// ---------------------------------------------------------------------------

template <class T> unsigned int LinkedList<T>::size()
{
    return Length;
}

/// ---------------------------------------------------------------------------
}
Edited by jaberwocky6669

Share this post


Link to post
Share on other sites



#2 ·  Posted (edited)

I'd have done it with templates. Then the "cargo" could be defined as whatever you wanted.

You also don't have an insert function.

Edited by Richard Robertson

Share this post


Link to post
Share on other sites

#4 ·  Posted (edited)

Templates are very useful when used correctly. They are worth knowing.

Also, don't blindly assume that the index provided to a function is between 0 and length. Add an explicit check.

Edited by Richard Robertson

Share this post


Link to post
Share on other sites

I would add functions like empty (clear the list) and isEmpty(). Otherwise good effort.

Also have a looke that the Vector class in the STL for standard function names. You should be able to get the source then see how the templates where used.


Post your code because code says more then your words can. SciTe Debug mode - it's magic: #AutoIt3Wrapper_run_debug_mode=Y. Use Opt("MustDeclareVars", 1)[topic="84960"]Brett F's Learning To Script with AutoIt V3[/topic][topic="21048"]Valuater's AutoIt 1-2-3, Class... is now in Session[/topic]Contribution: [topic="87994"]Get SVN Rev Number[/topic], [topic="93527"]Control Handle under mouse[/topic], [topic="91966"]A Presentation using AutoIt[/topic], [topic="112756"]Log ConsoleWrite output in Scite[/topic]

Share this post


Link to post
Share on other sites

#8 ·  Posted (edited)

I see these just quickly glancing over the code.

  • Not const-correct.
  • Does not provide a standard API (push_back(), push_front(), insert() methods among others).
  • Does not have a destructor so memory is leaked or explicitly node destruction must be performed (don't make the user do what a destructor should do).
  • Not a template. Templates are easy, there's no reason not to learn how to write them.
  • Remove() does not set Head->Prev to NULL when Index == 0 (will crash the program).
  • Remove() does not update Tail if the Tail element is deleted (will crash the program).
  • At() returns a valid value on failure. It should throw an exception or signal an error in some other fashion.
  • The return value from Remove() makes no sense. Maybe it should be a bool instead? Or just return the size, I can't recall off the top of my head what is common in this case.
Edited by Valik
Typos.

Share this post


Link to post
Share on other sites

Specifically, your change to At is still no good. You will still make invalid reads for bad indices.

Share this post


Link to post
Share on other sites

#11 ·  Posted (edited)

OK, the main changes I've made are trying to make it const correct and I changed Node from a struct to an object. More to come.

Hah, I just realized that in my destructor when I evaluate Size in my for loop Size will be decremjented by my Remove() method! So it only deletes half of the list! OK, I fixed that.

Edited by jaberwocky6669

Share this post


Link to post
Share on other sites

#12 ·  Posted (edited)

Ok, my compiler (MinGW) goes nuts when I add the template stuff!

Class LinkedList has two members of type Node. This runs fine until I add the template stuff. After that then it says: "error: ISO C++ forbids declaration of 'Node' with no type". Any clues? I tried making class LinkedList a friend of class Node. No joy.

I have to admit that this template stuff has made me into a feces flinging code monkey.

Edited by jaberwocky6669

Share this post


Link to post
Share on other sites

#13 ·  Posted (edited)

AHA! I got it!!!!!!!!!!!!!!

Okies, so I hope it's const correct now and I hope that templates were implemented correctly. If so then I'm off to implement the rest of everybody's suggestions.

Edited by jaberwocky6669

Share this post


Link to post
Share on other sites

Your constructor should take const parameters too.

Share this post


Link to post
Share on other sites

#16 ·  Posted (edited)

Node. Obviously because it's the only one that even takes a parameter.

Also, you can't go returning values for failure. If T = std::string and you return -1, you have a compile time error. You'll need to use a signal or structured exception.

Edited by Richard Robertson

Share this post


Link to post
Share on other sites

#17 ·  Posted (edited)

You will have to find an example somewhere however I the last time created a linked list in C++ I made Node a friendly inner class of LinkList. Personal choice I guess ...

Edited by bo8ster

Post your code because code says more then your words can. SciTe Debug mode - it's magic: #AutoIt3Wrapper_run_debug_mode=Y. Use Opt("MustDeclareVars", 1)[topic="84960"]Brett F's Learning To Script with AutoIt V3[/topic][topic="21048"]Valuater's AutoIt 1-2-3, Class... is now in Session[/topic]Contribution: [topic="87994"]Get SVN Rev Number[/topic], [topic="93527"]Control Handle under mouse[/topic], [topic="91966"]A Presentation using AutoIt[/topic], [topic="112756"]Log ConsoleWrite output in Scite[/topic]

Share this post


Link to post
Share on other sites

I'm about to wrap up for the night. What I have planned for tommorrow is to read up on exceptions and a crap load of other things like iterators. I really appreciate everybody's insights! Keep 'em coming.

Share this post


Link to post
Share on other sites

Ok, Node constructor takes a const param. Also, I tried to implement exceptions to the best of my current understanding. This concludes another productive learning day. I bid you peace.

Share this post


Link to post
Share on other sites

#20 ·  Posted (edited)

In my push_back method the compiler says that this line will never be executed: "Node<T> * const NewNode = new Node<T> ( Data );". Why should this be? And it seems as though it is executed. The compiler also gives me the same warning everywhere I have a throw statement.

Edited by jaberwocky6669

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0