Thread: Linked list/Doubly linked list

How would you go about studying for this topic? It's very confusing. I tried reading a book, but I have no idea what its talking about most of the time. I kind of get how single linked lists works, but I'm not quite sure about the coding. As for doubly linked lists, I have no clue.

Code:

#include <iostream>

using namespace std;

struct nodeType
{
	int info;
	nodeType * link;
};

int main()
{
	nodeType * first, * last, *newNode, * current ,*previous;
	first = last = newNode = NULL;

	cout << "///////////////////////////////" << endl;
	cout << "Building a linked list: " << endl;
	cout << "///////////////////////////////" << endl;
	newNode = new nodeType;                                  //create a first node
	newNode -> info = 5;                                     //first node = 5;
	newNode -> link = NULL;                                  //make the first link to NULL first
	cout << "My first node is " <<newNode -> info << endl;   //print the first node = 5
	

	first = last = newNode;                                  //ensure pointer first and last is in first node
                                        
	newNode = new nodeType;                                  //create a second node                                 
	newNode -> info = 15;                                    //second node = 15;
	newNode -> link = NULL;                                  //make the second link to NULL first
	cout << "My second node is " <<newNode -> info << endl;  //print the second node = 15
	last->link = newNode;                                    //link to the second node from the first node
	last = newNode;                                          //set last point to the second node

	newNode = new nodeType;                                  //create the third node
	newNode -> info = 10;                                    //third node = 10;
	newNode -> link = NULL;                                  //make the third link to NULL first
	cout << "My third node is " <<newNode -> info << endl;   //print the third node =1 0
	last->link = newNode;									 //link to the third node from the second node
	last = newNode;

	newNode = new nodeType;                                 //create a fourth node
	newNode -> info = 22;                                   //fourth node = 22;
	newNode -> link = NULL;                                 //make the fourth node link to NULL first
	cout << "My fourth node is " <<newNode -> info << endl; //print the fourth node
	last->link = newNode;
	last = newNode;
	cout << "///////////////////////////////" << endl;
	cout << "End of building a linked list: " << endl;     //end of building a linked list
system ("pause");
}

Some part of the linked list that I had copy paste to here Well, i had create 4 nodes but I did not copy paste all my entire code here and never include insertion deletion or transvering.

Originally Posted by iMalc

You simply wont understand it well at all until you're implemented it yourself.

Start implementing a singly-linked-list. Create a class and write methods for it such as:

Code:

bool IsEmpty();
 void addAtFront(int val);
 void outputList();
 int takeFromFront();
 void addAtBack(int val);
 void insertInOrder(int val);
 void removeFromAnywhere(int val);

Write a couple of pieces of code that uses a few of these each to check that they work.
E.g. call addToFront with 1, 2, and 3 and then call outputList and check that it prints 1 2 3.

Once you have experience with that then you can move onto doubly-linked-lists.

I made the "addAtFront" function, but not sure if I'm doing it right.

This is what I have so far. Can you tell me if I'm going the right direction?

Code:

#ifndef NODE_CLASS
#define NODE_CLASS

using namespace std;
// linked list node

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

      // default constructor with no initial value
      node() : next(NULL)
      {}

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

      template <typename T>
      void addAtFront(node<T> *front, int val)
      {
          node *newNode;
          if(front == NULL)
          {
              newNode = new node<T>(val);
              front = newNode;
          }
          else
          {
              newNode = new node<T>(val, front);
              front = newNode;
          }
      }


};

#endif   // NODE_CLASS

Not sure what I'm doing wrong, but the only error I seem to be getting is:
visual studio 2010\projects\linked list\linked list\d_node.cpp(11): error C3861: 'outputList': identifier not found

Code:

#ifndef NODE_CLASS
#define NODE_CLASS

using namespace std;
// linked list node

template <typename T>
class node
{
   public:
      T nodeValue;  
      node<T> *next;  
     void addAtFront(node<T> *front, int val);
     void outputList(node<T> *front);

      // default constructor with no initial value
      node() : next(NULL)
      {}

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

      template <typename T>
      void node<T>::addAtFront(node<T> *front, int val)
      {
          node *newNode;
          if(front == NULL)
          {
              newNode = new node<T>(val);
              front = newNode;
          }
          else
          {
              newNode = new node<T>(val, front);
              front = newNode;
          }
      }

      template <typename T>
      void node<T>::outputList(node<T> *front)
      {
          node<T> *ptr;
          ptr = front;
          while(ptr != NULL)
          {
              cout << ptr->nodeValue << " ";
              ptr->next = ptr->next;
          }
      }

#endif   // NODE_CLASS

Main:

Code:

 
#include <iostream>
#include "d_node.h"
using namespace std;

int main()
{
    node<int> *head, obj1, obj2;
    head = new node<int>;
    obj1.addAtFront(head, 10);
    obj2.addAtFront(head, 11);
    outputList(head);

    return 0;
}

I changed some things around and I got the output/addAtFront to work with no compile error, but for some reason I keep getting this:


Am I getting that error because I'm forgetting to add something in one of the functions? Here's what the code looks like now.

Code:

#ifndef NODE_CLASS
#define NODE_CLASS

using namespace std;


template <typename T>
class node
{    
   node *head;
   public:
      T nodeValue;  
      node<T> *next;  
     void addAtFront(int val);
     void outputList();

      node() : next(NULL)
      {}

      node(const T& item, node<T> *nextNode = NULL) : 
              nodeValue(item), next(nextNode)
      {}
};

     template <typename T>
     void node<T>::addAtFront(int val)
     {
         node *newNode;
         if(head == NULL)
         {
            head = new node<T>(val);
         }
          else
          {
             newNode = new node<T>(val, head);
             head = newNode;
             
          }
      }

      template <typename T>
      void node<T>::outputList()
      {
          node<T> *ptr;
          ptr = head;
          while(ptr != NULL)
          {
              cout << ptr->nodeValue << " ";
              ptr = ptr->next;
          }
      }

#endif

Main:

Code:

#include <iostream>
#include "d_node.h"
using namespace std;

int main()
{
    node<int> obj;
    obj.addAtFront(9);
    obj.addAtFront(0);
    obj.addAtFront(8);
    obj.addAtFront(7);
    obj.addAtFront(7);
    obj.outputList();

    return 0;
}

Added in the addAtBack function and now it's showing a blank output screen along with the error from above. I can't figure out what I'm doing wrong.

Code:

#ifndef NODE_CLASS
#define NODE_CLASS

using namespace std;

template <typename T>
class node
{    
   node *head;
   public:
     T nodeValue;  
     node<T> *next;  
     void addAtFront(const T val);
     void addAtBack(const T val);
     void outputList() const;

      node() : next(NULL)
      {}

      node(const T& item, node<T> *nextNode = NULL) : 
              nodeValue(item), next(nextNode)
      {}
};

     template <typename T>
     void node<T>::addAtFront(const T val)
     {
         node *newNode;
         if(head == NULL)
         {
            head = new node<T>(val);
         }
          else
          {
             newNode = new node<T>(val, head);
             head = newNode;
          }
      }

      template <typename T>
      void node<T>::addAtBack(const T val2)
      {
         
         if(head == NULL)
             head = new node<T>(val2);
         else 
         {    
            node<T> *bPtr = head;

             while(bPtr->next != NULL)
             {
                 bPtr = bPtr->next;
             }
             bPtr->next = new node<T>(val2);
         }
      }


      template <typename T>
      void node<T>::outputList() const
      {
          node<T> *ptr;
          ptr = head;
          while(ptr != NULL)
          {
              cout << ptr->nodeValue << " ";
              ptr = ptr->next;
          }
      }


#endif

Main:

Code:

#include <iostream>
#include "d_node.h"
using namespace std;

int main()
{
    node<int> obj;
    obj.addAtFront(9);
    obj.addAtFront(0);
    obj.addAtFront(8);
    obj.addAtFront(7);
    obj.addAtFront(7);
    obj.addAtBack(111);
    obj.outputList();
    return 0;
}

Originally Posted by iMalc

The code for the member functions looks good.

The problem looks to be that head is not initialised to NULL. You're also storing a head inside every node. You're almost there with splitting the thing up into a node class and a list class. I'll help you get the rest of the way when I get home tonight.

Should head be declared in public? I'm kinda confused about where to put it.

Originally Posted by Elysia

Are you using Visual Studio? If so, it might be a good time to learn the debugger. It's very simple and will help you a lot. I'd try using it to check for the problem iMalc mentioned. Nothing better than practice.
Also, a double linked list is the same as a linked list - except it goes in both directions - back and forth, while a single linked list only goes forward.

I'm not too familiar with the debugger.

Originally Posted by iMalc

You can do away with 1 and just have a raw pointer to the first node, but then your functions that do the bulk of the work will need to become free functions where you will constantly find yourself needing to pass in the list pointer. Having it as a class allows you to take advantage of constructors and destructors etc.
The hardest part of trying to combine the list and the node into one thing is that no node will know about the nodes that come before it.

<Sorry for a minor Hijack>
I was thinking about how it could be make into one class.
Is is a good design to put the node class in the private section of the list itself...and have the external interface through iterators (...the iterator class residing in the public region and only sugar coating node ) ?