Help with my doubly linked list

[Volatile Pulse]

My code so far:

   template<class T> class list {
      private:
         struct node {
            T value;
            node *next;
            node *prev;
         };
         node *firstNode;
         node *lastNode;
      public:
         /** list constructor **/
         list() : firstNode(NULL), lastNode(NULL) {}

         /** list deconstructor **/
         ~list() {
            /** while firstNode isn't NULL **/
            while (firstNode != NULL) {
               /** create new node at firstNode's "next" node **/
               node *n = firstNode->next;
               /** delete firstNode **/
               delete firstNode;
               /** reassign firstNode to the "next" node **/
               firstNode = n;
            }
         }
         void push_back(T x) {
            /** create new node **/
            node * n = new node;
            /** set value equal to x **/
            n->value = x;
            /** point to the prev node **/
            n->prev = lastNode;
            /** make the last node the new node **/
            lastNode->next = n;
            lastNode = n;
            if(!firstNode)
               firstNode = n;
         }
         void display() {
            /** create new node to display **/
            node displayNode = *firstNode;
            std::cout << displayNode.value;
         }
   };

I keep getting process terminated and I have a feeling it has something to do with how I'm assigning my next/prev nodes.

On a side note, I get a few warnings I'm unsure about when compiling. They are:

MinGW wrote:

C:\Programming\List Practice\main.cpp||In instantiation of 'class vp::list<int>':|
C:\Programming\List Practice\main.cpp|52|required from here|
C:\Programming\List Practice\main.cpp|5|warning: 'class vp::list<int>' has pointer data members [-Weffc++]|
C:\Programming\List Practice\main.cpp|5|warning: but does not override 'vp::list<int>(const vp::list<int>&)' [-Weffc++]|
C:\Programming\List Practice\main.cpp|5|warning: or 'operator=(const vp::list<int>&)' [-Weffc++]|
||=== Build finished: 0 errors, 5 warnings (0 minutes, 16 seconds) ===|

[Peter87]

/** make the last node the new node **/
lastNode->next = n;

What if lastNode is null?



The display() function will not work if the list is empty.



The warnings warn you that you have not implemented the copy assignment operator and the copy constructor. This will be a problem if you try to copy the list because the predefined copy assignment operator and copy constructor will not handle the copying correctly in this case because it will just copy the two pointer members.

[Volatile Pulse]

I'm not really worried about the copy constructor since it's only a sample exercise, and it's much easier than what I thought to do this. My issue was I wasn't thinking about the first node to be added, but how the other nodes got added. Here is the code so far (still working on pop_back()):

   template<class T> class list {
      private:
         struct node {
            T value;
            node *next;
            node *prev;
         };
         node *firstNode;
         node *lastNode;
      public:
         /** list constructor **/
         list() : firstNode(NULL), lastNode(NULL) {}

         /** list deconstructor **/
         ~list() {
            /** while firstNode isn't NULL **/
            while (firstNode != NULL) {
               /** create new node at firstNode's "next" node **/
               node *n = firstNode->next;
               /** delete firstNode **/
               delete firstNode;
               /** reassign firstNode to the "next" node **/
               firstNode = n;
            }
         }
         void push_back(T x) {
            /** create new node **/
            node *n = new node;
            /** set value equal to x **/
            n->value = x;
            /** since this is the end node there isn't a next node **/
            n->next = NULL;
            /** point to the prev node **/
            n->prev = ((lastNode) ? lastNode : NULL);
            /** if this isn't the first node **/
            if (lastNode)
               /** set the last node's next equal to this one **/
               lastNode->next = n;
            /** make the last node the new node **/
            lastNode = n;
            /** if fisrt node doesn't exist **/
            if (!firstNode)
               /** point to n **/
               firstNode = n;
         }
         T pop_back() {
            /** create a node equal to the last node **/
            if (lastNode)
               node *n = lastNode;
            /** set value equal to x **/
            n->value = x;
            /** since this is the end node there isn't a next node **/
            n->next = NULL;
            /** point to the prev node **/
            n->prev = ((lastNode) ? lastNode : NULL);
            /** if this isn't the first node **/
            if (lastNode)
               /** set the last node's next equal to this one **/
               lastNode->next = n;
            /** make the last node the new node **/
            lastNode = n;
            /** if fisrt node doesn't exist **/
            if (!firstNode)
               /** point to n **/
               firstNode = n;
         }
         void display() {
               /** create new node to display **/
            if (firstNode) {
               node *displayNode = firstNode;
               do {
                  std::cout << displayNode->value << "\n";
               } while ((displayNode = displayNode->next) != NULL);
            }
            else
               std::cout << "list is empty\n";
         }
   };

[HiteshVaghani1]

i think you are doing problem is in the pop_back(). i try to trace it in notebook please try to trace it. when we are doing pop_back(), we just need to do,

lastnode = lastnode->prev
lastode->next = NULL;

i am not including other stuff here..
sorry if i am wrong at any point.

[Volatile Pulse]

This is what I came up with for pop_back():

         T pop_back() {
            if (!lastNode)
               return NULL;
            /** create a node equal to the 2nd to last node **/
            node *n = lastNode->prev;
            /** next should point to NULL **/
            n->next = NULL;
            /** create a variable equal to the value of the last node **/
            T value = lastNode->value;
            /** delete last node **/
            delete lastNode;
            /** assign last node to the new last node **/
            lastNode = n;
            /** return the value **/
            return value;
         }

The only issue I run across is when I pop_back the last item, I get a runtime error. I know it has something to do with node *n = lastNode->prev; since there is a time when it will point to the previous node, which would be NULL, but I'm not quite sure how to program that correctly.

Also, any tips on improving the list?

[naraku9333]

Your pop_back function will dereference a null pointer when last->prev is null (you dont check for it) tested with this

int main()
 {
	 list<int> l;

	 for(int i = 1; i <= 10; ++i)
		 l.push_back(i);

	 int x;
	 while((x = l.pop_back()) != NULL)
		 std::cout<<x<<"\t";
	// l.display();
	 return 0;
}

I fixed the function, I'll post it if you'd like but I thought I'd give you a chance first if you haven't already fixed it.

[Volatile Pulse]

This is what I've come up with so far for the entire list:

#include <iostream>
#include <list>

namespace vp {
   template<class T> class list {
      private:
         struct node {
            T value;
            node *next;
            node *prev;
         };
         node *firstNode;
         node *lastNode;
         unsigned int mSize;
      public:
         /** list constructor **/
         list() : firstNode(NULL), lastNode(NULL), mSize(0) {}

         /** list deconstructor **/
         ~list() {
            /** while firstNode isn't NULL **/
            while (firstNode != NULL) {
               /** create new node at firstNode's "next" node **/
               node *n = firstNode->next;
               /** delete firstNode **/
               delete firstNode;
               /** reassign firstNode to the "next" node **/
               firstNode = n;
            }
         }
         unsigned int size() {
            return mSize;
         }
         void push_back(T x) {
            /** create new node **/
            node *n = new node;
            /** set value equal to x **/
            n->value = x;
            /** since this is the end node there isn't a next node **/
            n->next = NULL;
            /** point to the prev node **/
            n->prev = ((lastNode) ? lastNode : NULL);
            /** if this isn't the first node **/
            if (lastNode)
               /** set the last node's next equal to this one **/
               lastNode->next = n;
            /** make the last node the new node **/
            lastNode = n;
            /** if first node doesn't exist **/
            if (!firstNode)
               /** point to n **/
               firstNode = n;
            mSize ++;
         }
         void push_front(T x) {
            /** create new node **/
            node *n = new node;
            /** set value equal to x **/
            n->value = x;
            /** point to the next node **/
            n->next = ((firstNode) ? firstNode : NULL);
            /** since this is the first node there isn't a prev node **/
            n->prev = NULL;
            /** if this isn't the first node **/
            if (firstNode)
               /** set the first node's prev equal to this one **/
               firstNode->prev = n;
            /** make the first node the new node **/
            firstNode = n;
            /** if last node doesn't exist **/
            if (!lastNode)
               /** point to n **/
               lastNode = n;
            mSize ++;
         }
         T pop_back() {
            /** make sure there is something to pop back **/
            if (!size())
               return NULL;
            /** if popping back the last element in the list **/
            if (size() == 1) {
               /** we only need the value **/
               T value = lastNode->value;
               /** delete the node **/
               delete lastNode;
               /** set them equal to NULL again **/
               lastNode = firstNode = NULL;
               /** reduce the size **/
               mSize --;
               /** return the value **/
               return value;
            }

            /** create a node equal to the 2nd to last node **/
            node *n = lastNode->prev;
            /** next should point to NULL **/
            n->next = NULL;
            /** create a variable equal to the value of the last node **/
            T value = lastNode->value;
            /** delete last node **/
            delete lastNode;
            /** assign last node to the new last node **/
            lastNode = n;
            /** reduce the size **/
            mSize --;
            /** return the value **/
            return value;
         }
         T pop_front() {
            /** make sure there is something to pop front **/
            if (!size())
               return NULL;
            /** if popping front the last element in the list **/
            if (size() == 1) {
               /** we only need the value **/
               T value = firstNode->value;
               /** delete the node **/
               delete firstNode;
               /** set them equal to NULL again **/
               firstNode = lastNode = NULL;
               /** reduce the size **/
               mSize --;
               /** return the value **/
               return value;
            }

            /** create a node equal to the 2nd node **/
            node *n = firstNode->next;
            /** prev should point to NULL **/
            n->prev = NULL;
            /** create a variable equal to the value of the first node **/
            T value = firstNode->value;
            /** delete first node **/
            delete firstNode;
            /** assign first node to the new first node **/
            firstNode = n;
            /** reduce the size **/
            mSize --;
            /** return the value **/
            return value;
         }
         void display() {
            /** make sure nodes exists **/
            if (size()) {
               /** create new node to display **/
               node *displayNode = firstNode;
               /** loop through the list **/
               for (unsigned int i = 0; i < size(); i ++) {
                  /** display each node **/
                  std::cout << displayNode->value << " ";
                  /** get the next node **/
                  displayNode = displayNode->next;
               }
            }
            else
               std::cout << "list is empty\n";
            std::cout << "\n";
         }
   };
}

int main() {
   vp::list<int> myList;
   myList.push_back(5);
   myList.display();
   myList.push_back(6);
   myList.display();
   myList.push_back(5);
   myList.display();
   myList.push_back(7);
   myList.display();
   for (unsigned int i = 0; i < myList.size(); i ++) {
      myList.push_front(myList.pop_back());
      myList.display();
   }
   for (unsigned int i = 0; i < myList.size(); i ++) {
      myList.push_back(myList.pop_front());
      myList.display();
   }
   myList.pop_back();
   myList.pop_front();
   myList.display();
   myList.pop_back();
   myList.pop_front();
   myList.display();
   myList.pop_back();
   myList.pop_front();
   myList.display();
}

I use a lot of comments simply because I might forget something when I come back. I've also gotten into the habit of commenting every line because what might seem obvious to me might not be obvious to someone else. Anyways, can you see anything wrong with the actual code? It seems to run perfectly fine for me, no more crashes, freezes, or memory leaks that I can tell.

What improvements can I work on? What else should I implement?

[naraku9333]

Looks good, maybe add an iterator class?
Edit: You could also add a copy ctor and operator= overload.

[Volatile Pulse]

I honestly have no idea where to even begin with that. I thought about doing the begin() and end() functions, but I know they need to return an iterator and I don't know what an iterator even looks like to be honest =(

[firedraco]

Your pop_front and back won't work if NULL is not convertible to T. Just throw an exception.

[naraku9333]

The begin and end functions can return firstNode and lastNode respectively. Then overload operator++ to increment the pointer to the next node.

[Volatile Pulse]

Ok, I've come up with this so far:

            node *operator ++() {
               if (this->next != NULL)
                  this = this->next;
               else
                  this = NULL;
               return this;
            }
            node *operator --() {
               if (this->prev != NULL)
                  this = this->prev;
               else
                  this = NULL;
               return this;
            }
            T operator *() {
               if (this == NULL)
                  return NULL;
               return this->value;
            }

And:

   auto firstNode = myList.begin();
   std::cout << firstNode->value << "\n\n";

A few things, I believe the increment and decrement operators are working correctly. I, however, haven't been able to get the reference operator working correctly. What am I doing wrong there? Also, what type does auto become? I thought node was private so nothing would be able to be of type node...

@firedraco
I'm just trying to learn how the list works right now. I have always tried to stay away from exceptions, but I will find a proper way once I can get my list to where I'm happy with it.

[naraku9333]

I believe auto should become a node* assuming that is what begin returns. The de-reference operator should return a pointer to the node. heres an example added to your class.

...
node *firstNode;
         node *lastNode;
         unsigned int mSize;
      public:
		   class iterator
		   {
		   public:
			  iterator operator=(node* n){this->current = n; return *this;}
			  void operator++()
			  {
				  if(current)
					  current = current->next;
			  }
			  node* operator->()
			  {
				  return current;
			  }
			  bool operator!=(node* n){return current != n;}
		  private:
			  node* current;
		  };
		  

		  node* begin(){return firstNode;}
		  node* end(){return lastNode->next;}

         /** list constructor **/
         list() : firstNode(NULL), lastNode(NULL), mSize(0) {}
...

then tested (somewhat) with

vp::list<int>::iterator myIt;

   for(myIt = myList.begin(); myIt != myList.end(); myIt++)
	   std::cout<<myIt->value<<"\t";

[Volatile Pulse]

Alright, I implemented your code, and I'm not quite sure what went wrong, but doing it just as you had it, this code should work perfectly:

int main() {
   vp::list<int> myList;
   myList.push_back(5);
   myList.push_back(6);
   myList.push_back(5);
   myList.push_back(7);
   for (auto iter : myList)
      std::cout << "Node: " << *iter << "\tValue: " << iter.value << "\n";
}

However, the first thing I notice is that I can't just display iter, I need to dereference it. I didn't believe this to be the case with other iterators. My second thing I noticed is the output, as seen below. Something doesn't seem right, most likely in the ++ function. The only reason I was able to get this correctly was because I removed the ->next from the end() function. I would get an infinite loop and then the program would crash, which I guess was due to an access violation.

Node: 5 Value: 5
Node: 6841185   Value: 6841185
Node: 6 Value: 6
Node: 1163154768        Value: 1163154768
Node: 5 Value: 5
Node: 842879826 Value: 842879826

Obviously my list is slowly coming together (which makes me happy) but I am soon going to have to sit down and write this all out on paper again so I can completely understand everything that's going on.

Edit: Maybe I should have asked this as well, but what is lastNode->next supposed to equal? Currently, the lastNode->next points to a NULL node...but if that was the case, couldn't I just return NULL instead?

[naraku9333]

My guess is you cant use the for each syntax because you need to explicitly set the iterator to the first element(such as begin does).

[Volatile Pulse]

Read from here:http://en.wikipedia.org/wiki/C%2B%2B0x#Range-based_for-loop

Wikipedia wrote:

It will work for C-style arrays, initializer lists, and any type that has begin() and end() functions defined for it that return iterators.

I was trying to follow the tutorial on cprogramming, but his code looks a lot different than mine. I might have to take a gander at what I can come up with. I know I'll never recreate the std::list, but it's a lot of fun seeing how this is done in the "real" world.

Also, I will have to write this out by hand sooner than I thought. Can you give me some requirements of a list (possible things I might need to change when I run across them) like should lastNode->next = NULL and firstNode->prev = NULL and should they both equal NULL when there is nothing in the list?

[naraku9333]

Some fixes

class iterator
		   {
		   public:
			   iterator(node* n){current = n;}
			   iterator operator=(iterator n){this->current = n->current; return *this;}
			  void operator++()
			  {
				  if(current)
					  current = current->next;
			  }
			  node* operator->()
			  {
				  return current;
			  }
			  node* operator*()
			  {
				  return current;
			  }
			  bool operator!=(iterator n){return current != n.current;}
		  private:
			  node* current;
		  };
		  

		  iterator begin(){return iterator(firstNode);}
		  iterator end(){return iterator(lastNode->next);}
...
for (auto iter : myList)
	   std::cout << "Node: " << iter << "\tValue: " << iter->value << "\n";

[Volatile Pulse]

I'm incredibly happy. It took me about 20 minutes or so to track down a minor bug. Everything seemed to be working perfectly, but the program would keep hanging. I accidentally commented out a line in the destructor that prevented the list from being destroyed. After fixing it, I started reading through all of the lines that are there, but my brain has been shutting down for the last three hours.

I appreciate the help, and I'm going to try to tackle this entire thing before work. I guess something else that I can look forward to is the insert function.

(I actually want to attempt this one by myself, but if you have any pointers, they're more than welcome.)