# Validity of doubly linked list

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_
#include <iostream>
template<class E>

public:
E data;

}
this->data = e;
}
}
E getData() {
return data;
}
void setData(E e) {
this->data = e;
}
return leftNode;
}
this->leftNode = node;
}
return rightNode;
}
this->rightNode = node;
}

};



LinkedList Class:

    #ifndef LINKEDLIST_H_
template<class T>
private:
int size;
public:

lastNode = firstNode;
size = 0;
}

}

void pushFront(T t) {
if (size == 0) {
pushBack(t);
return;
}
size++;
}

void pushBack(T t) {
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;
}

return firstNode;
}

return lastNode;
}

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

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

};


New LinkedList Class:

#ifndef LINKEDLIST_H_
#include <iostream>
template<class T>
/**
* Private inner node class
*/
//Have to use new template. Does not run if I try to use T
template<class E>
public:
E data;

}
this->data = e;
}
}
};
private:
int size;
public:

/*
* Init left and right node to null to prevent exception.
*/
firstNode->leftNode = NULL;
firstNode->rightNode = NULL;
lastNode = firstNode;
size = 0;
}

}
}

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;
}
size++;
}

void pushBack(T t) {
if (size == 0) {
firstNode = lastNode;
}
size++;
}

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

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

return *firstNode;
}

return *lastNode;
}

int const Size() {
return size;
}

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

};

• Xubuntu 13.10
• GCC Compiler installed with sudo apt-get install g++

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>
public:
E data;

}
this->data = e;
}
}
};


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>
public:
E data;

}
this->data = e;
}
}
};
private:
int size;


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) {
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;


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;
};


• 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.

• 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. – horvste Feb 14 '14 at 0:04
• @horvste: Okay. I'm a C++ reviewer (and no Java experience), so I wasn't aware of that. – Jamal Feb 14 '14 at 0:06
• @horvste These methods are to satisfy the (De)Queue interface. – David Harkness Feb 14 '14 at 4:02

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.

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>
private:

public:
T data;
}
this->data = e;
}
}
T getData() {
return data;
}
void setData(T e) {
this->data = e;
}
return leftNode;
}
this->leftNode = node;
}
return rightNode;
}
this->rightNode = node;
}

};
int size;
public:

lastNode = firstNode;
size = 0;
}

}

void pushFront(T t) {
if (size == 0) {
pushBack(t);
return;
}
size++;
}

void pushBack(T t) {
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;
}

return firstNode;
}

return lastNode;
}

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

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>
private:

public:
T data;
}
this->data = e;
}
}
};
int size;
public:

lastNode = firstNode;
size = 0;
}

}

void pushFront(T t) {
if (size == 0) {
pushBack(t);
return;
}
size++;
}

void pushBack(T t) {
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;
}

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() {
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>
private:

public:
T data;
this->data = e;
leftNode = 0;
rightNode = 0;
}
}
};
int size;
public:

firstNode = 0;
lastNode = 0;
size = 0;
}

}

void pushFront(T t) {
++size;
if (size == 1) {
return;
}
}

void pushBack(T t) {
++size;
if (size == 1) {
return;
}
}

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;
}

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>
private:
public:
T data;
this->data = e;
leftNode = 0;
rightNode = 0;
}
}
};
int size;
public:

firstNode = 0;
lastNode = 0;
size = 0;
}

while (temp != NULL) {
delete temp;
temp = next;
}
}

void pushFront(T t) {
++size;
if (size == 1) {
return;
}
}

void pushBack(T t) {
++size;
if (size == 1) {
return;
}
}

T pollFirst() {
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() {
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;
}

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

• Now THAT is some seriously EPIC answer! – Mathieu Guindon Feb 14 '14 at 3:09
• @lol.upvote: It did need a lot of cleaning. :-) Such implementations are taken quite seriously. – Jamal Feb 14 '14 at 3:14
• 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. – horvste Feb 14 '14 at 17:55
• @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). – ChrisW Feb 14 '14 at 18:00
• @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 = ???; } – ChrisW Feb 14 '14 at 19:00

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.