C++ single linked list (node class)

[figuer25]

Hi so I am just trying to figure out what is wrong with my program. I am trying to implement the node class in C++. All I want to do is learn how to implement it and get it working. I am not trying to use it to create a list class, I just want to learn how to work with linked lists and the node class for certain interview questions. Anyways I seem to have a problem with my next pointer. When I insert a new node it seems to work as I kept a length field to see if its working and the length is incremented but I must be doing something wrong with the next and front pointers. Please help, let me know what I may be doing wrong

#ifndef NODE_H_
#define NODE_H_

#include <iostream>

using namespace std;

template <class T>
class node {
	public:
		int length;
		T nodeValue;
		node<T> *front, *next;

		// Default constructor
		node(): next(NULL), front(NULL), length(0)
		{}

		// Constructor. Initialize nodeValue and next.
		node(const T& item, node<T> *nextNode = NULL):
		nodeValue(item), next(nextNode)
		{}

		// Add a new node
		void addNodeAtFront(const T& value);

		virtual ~node();
};

template <typename T>
void node<T>::addNodeAtFront(const T& value){

	node<T> *newNode;
	newNode = new node<T>(value,next);

	if (front == NULL){
		// Set the new node to be the front
		front = newNode;
		if (newNode->next == NULL)
			cout<<"newNode->next is NULL"<<endl;
		//cout<<newNode<<endl;
		length++;
	}
	else {
		// Set the new node to point at the next node
		newNode->next = front;
		// Set the new node to be the 'front'
		front = newNode;
		//cout<<newNode<<endl;
		length++;
	}

}

template <typename T>
node<T>::~node() {
	// TODO Auto-generated destructor stub
}

#endif /* NODE_H_ */

Here is the main program

#include <iostream>
#include "node.h"

using namespace std;

int main(){
	node<int> *p;

	p = new node<int>(5);
	cout<<"Here is your value: "<<p->nodeValue<<endl;

	for (int i = 0; i < 10; i++)
		p->addNodeAtFront(i);

	cout<<"p->length is: "<<p->length<<endl;

	if (p->next == NULL)
		cout<<"P->next is NULL"<<endl;
	else
		cout<<"P->next is not NULL"<<endl;

	return 0;
}

I had some code to write the list i.e.

while (P != NULL){
   cout<<p->nodeValue<<endl;
p = p->next;
}

but I erased it and that's is why I added the check to see if p->next is NULL and it is.

here is the output:

Here is your value: 5
newNode->next is NULL
p->length is: 10
P->next is NULL

[mike_2000_17]

p->next will be NULL for sure, do you see any line in addNodeAtFront() which starts with "next =".. the answer is no. So next will start with the value NULL and will remain that way.

I think you have mixed up front and next in your addNodeAtFront().. not entirely, but enough that I can't understand where the new node that is added should stand, and what exactly front and next point to, in the whole scheme of things.

Think of a linked list as a chain (excuse the ascii artwork, and I will use prev for what I think you call front):

NULL
 ||
prev <- node1 -> next
          ||      ||
         prev <- node2 -> next
                           ||
                          NULL

So to insert a node between node1 and node2 from the above, you need to set the new_node->prev to node1, node1->next to new_node, new_node->next to node2 and node2->prev to new_node. All these are accessible from either node1 or node2 (hence, a bi-directional linked-list). If you are implementing a unidirectional linked-list, then it is the same business but simpler, and of course, you can only add elements in one direction.

But again, I'm not sure of what you want to accomplish, what does length really mean in a linked-list? The idea of a linked-list is that it is decentralized, i.e. you shouldn't need any oversight as to the length, to go through the list in one direction, you start at the first node and follow the next pointers until that next pointer is NULL and you stop, so length is useless, but I think you know that already. What is front supposed to point to? the starting node or just the one before (as prev in my example).

Final note: >>I am trying to implement the node class in C++.
Node is a very general term and can refer to many things, so that statement sort of assumes too much that we know exactly what you are talking about when you say node class. There are nodes in unidirectional and bidirectional linked-lists, in trees, in graphs, in cycles, and a whole bunch of non pure computer science problems but still programming problems (but maybe I'm the only one who finds that confusing, as a non computer scientist myself).

[AuburnMathTutor]

Uh, I think it's normally customary for the node class and the linked-list class to be made into separate entities. Without looking too hard at your code, this could be part of the problem. In any event, it's dangerous and - frankly - weird that every node contains a reference to the front, as well as the length of the list... since all nodes do.

In other words, if you are trying to learn about linked lists for an interview, this is in the danger zone. Are you familiar with the "standard" definition of a linked list structure? I'm very serious.

Looking at your code in somewhat more detail, the problem seems to be that there are several "fronts" and there's no clear indication you're ever using the correct one, or that the correct front is ever being established. This problem is corrected by correctly separating the ideas of "node" and "list". Please let me or others know if reference material on constructing and manipulating linked lists is required.

[figuer25]

p->next will be NULL for sure, do you see any line in addNodeAtFront() which starts with "next =".. the answer is no. So next will start with the value NULL and will remain that way.

I think you have mixed up front and next in your addNodeAtFront().. not entirely, but enough that I can't understand where the new node that is added should stand, and what exactly front and next point to, in the whole scheme of things.

Think of a linked list as a chain (excuse the ascii artwork, and I will use prev for what I think you call front):

NULL
 ||
prev <- node1 -> next
          ||      ||
         prev <- node2 -> next
                           ||
                          NULL

So to insert a node between node1 and node2 from the above, you need to set the new_node->prev to node1, node1->next to new_node, new_node->next to node2 and node2->prev to new_node. All these are accessible from either node1 or node2 (hence, a bi-directional linked-list). If you are implementing a unidirectional linked-list, then it is the same business but simpler, and of course, you can only add elements in one direction.

But again, I'm not sure of what you want to accomplish, what does length really mean in a linked-list? The idea of a linked-list is that it is decentralized, i.e. you shouldn't need any oversight as to the length, to go through the list in one direction, you start at the first node and follow the next pointers until that next pointer is NULL and you stop, so length is useless, but I think you know that already. What is front supposed to point to? the starting node or just the one before (as prev in my example).

Final note: >>I am trying to implement the node class in C++.
Node is a very general term and can refer to many things, so that statement sort of assumes too much that we know exactly what you are talking about when you say node class. There are nodes in unidirectional and bidirectional linked-lists, in trees, in graphs, in cycles, and a whole bunch of non pure computer science problems but still programming problems (but maybe I'm the only one who finds that confusing, as a non computer scientist myself).

Hey thanks for the help. I was a bit confused my self with the next pointer. I was not thinking that the next pointer needed to be given a value except when I want to give the 'newNode->next' value. I made the mistake. Oh and this is for a single linked list, meaning unidirectional based on the terms you used. And you are right, nodes are also used in tress and graphs etc. since I said linked list I assumed everyone knows I was referring to nodes for a linked list. I will add the link to the new pointer and that should fix my problem, I did have front and next confused for a while but I think I got it now. Also this function is to insert a node at the front of the list so with every new node I add I have to change front to point at the new node after I set newNode->next = front.

[figuer25]

Uh, I think it's normally customary for the node class and the linked-list class to be made into separate entities. Without looking too hard at your code, this could be part of the problem. In any event, it's dangerous and - frankly - weird that every node contains a reference to the front, as well as the length of the list... since all nodes do.

In other words, if you are trying to learn about linked lists for an interview, this is in the danger zone. Are you familiar with the "standard" definition of a linked list structure? I'm very serious.

Looking at your code in somewhat more detail, the problem seems to be that there are several "fronts" and there's no clear indication you're ever using the correct one, or that the correct front is ever being established. This problem is corrected by correctly separating the ideas of "node" and "list". Please let me or others know if reference material on constructing and manipulating linked lists is required.

I think the first guy nailed it. I ll try that first. By standard you mean declaring it as a POD (Plain Old Data) type struct with no constructors and then use it within a class as in a "linkedList" class and use object composition by using a node object within the class?

like this...

struct node {
   int nodeValue;
   node *next;
};

class LinkedList {
.....
   private:
      node *p
}

[figuer25]

mike_2000_17 you helped me focus on the problem. I was assigning newNode->next front instead of next it self, I was treating newNode like I was trying to reference it from main.

so heres the code change...

template <typename T>
void node<T>::addNodeAtFront(const T& value){

	node<T> *newNode;
	newNode = new node<T>(value,front);


	if (front == NULL){
		// Set the new node to be the front
		front = newNode;
		if (newNode->next == NULL)
			cout<<"newNode->next is NULL"<<endl;
	}
	else {
		// Set the new node to point at the next node
		next = front;           // I was assigning 'newNode->next = front'
		
                // Set the new node to be the 'front'
		front = newNode;
	}

}

[figuer25]

Ok I changed the code a bit around because I had my "front" pointer inside my class definition. I want to declare that pointer in main now and pass it to the function. The point of this code is to add a node to the FRONT of the list. So we have

front--->[1 | next]--> NULL

so if we add a new node we have

front--->[2 | next]-->[1 | next]--> NULL

the first node's 'next' pointer will ALWAYS be null because the new nodes are being added at the front. I got the code to work with using a 'front' node pointer which I set inside my constructor BUT when I try to take this out of the code and declare it in main and pass it in as a parameter I get an infinite loop. Here is the code...

#include <iostream>
#include <string>

using namespace std;

template <class T>
class node {
	public:
		T nodeValue;
		node<T> *next;

		// Default constructor
		node(): next(NULL)
		{}

		// Constructor. Initialize nodeValue and next.
		node(const T& item, node<T> *nextNode = NULL):
		nodeValue(item), next(nextNode)
		{}

		// Add a new node to the front of the list
		void addNodeAtFront(const T& value, node<T> *frontNode);

		// Write your node list
		void writeList(node<T> *frontNode, const string& seperator);

		virtual ~node();
};

template <typename T>
void node<T>::addNodeAtFront(const T& value, node<T> *frontNode){

	node<T> *newNode = new node<T>(value,frontNode);

	// Set the new node to point at the next node
	next = frontNode;

	// Set the new node to be the 'front'
	frontNode = newNode;
}

template <typename T>
void node<T>::writeList(node<T> *frontNode, const string& seperator){

	node<T> *curr = frontNode;
	while (curr != NULL){
		cout<<curr->nodeValue<<seperator;
		curr = curr->next;
	}
}

Here is main()

#include <iostream>
#include "node.h"

using namespace std;

int main(){

	node<int> *front = NULL, *p = new node<int>;

	front = p;
	for (int i = 0; i < 5; i++)
		p->addNodeAtFront(i,front);

	p->writeList(front,"  ");

	return 0;
}

Its actually an infinite loop. Its 3:30 am and I am tired of staring at this code, someone with fresh eyes give me some hints

[mike_2000_17]

Ok, now that I understand the problem, let me go through the problems with addNodeAtFront() function (see comments):

//First, this doesn't need to be a member function, see later for why that is.
template <typename T>
void node<T>::addNodeAtFront(const T& value, node<T> *frontNode){

	node<T> *newNode = new node<T>(value,frontNode);

	// Set the new node to point at the next node
        //--> This will introduce a cycle. Because most likely, in fact most certainly in a linked-list, frontNode will refer back to "this" node if you follow the next pointers, so setting the last node's next pointer to the front node will of course be a cycle.
        // As you said earlier, the next pointer has no reason to change.
	next = frontNode;

	// Set the new node to be the 'front'
        //--> I am surprised your compiler does not say "warning: this line ##: 'frontNode = newNode;' has no effect." (maybe a -Wall is missing or your compiler is stupid)
        // This has no effect because the frontNode pointer is passed by value and thus, changing it has no effect after returning from the function.
	frontNode = newNode;
}
//Since newNode is never "exported" outside the function, it is a memory leak. 
//It should be returned from this function as the new front pointer.
//Conclusion: this function does not need to exist, because the last two lines are useless, and the first line does everything you need. You can wrap it in this function if you want, for clarity, but it is not necessary.

So finally, just by not using this function, your code will work if you do this:

//node.h
#include <iostream>
#include <string>

using namespace std;

template <class T>
class node {
	public:
		T nodeValue;
		node<T> *next;

		// Default constructor
		node(): next(NULL)
		{}

		// Constructor. Initialize nodeValue and next.
		node(const T& item, node<T> *nextNode = NULL):
		nodeValue(item), next(nextNode)
		{}

		// Write your node list
		void writeList(const string& separator);

		virtual ~node() {
                        if(next != NULL)
                                delete next;
                };
};

template <typename T>
void node<T>::writeList(const string& separator){
        cout << nodeValue << separator;
	if(next != NULL)
                next->writeList(separator);
}

//main.cpp
#include <iostream>
#include "node.h"

using namespace std;

int main(){

	node<int> *front = new node<int>(-1);

	for (int i = 0; i < 5; i++)
		front = new node<int>(i,front);

	front->writeList("  ");

        delete front;
        return 0;
}

I guess you can see why people love linked-lists, they are so simple and lightweight. Of course a bidirectional one has a bit more overhead.

Also notice in the above the destruction sequence, it's important not to omit it.

One last note, you shouldn't import a namespace (i.e. "using namespace std;") in a header file, because you don't know where someone else might include the header and then you importing the namespace might cause name-clashes in other peoples code. It is quite alright to import a namespace in a cpp after all include statements, but not in a header. As a rule, after a header file was included, the code environment should come back to the same exact state as it was before the include statement (so no using namespace statements or other things of that flavour).

[figuer25]

ARRGGGGG!!! I just had a long post reply and because I wasnt logged in I lost my post...

anyways in shorter words I get the explinations, it is def simpler and easier to create the nodes from main, I did that before I tried to implement it as a member function. I would like to do it as a member function for practice.

Here are some questions...

so I get rid of that next = frontNode line because in the line above when we create the newNode we pass in frontNode as the second parameter which calls the constructor and assigns frontNode to next so I get that. Now we have this...

template <typename T>
void node<T>::addNodeAtFront(const T& value, node<T> *frontNode){

	node<T> *newNode = new node<T>(value,frontNode);

	frontNode = newNode;
}

can you help me convert this and the prototype so that its passed by reference, that is my problem. I did notice when I was in the member function frontNode actually had a value but it never made its way to main. How do I pass it by reference, do I use the & operator like this...

void node<T>::addNodeAtFront(const T& value, node<T>& frontNode){

or are class pointers treated differently? I tried the node<T>& and I got an error..

no matching function for call to 'node<int>::addNodeAtFront(int&, node<int>*&)'

when running this main...

int main(){

	node<int> *front = NULL, *p = new node<int>;

	for (int i = 0; i < 5; i++)
		p->addNodeAtFront(i,front);

	p->writeList(front,"  ");

	return 0;
}

oh Also why did you initialize front to -1? and about memory management, I was not going to worry about that until I had the other stuff working.

[figuer25]

Hey Mike, I got my answers so I m moving on. I was really curious to try and have a function from main work. I am still curious about how you could pass the value by refenrence though so if you have time see if you can help me with that

Oh and thanks for the advice on the "not including namespaces in header files" that is something I found really usefull, I am now using std:: so that I dont have to include anything and use namespaces.

[mike_2000_17]

>>Also why did you initialize front to -1?
Because that's the value before 0.

>>Pass-by-reference?
Well as the compiler tells you to:

void node<T>::addNodeAtFront(const T& value, node<T>*& frontNode) //notice *&, not just &

glad I could help!

[figuer25]

>>Also why did you initialize front to -1?
Because that's the value before 0.

>>Pass-by-reference?
Well as the compiler tells you to:

void node<T>::addNodeAtFront(const T& value, node<T>*& frontNode) //notice *&, not just &

glad I could help!

whoa I didn't get an email alerting me that you replied. I used the node class to implement a stack, got it working nicely thanks to your help with the node class. Oh and EXCELLENT on the pass by reference, that was not something I would have guessed, that is extremly useful