31
\$\begingroup\$

I am currently in a data-structures class. The professor will be providing a singly linked list. I wanted to make a doubly linked list to "learn" how to do it. I tested it and I think it works. After making it, I did compare it to other doubly linked lists but I still want to see if there is anything I am missing. Are there any other problems with it?

LinkNode Class:

#ifndef LINKNODE_H_
#define LINKNODE_H_
#include <iostream>
template<class E>
class LinkNode {

public:
    E data;
    LinkNode<E> *leftNode;
    LinkNode<E> *rightNode;
    LinkNode() {

    }
    LinkNode(E e) {
        this->data = e;
    }
    ~LinkNode() {
    }
    E getData() {
        return data;
    }
    void setData(E e) {
        this->data = e;
    }
    LinkNode<E> getLeftNode() {
        return leftNode;
    }
    void setLeftNode(LinkNode<E> node) {
        this->leftNode = node;
    }
    LinkNode<E> getRightNode() {
        return rightNode;
    }
    void setRightNode(LinkNode<E> node) {
        this->rightNode = node;
    }

};

#endif /* LINKNODE_H_ */

LinkedList Class:

    #ifndef LINKEDLIST_H_
#define LINKEDLIST_H_
#include "LinkNode.h"
template<class T>
class LinkedList {
private:
    int size;
    LinkNode<T> *firstNode;
    LinkNode<T> *lastNode;
public:

    LinkedList() {
        firstNode = new LinkNode<T>();
        lastNode = firstNode;
        size = 0;
    }

    ~LinkedList() {
    }

    void pushFront(T t) {
        if (size == 0) {
            pushBack(t);
            return;
        }
        LinkNode<T> *linkNode = new LinkNode<T>(t);
        linkNode->rightNode = firstNode;
        firstNode->leftNode = linkNode;
        firstNode = linkNode;
        size++;
    }

    void pushBack(T t) {
        LinkNode<T> *linkNode = new LinkNode<T>(t);
        linkNode->leftNode = lastNode;
        lastNode->rightNode = linkNode;
        lastNode = linkNode;
        if (size == 0) {
            firstNode = lastNode;
        }
        size++;
    }

    T pollFirst() {
        T t = firstNode->data;
        firstNode = firstNode->rightNode;
        size--;
        return t;
    }

    T pollLast() {
        T t = lastNode->data;
        lastNode = lastNode->leftNode;
        size--;
        return t;
    }

    LinkNode<T> getFirstNode() {
        return firstNode;
    }

    LinkNode<T> getLastNode() {
        return lastNode;
    }

    T searchNode(T t) {
        return t;
    }
    int Size() {
        return size;
    }

    void printLinkedList() {
        LinkNode<T> *temp = firstNode;
        while (temp != NULL) {
            std::cout << temp->data << "\t";
            temp = temp->rightNode;
        }
    }

};
#endif /* LINKEDLIST_H_ */

New LinkedList Class:

#ifndef LINKEDLIST_H_
#define LINKEDLIST_H_
#include <iostream>
template<class T>
class LinkedList {
    /**
     * Private inner node class
     */
    //Have to use new template. Does not run if I try to use T
    template<class E>
    class LinkNode {
    public:
        E data;
        LinkNode<E> *leftNode;
        LinkNode<E> *rightNode;
        LinkNode() {

        }
        LinkNode(E e) {
            this->data = e;
        }
        ~LinkNode() {
        }
    };
private:
    int size;
    LinkNode<T> *firstNode;
    LinkNode<T> *lastNode;
public:

    LinkedList() {
        firstNode = new LinkNode<T>();
        /*
         * Init left and right node to null to prevent exception.
         */
        firstNode->leftNode = NULL;
        firstNode->rightNode = NULL;
        lastNode = firstNode;
        size = 0;
    }

    ~LinkedList() {
        LinkNode<T> *linkNode = firstNode->rightNode;
        while (linkNode != NULL) {
            delete linkNode->leftNode;
            linkNode = linkNode->rightNode;
        }
    }

    void pushFront(T t) {
        //the size is zero therefore we are really justing pushing to the back of the linked list
        if (size == 0) {
            pushBack(t);
            return;
        }
        LinkNode<T> *linkNode = new LinkNode<T>(t);
        linkNode->rightNode = firstNode;
        firstNode->leftNode = linkNode;
        firstNode = linkNode;
        size++;
    }

    void pushBack(T t) {
        LinkNode<T> *linkNode = new LinkNode<T>(t);
        linkNode->leftNode = lastNode;
        lastNode->rightNode = linkNode;
        lastNode = linkNode;
        if (size == 0) {
            firstNode = lastNode;
        }
        size++;
    }

    T pollFirst() {
        LinkNode<T> *temp = firstNode;
        T t = firstNode->data;
        firstNode = firstNode->rightNode;
        delete temp;
        size--;
        return t;
    }

    T pollLast() {
        LinkNode<T> *temp = lastNode;
        T t = lastNode->data;
        lastNode = lastNode->leftNode;
        delete temp;
        size--;
        return t;
    }

    LinkNode<T> getFirstNode() {
        return *firstNode;
    }

    LinkNode<T> getLastNode() {
        return *lastNode;
    }

    int const Size() {
        return size;
    }

    void const printLinkedList() {
        LinkNode<T> *temp = firstNode;
        while (temp != NULL) {
            std::cout << temp->data << "\t";
            temp = temp->rightNode;
        }
    }

};
#endif /* LINKEDLIST_H_ */
  • Xubuntu 13.10
  • GCC Compiler installed with sudo apt-get install g++
\$\endgroup\$
0

4 Answers 4

15
\$\begingroup\$

New Linked List Class

This is a review of the new "New Linked List Class".


Here you wrote:

//Have to use new template. Does not run if I try to use T
template<class E>
class LinkNode {
public:
    E data;
    LinkNode<E> *leftNode;
    LinkNode<E> *rightNode;
    LinkNode() {

    }
    LinkNode(E e) {
        this->data = e;
    }
    ~LinkNode() {
    }
};

I said, "LinkNode is no longer a template class: it's a nested class of a template class."

You said you don't want to read my code, but here's my code ahead:

    // Not a template class.
    // template<class E>
    class LinkNode {
    public:
        E data;
        LinkNode *leftNode;
        LinkNode *rightNode;
        LinkNode() {

        }
        LinkNode(E e) {
            this->data = e;
        }
        ~LinkNode() {
        }
    };
private:
    int size;
    LinkNode *firstNode;
    LinkNode *lastNode;

In C++, unlike in Java, members are not auto-initialized to 0. Maybe your compiler leaves them initialized to 0, but mine doesn't. Your compiler is probably leaving you with uninitialized memory, which happened to be zero-filled, but which would no longer be zero-filled if your program had been running for longer with lots of previous news and deletes.

If I do printLinkedList after the first push, it crashes. That's because your push method is like this:

void pushBack(T t) {
    LinkNode<T> *linkNode = new LinkNode<T>(t);
    linkNode->leftNode = lastNode;
    lastNode->rightNode = linkNode;
    lastNode = linkNode;
    if (size == 0) {
        firstNode = lastNode;
    }
    size++;
}

It doesn't initialize the rightNode member of the new linkNode.

You probably want to initialize everything in your LinkNode constructor: set leftNode and rightNode to 0.


Before the first push, firstNode and lastNode point to your initial, empty, 'sentinel' node.

After the first push, firstNode and lastNode point to the new node, and the new node's leftNode points to your sentinel node.

Then after the next pushFront, nothing is pointing to your sentinel node. If you're going to lose your sentinel node from the list, I don't see any good reason for creating it in the first place. (The solution I proposed in my other answer doesn't create an initial sentinel node, and instead sets and expects firstNode and lastNode to be NULL when the list is empty).


If I call printLinkedList before I push anything onto the list, it prints the value (possibly 0, possibly something else) contained in your initial, empty, sentinel node.


If I run the following test code then it prints an infinite number of 2s:

LinkedList<int> linked;
linked.printLinkedList();
linked.pushFront(10);
linked.printLinkedList();
linked.pollFirst();
linked.printLinkedList();
linked.pushBack(2);
linked.printLinkedList();
\$\endgroup\$
39
\$\begingroup\$

LinkNode

Assuming this is not an internal class:

A huge problem (probably the biggest) with this is that everything is public. The three data members should be private. Data members should always be private, otherwise any outside code can access them. This defeats the purpose of using a class as opposed to a struct.

You should also not have any accessors ("getters") and mutators ("setters"). The node should belong only to the class, and none of its implementation should be exposed to the public. The list itself should use the nodes, and it should be able to access the node's members directly.

An implementation of a node includes its pointers (next for a singly list, or previous and next nodes for a doubly list) and its data. That can either be a struct or a class, inside the list class as a private data member.

An example of a templated node implementation as a class:

template <typename T>
class Node
{
    T data;
    Node<T>* previous;
    Node<T>* next;
};

LinkedList

  • Huge problem: no destructor! You need a destructor for a linked list so that its allocated nodes will be deleted after use. Without this, you'll have memory leaks. The destructor should go through each node, using delete on each node until the list is empty.

  • You should define a copy constructor and assignment operator (operator=). The default copy constructor performs a shallow copy versus a deep copy, and a shallow copy is bad to use with pointers as members. Copying can still compile (the default is used), but it won't be done properly.

  • size() should be const since it's not modifying any data members:

    int Size() const { return size; }
    

    On another note, Size() should be lowercase to match your other functions. It shouldn't need to have different naming.

  • printLinkedList() should also be const as it's not modifying any data members. This applies to display functions in general, due to their nature.

  • searchNode() just returns its argument instead of conducting an actual search, so it's obsolete and should be removed.

  • What are pollFirst() and pollLast() used for? The names aren't very clear. If they're short for something, write them out entirely.

  • Get rid of getFirstNode() and getLastNode(). You should not expose the nodes to the public, which is bad for encapsulation. Keep the node functionality within the list.

\$\endgroup\$
3
  • \$\begingroup\$ I am a java developer and "their" linked list contains pollFirst() and pollLast(). It returns the first or last nodes data and then removes them from the linked list. \$\endgroup\$
    – horvste
    Feb 14, 2014 at 0:04
  • \$\begingroup\$ @horvste: Okay. I'm a C++ reviewer (and no Java experience), so I wasn't aware of that. \$\endgroup\$
    – Jamal
    Feb 14, 2014 at 0:06
  • 2
    \$\begingroup\$ @horvste These methods are to satisfy the (De)Queue interface. \$\endgroup\$ Feb 14, 2014 at 4:02
26
\$\begingroup\$

When I run your test code on my machine, it crashes.

  • 1st node on the list contains '10'
  • 2nd node on the list contains '0'
  • 3rd node on the list contains '2'
  • rightNode element of the 3rd node contains a garbage address => exception when trying to dereference the 4th node

So I'll try to clean this up.

Following from Jamal's answer, the following reworks your code to implement his suggestions.

First, the only change is that I made LinkNode a private nested class of LinkList.

Second, we don't need two separate template parameters anymore: so get rid of E and have only T. LinkNode is no longer a template class: it's a nested class of a template class.

#include <iostream>
template<class T>
class LinkedList {
private:
    class LinkNode {

    public:
        T data;
        LinkNode *leftNode;
        LinkNode *rightNode;
        LinkNode() {
        }
        LinkNode(T e) {
            this->data = e;
        }
        ~LinkNode() {
        }
        T getData() {
            return data;
        }
        void setData(T e) {
            this->data = e;
        }
        LinkNode getLeftNode() {
            return leftNode;
        }
        void setLeftNode(LinkNode node) {
            this->leftNode = node;
        }
        LinkNode getRightNode() {
            return rightNode;
        }
        void setRightNode(LinkNode node) {
            this->rightNode = node;
        }

    };
    int size;
    LinkNode *firstNode;
    LinkNode *lastNode;
public:

    LinkedList() {
        firstNode = new LinkNode();
        lastNode = firstNode;
        size = 0;
    }

    ~LinkedList() {
    }

    void pushFront(T t) {
        if (size == 0) {
            pushBack(t);
            return;
        }
        LinkNode *linkNode = new LinkNode(t);
        linkNode->rightNode = firstNode;
        firstNode->leftNode = linkNode;
        firstNode = linkNode;
        size++;
    }

    void pushBack(T t) {
        LinkNode *linkNode = new LinkNode(t);
        linkNode->leftNode = lastNode;
        lastNode->rightNode = linkNode;
        lastNode = linkNode;
        if (size == 0) {
            firstNode = lastNode;
        }
        size++;
    }

    T pollFirst() {
        T t = firstNode->data;
        firstNode = firstNode->rightNode;
        size--;
        return t;
    }

    T pollLast() {
        T t = lastNode->data;
        lastNode = lastNode->leftNode;
        size--;
        return t;
    }

    LinkNode getFirstNode() {
        return firstNode;
    }

    LinkNode getLastNode() {
        return lastNode;
    }

    T searchNode(T t) {
        return t;
    }
    int Size() {
        return size;
    }

    void printLinkedList() {
        LinkNode *temp = firstNode;
        while (temp != NULL) {
            std::cout << temp->data << "\t";
            temp = temp->rightNode;
        }
    }

};

Next, I tried to invoke one of those methods which returns a LinkNode. Adding a linked.getFirstNode(); statement to the test program gives me the following compiler error:

'LinkedList<T>::LinkNode::LinkNode(T)' : cannot convert parameter 1 from 'LinkedList<T>::LinkNode *' to 'int'

The problem with the getFirstNode() method is that it promises to return a LinkNode and then tries to return firstNode which is a LinkNode* pointer (which is illegal). With C++ templates the compiler doesn't try to instantiate the method unless you use it; you hadn't tried to use it so the compiler didn't notice that coding error.

Fortunately you shouldn't be trying to use it: LinkNode should be a private implementation detail of LinkedList. So I'll just remove the getFirstNode and getLastNode methods.

It's not clear what your searchNode method is doing too, and you're not testing it, so I'll remove that too.

And I'll remove most of the LinkNode methods, because LinkedList accesses its data members directly, and because classes other than LinkedList cannot access any of its members at all.

#pragma once
#include <iostream>
template<class T>
class LinkedList {
private:
    class LinkNode {

    public:
        T data;
        LinkNode *leftNode;
        LinkNode *rightNode;
        LinkNode() {
        }
        LinkNode(T e) {
            this->data = e;
        }
        ~LinkNode() {
        }
    };
    int size;
    LinkNode *firstNode;
    LinkNode *lastNode;
public:

    LinkedList() {
        firstNode = new LinkNode();
        lastNode = firstNode;
        size = 0;
    }

    ~LinkedList() {
    }

    void pushFront(T t) {
        if (size == 0) {
            pushBack(t);
            return;
        }
        LinkNode *linkNode = new LinkNode(t);
        linkNode->rightNode = firstNode;
        firstNode->leftNode = linkNode;
        firstNode = linkNode;
        size++;
    }

    void pushBack(T t) {
        LinkNode *linkNode = new LinkNode(t);
        linkNode->leftNode = lastNode;
        lastNode->rightNode = linkNode;
        lastNode = linkNode;
        if (size == 0) {
            firstNode = lastNode;
        }
        size++;
    }

    T pollFirst() {
        T t = firstNode->data;
        firstNode = firstNode->rightNode;
        size--;
        return t;
    }

    T pollLast() {
        T t = lastNode->data;
        lastNode = lastNode->leftNode;
        size--;
        return t;
    }

    int Size() const {
        return size;
    }

    void printLinkedList() const {
        LinkNode *temp = firstNode;
        while (temp != NULL) {
            std::cout << temp->data << "\t";
            temp = temp->rightNode;
        }
    }

};

The next problem is with your use of a sentinel node when the list is empty.

The following method creates an initial empty node ...

LinkedList() {
    firstNode = new LinkNode();
    lastNode = firstNode;
    size = 0;
}

... but doesn't initialize the node's leftNode and rightNode elements (which causes the crash later on).

Also I'm confused by the idea of having an empty node in the list: how will you make sure that printLinkedList will not try to print the contents of the empty node?

So I change the code as follows to get rid of the empty node:

  • Remove the default constructor from LinkNode (so it can only be instantiated when there is data)
  • Initialize the pointer elements of LinkNode to null in the LinkNode constructor
  • Initialize the pointer elements of LinkedList to null in the LinkedList constructor
  • Special case in pushFront and pushBack to handle inserting into an empty list
  • Special case in pollFirst and pollLast to handle removing the last node from the list

After these changes the code looks like this:

#pragma once
#include <iostream>
template<class T>
class LinkedList {
private:
    class LinkNode {

    public:
        T data;
        LinkNode *leftNode;
        LinkNode *rightNode;
        LinkNode(T e) {
            this->data = e;
            leftNode = 0;
            rightNode = 0;
        }
        ~LinkNode() {
        }
    };
    int size;
    LinkNode *firstNode;
    LinkNode *lastNode;
public:

    LinkedList() {
        firstNode = 0;
        lastNode = 0;
        size = 0;
    }

    ~LinkedList() {
    }

    void pushFront(T t) {
        LinkNode *linkNode = new LinkNode(t);
        ++size;
        if (size == 1) {
            firstNode = lastNode = linkNode;
            return;
        }
        linkNode->rightNode = firstNode;
        firstNode->leftNode = linkNode;
        firstNode = linkNode;
    }

    void pushBack(T t) {
        LinkNode *linkNode = new LinkNode(t);
        ++size;
        if (size == 1) {
            firstNode = lastNode = linkNode;
            return;
        }
        linkNode->leftNode = lastNode;
        lastNode->rightNode = linkNode;
        lastNode = linkNode;
    }

    T pollFirst() {
        T t = firstNode->data;
        firstNode = firstNode->rightNode;
        if (firstNode)
            firstNode->leftNode = NULL;
        --size;
        return t;
    }

    T pollLast() {
        T t = lastNode->data;
        lastNode = lastNode->leftNode;
        if (lastNode)
            lastNode->rightNode = NULL;
        --size;
        return t;
    }

    int Size() const {
        return size;
    }

    void printLinkedList() const {
        LinkNode *temp = firstNode;
        while (temp != NULL) {
            std::cout << temp->data << "\t";
            temp = temp->rightNode;
        }
    }
};

Also the test output looks like this (which is the correct result, and it's not crashing any longer):

10      0       2

A remaining problem is that you don't delete the nodes which you create. I change the code as follows:

  • Add a delete statement to the poll methods (to delete the node they remove from the list)
  • Invoke delete statements from the LinkedList destructor (to delete nodes on the list when the list is destroyed)

After these changes the code is as follows:

#pragma once
#include <iostream>
#include <assert.h>
template<class T>
class LinkedList {
private:
    class LinkNode {
    public:
        T data;
        LinkNode *leftNode;
        LinkNode *rightNode;
        LinkNode(T e) {
            this->data = e;
            leftNode = 0;
            rightNode = 0;
        }
        ~LinkNode() {
        }
    };
    int size;
    LinkNode *firstNode;
    LinkNode *lastNode;
public:

    LinkedList() {
        firstNode = 0;
        lastNode = 0;
        size = 0;
    }

    ~LinkedList() {
        LinkNode *temp = firstNode;
        while (temp != NULL) {
            LinkNode *next = temp->rightNode;
            delete temp;
            temp = next;
        }
    }

    void pushFront(T t) {
        LinkNode *linkNode = new LinkNode(t);
        ++size;
        if (size == 1) {
            firstNode = lastNode = linkNode;
            return;
        }
        linkNode->rightNode = firstNode;
        firstNode->leftNode = linkNode;
        firstNode = linkNode;
    }

    void pushBack(T t) {
        LinkNode *linkNode = new LinkNode(t);
        ++size;
        if (size == 1) {
            firstNode = lastNode = linkNode;
            return;
        }
        linkNode->leftNode = lastNode;
        lastNode->rightNode = linkNode;
        lastNode = linkNode;
    }

    T pollFirst() {
        LinkNode *found = firstNode;
        T t = found->data;
        firstNode = found->rightNode;
        if (firstNode)
            firstNode->leftNode = NULL;
        else {
            assert(size == 1);
            lastNode = 0;
        }
        delete found;
        --size;
        return t;
    }

    T pollLast() {
        LinkNode *found = lastNode;
        T t = found->data;
        lastNode = found->leftNode;
        if (lastNode)
            lastNode->rightNode = NULL;
        else {
            assert(size == 1);
            firstNode = 0;
        }
        delete found;
        --size;
        return t;
    }

    int Size() const {
        return size;
    }

    void printLinkedList() const {
        LinkNode *temp = firstNode;
        while (temp != NULL) {
            std::cout << temp->data << "\t";
            temp = temp->rightNode;
        }
    }
};
\$\endgroup\$
6
  • 1
    \$\begingroup\$ Now THAT is some seriously EPIC answer! \$\endgroup\$ Feb 14, 2014 at 3:09
  • 2
    \$\begingroup\$ @lol.upvote: It did need a lot of cleaning. :-) Such implementations are taken quite seriously. \$\endgroup\$
    – Jamal
    Feb 14, 2014 at 3:14
  • \$\begingroup\$ Mine doesn't crash. Could it be a compiler difference? I am using gcc compiler. Regardless, I will take your advice do some clean up and repost the code for further inspection. I am trying to learn it so I read your advice but did not look at the code. \$\endgroup\$
    – horvste
    Feb 14, 2014 at 17:55
  • 1
    \$\begingroup\$ @horvste Yes it could be a compiler difference. Notice when you call firstNode = new LinkNode<T>(); you don't initialize the leftValue and rightValue fields of that first node. Possibly/probably with your compiler, those field values happen to be 0 which causes your while (temp != NULL) in printLinkedList to exit when it finds them. In my compiler running in debug mode, uninitialized fields are initialized to a value like 0xadadadad (which, by crashing, makes it easier to detect trying to use an uninitialized pointer). \$\endgroup\$
    – ChrisW
    Feb 14, 2014 at 18:00
  • 1
    \$\begingroup\$ @horvste What was wrong is that in C++ (unlike in Java) if you don't initialize a field in a constructor then the field contains a pseudo-random value (possibly but not necessarily 0). So your LinkNode() { } constructor should probably initialize its leftField and rightField elements to 0 explicitly: LinkNode() { leftField = 0; rightField = 0; data = ???; } \$\endgroup\$
    – ChrisW
    Feb 14, 2014 at 19:00
15
\$\begingroup\$

One quite important thing to do when you work with linked lists is to link and unlink the previous/next nodes as you add/remove nodes.

If you can only add at the end, that's good, but if you can insert a node anywhere you have to be careful. The same goes with removing nodes.

         +--------+    +--------+    +--------+
         |    A   |    |   B    |    |    C   |
         |   A.n  |--->|  B.n   |--->|   C.n  |---> null
null <---|   A.p  |<---|  B.p   |<---|   C.p  |
         +--------+    +--------+    +--------+

In this representation, removing B from the list means making A.n point to C instead of B, and C.p point to A instead of B. And setting B.n and B.p to nullptr.

Similarly, if you only had A and C and wanted to add B, now you need to set B.p to A and A.n to B. Then C.p to B and B.n to C.

It seems you only want to offer a push and a pop, so it makes it simpler, but that's something to keep in mind.

Two other notes:

  1. I see that you use this->... within the class; that's not necessary.

  2. You may want to consider using std::shared_ptr<>() so that way multiple people can own a node and it doesn't get deleted until all are done with it.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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