Like Tree1Likes

Linked list/Doubly linked list

This is a discussion on Linked list/Doubly linked list within the C++ Programming forums, part of the General Programming Boards category; How would you go about studying for this topic? It's very confusing. I tried reading a book, but I have ...

  1. #1
    Registered User
    Join Date
    Oct 2011
    Posts
    13

    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.

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,293
    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.
    King Mir likes this.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Registered User
    Join Date
    Apr 2011
    Posts
    135
    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.

  4. #4
    Registered User
    Join Date
    Oct 2011
    Posts
    13
    Quote Originally Posted by iMalc View Post
    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

  5. #5
    Registered User
    Join Date
    Oct 2011
    Posts
    13
    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;
    }

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,293
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    Registered User
    Join Date
    Oct 2011
    Posts
    13
    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:
    Name:  pBXKd.png
Views: 447
Size:  9.6 KB

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

  8. #8
    Registered User
    Join Date
    Oct 2011
    Posts
    13
    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;
    }

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,293
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  10. #10
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,423
    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 Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  11. #11
    Registered User
    Join Date
    Oct 2011
    Posts
    13
    Quote Originally Posted by iMalc View Post
    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 View Post
    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.

  12. #12
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,423
    Quote Originally Posted by UserName112 View Post
    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?
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  13. #13
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,293
    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;
    };
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  14. #14
    Registered User
    Join Date
    Oct 2011
    Posts
    13
    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.

    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
    Last edited by UserName112; 12-09-2011 at 06:09 PM.

  15. #15
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    Quote Originally Posted by iMalc View Post
    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 ) ?
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help with my doubly linked list
    By evildotaing in forum C++ Programming
    Replies: 3
    Last Post: 11-29-2011, 10:47 AM
  2. doubly linked list
    By BEN10 in forum C Programming
    Replies: 4
    Last Post: 07-21-2009, 09:32 AM
  3. Doubly-Linked List
    By jgs in forum C Programming
    Replies: 7
    Last Post: 04-18-2005, 01:39 PM
  4. singly linked list to doubly linked list
    By t48j in forum C Programming
    Replies: 3
    Last Post: 03-23-2005, 05:37 PM
  5. Doubly Linked List.. please Help!!
    By ProgrammingDlux in forum C++ Programming
    Replies: 8
    Last Post: 10-24-2004, 08:27 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21