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.

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.

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.

Quote:

---

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

---

Wow, you've jumped in there with templates! I was expecting that you'd just start off making a list hardcoded to only ints.
It's easy to make it templated later. But hey if you've got that part down then may as well keep at it.

The main thing I think you need to change is that there are two concepts here that you're sort of combining into one which wont really work.
1. A list itself. A list is typically an object i.e. class or struct with methods for doing things like adding nodes. Most of your code would be in here.
2. A node. This typically doesn't do much, it may have a member function for setting its next node for example, but it isn't the node's job to add other nodes etc.

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.

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:
Attachment 11203

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

---

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.

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.

Quote:

---

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.

Quote:

---

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.

Quote:

---

Originally Posted by UserName112

I'm not too familiar with the debugger.

---

Get familiar! That's all I'm saying.
You will need it in the future. Why wait, when it can make life so much easier?

Okay, here's the main change to split 'list' and 'node' apart:

Code:

---

template <typename T>
class node
{   
        T nodeValue; 
        node<T> *next;
public:
        node() : next(NULL)
        {}

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

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

---

I replaced the code and got an error saying that it could not access "next" because it was a private member. So I tried putting it into the public section and now there's no compile error, but I'm getting the ''Linked list.exe has encountered a problem" error with a blank screen as output.

Quote:

---

Get familiar! That's all I'm saying.
You will need it in the future. Why wait, when it can make life so much easier?

---

Is this a good tutorial to start out with?
http://www.codeproject.com/KB/cs/Mas...Debugging.aspx

Quote:

---

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 ) ?

Putting the node class inside the list class is certainly one option.

Quote:

---

Originally Posted by UserName112

Is this a good tutorial to start out with?
Mastering Debugging in Visual Studio 2010 - A Beginner's Guide - CodeProject

---

Yes, that looks like a good tutorial.

Quote:

---

Originally Posted by UserName112

How would you go about studying for this topic?

---

I read the material here at first: Linked List Problems. When I first studied the topic, this was very helpful. It went very slow and I started to understand pointers a lot better. Then I studied it a second and third time, using other sites. This is another very good read, Eternally Confuzzled - Linked List Tutorial . I still use wikipedia as a reference.

Like other people have said, making a linked list library is the best way to get it, so keep doing what you're doing. My goal when I studied was to build a similar library to the material I was reading, and to understand all the parts of it. Watching things happen in a debugger, or simply testing parts made things very clear.

Making a linked list class library is not really something I'm very interested in doing, though I certainly could now. If I did make it I am sure I would be the only benefactor.