Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I feel like there is room for improvement in the push/pop methods. Any suggestions?

#include <exception>

template <typename T>
class List
{
public:

                    List();
                    ~List();
    void            PushBack(const T &data);
    void            PushFront(const T &data);
    void            PopBack();
    void            PopFront();
    void            Clear();    
    bool            IsEmpty() const;
    unsigned int    Size() const;
    T&              Front() const;
    T&              Back() const;

private:

    template <typename T>
    struct Node
    {
        Node(const T &data) : data(data), next(NULL) {}
        T      data;
        Node  *next;
    };

    Node<T> *head;
    Node<T> *tail;
};

template <typename T>
List<T>::List()
    : head(NULL),
      tail(NULL)
{

}

template <typename T>
List<T>::~List()
{
    Clear();
}

template <typename T>
void List<T>::PushBack(const T &data)
{   
    if ( !head )
    {
        head = new Node<T>(data);
        tail = head;
        return;
    }

    tail->next = new Node<T>(data);
    tail = tail->next;
}

template <typename T>
void List<T>::PushFront(const T &data)
{
    Node<T> *tmp = head;
    head = new Node<T>(data);
    head->next = tmp;

    if ( !tail )
    {
        tail = head;
    }
}

template <typename T>
void List<T>::PopBack()
{
    //empty list
    if ( !head )
    {
        throw std::out_of_range("Can't pop from empty list");
    }

    //list with one element
    if ( head == tail )
    {
        delete head;
        head = NULL;
        tail = NULL;
        return;
    }

    Node<T> *current = head;
    while ( current->next != tail )
    {
        current = current->next;
    }

    delete tail;
    tail = current;
    tail->next = NULL;
}

template <typename T>
void List<T>::PopFront()
{
    //empty list
    if ( !head )
    {
        throw std::out_of_range("Can't pop from empty list");
    }

    //list with one element
    if ( head == tail )
    {
        delete head;
        head = NULL;
        tail = NULL;
        return;
    }

    Node<T> *tmp = head->next;
    delete head;
    head = tmp;
}

template <typename T>
void List<T>::Clear()
{
    Node<T> *current = head;
    while ( head )
    {
        current = head;
        head = head->next;
        delete current;
    }

    head = NULL;
    tail = NULL;
}

template <typename T>
bool List<T>::IsEmpty() const
{
    return ( head == NULL );
}

template <typename T>
unsigned int List<T>::Size() const
{
    unsigned int size = 0;
    for ( Node<T> *current = head; current; current = current->next )
    {
        ++size;
    }

    return size;
}

template <typename T>
T& List<T>::Front() const
{
    if ( !head )
    {
        throw std::out_of_range("Can't return value from empty list");
    }

    return head->data;
}

template <typename T>
T& List<T>::Back() const
{
    if ( !head )
    {
        throw std::out_of_range("Can't return value from empty list");
    }

    return tail->data;
}
share|improve this question
3  
Hm, I realised there is no way of iterating through it. I should implement an iterator –  Innkeeper Apr 5 at 17:47

2 Answers 2

up vote 7 down vote accepted
  • Consider using a different naming convention for your data members and methods, such as camelCase or snake_case. Your user-defined types are already uppercase, which is okay. Whichever you choose, it's more readable to keep them separate.

  • The push/pop methods here imply that this is a stack implementation, but a linked list should be capable of inserting or removing a node at any location in the list. Consider adding additional functions for this. For an idea of typical linked list functions, read this.

  • Since you're using a list class, you should have a size member to maintain. Your Size() method is calculating the size at each call by traversing, which is O(n).

    Instead, have a size data member and update it with other operations:

    • initialize to 0 in the initializer list
    • increment with each push
    • decrement with each pop
    • reset to 0 with each clear

    When you call Size(), it should just return the data member value, which is O(1).

    It should also return a std::size_t. It is closest to the return type used in STL containers, and a very large list size may not fit inside an unsigned int.

  • Instead of having a return in PushFront(), put the last two lines into an else block.

  • Shouldn't popBack() check tail if PopFront() checks head? Although they may be pointing to the same node if there's only one node, but the intent is more clear this way.

  • You should probably also have a Front() and Back() that return a T const&, in case the reference will not be modified or a const value is needed.

  • You should have some way of displaying the list. For that, consider overloading operator<< for the List class (instead of a display function), allowing you to do this:

    List list;
    std::cout << list;
    

    You could also overload Node's operator, allowing you to output a node within the List class.

  • std::out_of_range is defined in <stdexcept>, not <exception>.

share|improve this answer
    
Thank You! I might edit with the implemented iterator later. –  Innkeeper Apr 5 at 19:59
3  
@Innkeeper: You're welcome! As that change may affect more of your code, I'd recommend asking a new question with that implementation. Follow-up questions are okay here. –  Jamal Apr 5 at 20:01
    
What's the problem with the capitalization convention? I don't see any issue. –  200_success Apr 6 at 3:35
2  
@200_success: More of a personal preference, I suppose. It just seems odd sharing it with types, variables, and functions. –  Jamal Apr 6 at 3:38
    
If I overloaded operator<<, I still wouldn't have any way to iterate through and say, modify each item. Wouldn't an iterator/const iterator be more useful? Well, these could coexist, but I'm on the right track thinking this really needs an iterator, right? –  Innkeeper Apr 6 at 9:56

IMO, if you're going to implement a linked list (probably shouldn't--they're pretty worthless) it's best to specify both the data and the next pointer when you create a node.

Node(const T &data, struct node *next = nullptr) : data(data), next(next) {}

This lets you simplify quite a bit of the insertion code. For example:

template <typename T>
void List<T>::PushFront(const T &data) {

    head = new node(data, head);

    if ( !tail )
        tail = head;
}

The other big thing that jumped out at me (that Jamal hasn't already discussed) was using NULL. I'd prefer nullptr, unless you're stuck with an ancient compiler that doesn't support it yet (in which case, you still want to do it, but after updating your compiler).

share|improve this answer
    
I haven't forgotten about nullptr, but I sometimes feel tempted to not bring it up if it appears that the OP isn't already using C++11. –  Jamal Apr 6 at 3:34
    
Yeah, much clearer with that ctor, thanks! –  Innkeeper Apr 6 at 9:58
    
Linked lists are not worthless, you need to know when to use the correct data structure. Linked lists have constant time insertion and deletion at the front and tail or anywhere where you already have a pointer. If you are frequently inserting or deleting at the front or tail (like a queue) then a linked list is just fine. A plain vector or array would perform terribly in this case making a pop operation an \$\mathcal{O}(n)\$ operation. –  Emily L. Aug 21 at 15:26
    
@EmilyL.: You sound like you were in the data structures classes I taught 20+ years ago. At that time, the advice was even sort of close to accurate. Unfortunately, it wasn't nearly as good then as I thought, and it's much less so now. –  Jerry Coffin Aug 21 at 15:39
    
@JerryCoffin "Right tool for the job" is no longer applicable? Then I'm out of a job :'( Jokes aside, I'm not saying to use linked lists for everything or even most things. I'm saying that there are use cases and you need to know what structure you need and how it will perform on your target machine. Blanket statements like "linked-lists are worthless" are not constructive or educational in any way. –  Emily L. Aug 21 at 15:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.