Thread: LinkedList Error

  1. #1
    Registered User
    Join Date
    Nov 2004
    Posts
    49

    LinkedList Error

    I'm tring to make my own Linked List, and its not coming along soo Good. I Cant seem to make my AddNode Work all the time.
    Linked List Header
    Code:
    #include <iostream>// Needed for Null 
    #include <string>
    using namespace std;
    
    class Node{
    public:
    
    string Name;
    Node * Next;
    };
    class LinkedList{
    public:
    void AddNode(Node*, int);
    void DisplayName();
    LinkedList();
    ~LinkedList();
    private:
    Node * Start;
    };
    LinkedList::LinkedList(){
    Start=new Node;
    Start->Next=NULL;
    Start->Name="Start";
    }
    LinkedList::~LinkedList(){};
    void LinkedList::AddNode(Node *What, int Where){
    Node *temp=Start;
    if(Where==1&& Start!=What){
        Node *T;
        T=Start;
        Start=What;
        What->Next=T;
    }
    else {
    Node * S;
    for(int i=1;i<Where && temp->Next!=NULL&& Start!=What;temp=temp->Next);
    S=temp->Next;
    temp->Next=What;
    What->Next=S;
    
    }
    }
    void LinkedList::DisplayName(){
    Node *t=Start;
    while(t!=NULL){
    cout<<t->Name<<endl;
    t=t->Next;
    }
    
    }
    Im tring to add a node Before Start. Its not coming along soo hot
    If anyone can help me Id Appreciate it
    THanks

  2. #2
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    I think the basic problem is that your list doesn't have control of the memory of the nodes in the list because you are passing in memory addresses using what. I'd suggest revamping your code a bit, having the list allocate memory when needed, so it can control it.
    Code:
    //I think of lists as empty when created, so Start can be NULL---pointing at nothing.  (If you want Start to be just a placeholder, and not contain any meaningful data, that can be arranged too.)
     
    LinkedList::LinkedList() : Start(NULL) {}
     
    //Always add at the front of the list, before Start.
    void LinkedList::AddNode(Node * what)
    {
      //allocate new memory every time you add a Node to the list.
      Node * newNode = new Node;
     
      //assign the inofrmation stored in what to newNode
      newNode->name = what->name;
     
      //be sure to have the pointer in newNode point to NULL, so the pointer in the last Node of the list will always be NULL--or some other known value if you don't what to use NULL.  
      newNode->Next = NULL;
     
      if(Start == NULL) //empty list
    	Start = newNode;
      else
    	newNode->Next = Start;
    	Start = newNode;
    }

  3. #3
    VA National Guard The Brain's Avatar
    Join Date
    May 2004
    Location
    Manassas, VA USA
    Posts
    903
    If you are keeping head and tail pointers in your class.. you will not need to pass in pointers to your add node/delete node functions. Make them 'void' functions.

    The T variable you are using is typical of a 'Template'.. you are not templating your functions.. so instead of 'T'.. you should explicitly declare your variable types.


    Here are some considerations when designing your list of link:

    • First decide weather you want a singly linked list.. or a doubly linked list. (double-linking is desireable when you want to insert nodes into the middle of a list)
    • Decide how you want to add nodes to the list (head node or tail node insertion)
    • Always keep a head pointer to the beginning of the list and a tail pointer to the end of the list.
    • Keep careful track of pointers that are at the ends of the list point to NULL. This will come in handy when it comes to iteration through your list. (it will help prevent from iterating out of the bounds of the list)
    • Handle the first node you add as a special case... because for this node, you will need to assign a head pointer AND a tail pointer.. and also assign node->next equal to NULL
    • Your "add node" function should handle all aspects of adding a node to the list (including prompting the user to enter data)
    • Only call NEW when adding nodes to a list.. and only call DELETE when deleting nodes from a list.
    • When deleting the head_pointer or tail_pointer node, make sure you re-assign the head/tail pointer using a temporary pointer before you call delete. This will prevent a "dangling pointer"


    Generally speaking... your "add node" and "delete node" functions will be void functions.. because they will just manipulate class member variables.. so there is no need to return a value. Also, unless you are creating pointers in int main( ) then there is no need to pass variables into your "add node" and "delete node" functions... so add_node( ) and delete_node( ) will have empty parameter lists.

    Also, drawing pictures.. and writing out good psuedo code will come in handy when it comes to developing your scheme for creating your linked list.
    Last edited by The Brain; 11-25-2004 at 10:16 AM.
    • "Problem Solving C++, The Object of Programming" -Walter Savitch
    • "Data Structures and Other Objects using C++" -Walter Savitch
    • "Assembly Language for Intel-Based Computers" -Kip Irvine
    • "Programming Windows, 5th edition" -Charles Petzold
    • "Visual C++ MFC Programming by Example" -John E. Swanke
    • "Network Programming Windows" -Jones/Ohlund
    • "Sams Teach Yourself Game Programming in 24 Hours" -Michael Morrison
    • "Mathmatics for 3D Game Programming & Computer Graphics" -Eric Lengyel

  4. #4
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    You can insert/add a node anywhere in the list you want. Inserting at the front of the list or at the end of the list are the most straightforward places to insert, but you can insert anywhere.

    Some people like to have holding nodes for the first and last nodes of the list (see Sedgewick or Liberty). The holding nodes contain no data, but make it possible to keep track of the front an back without having to run the list all the time. However, many other people do not use explicit holding nodes. You always need to keep track of a given node which you can use to access the list. The first node in the list is as good as any to keep track of, and is traditionally the node used. The "next" pointer in the last node of a non circular list can be set to any arbitrary value, which usually NULL. Looking for that arbitrary value allows you to know when you are at the end of the list, if you don't explicitly keep track of the end of the list using a holding node.

    There's nothing wrong with passing the information you want to add/insert to the add/insert function. There's nothing wrong having the add/insert function control the acquisition of the information to add/insert, either. However, I prefer the former approach that functions should do just one thing, so I usually have the add/insert function do the add/insert protocol and pass it the information I want add/inserted. To each their own, however.

  5. #5
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    If I'd use a Linked List I wouldn't want in any way to work with the nodes. The add function should receive the variable to store, and the node would be created and stored internally, and without any interfearence of mine.

  6. #6
    Registered User
    Join Date
    Nov 2004
    Posts
    49
    Thanks for the Advice Everyone. And Happy ThanksGiving. The Whole Link List thing is confusing me. Elad thanks for your advice. Im confused by your code. I Dont know why My Code is faulty. It isnt adding the nodes right. I tried to Draw it out but nothing works. I think Im going to try and redraw it from scratch then look at why it dont work in code later on. Thanks For the advice.

  7. #7
    VA National Guard The Brain's Avatar
    Join Date
    May 2004
    Location
    Manassas, VA USA
    Posts
    903
    It took me a long time to learn linked lists.. they are kind of an abstract data structure.. as compared to something like an array.. As you can see in this post there is more than one way to implement a linked list.

    but i think if you know how to perform pointer assignments.. know how to re-assign pointers.. know how to dereference pointers.. and know how to add and delete nodes.. you'll be ahead of the game.

    I think a good way to learn linked lists.. is to start out very very small. At first.. just try to write a program.. that will add a node.. and then desplay that node.. and then work up from there.
    Last edited by The Brain; 11-25-2004 at 08:46 PM.
    • "Problem Solving C++, The Object of Programming" -Walter Savitch
    • "Data Structures and Other Objects using C++" -Walter Savitch
    • "Assembly Language for Intel-Based Computers" -Kip Irvine
    • "Programming Windows, 5th edition" -Charles Petzold
    • "Visual C++ MFC Programming by Example" -John E. Swanke
    • "Network Programming Windows" -Jones/Ohlund
    • "Sams Teach Yourself Game Programming in 24 Hours" -Michael Morrison
    • "Mathmatics for 3D Game Programming & Computer Graphics" -Eric Lengyel

  8. #8
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    Code:
    if(Where==1&& Start!=What){
    	Node *T;
    	T=Start;
    	Start=What;
    	What->Next=T;
    }
    Let me see if I can put my concerns in written form. I'm not always very good at this, so bear with me. To me the above snippet means try to insert What before Start if Where is 1 and the address stored in What isn't the same as the address stored in Start. To accomplish this you use a local Node pointer called T to temporarily hold the value of Start, then assign the value of What to Start, and the value of T to What->Next (and Start->Next since Start now equals What). But, what if the program changes the value stored at the address in What later in the code? Now you've just changed the value stored at the address in Start as well. Or what if you change the address stored in What later in the program? This will change the address in Start, too. This may or may not be what you intended, but I doubt that it is/would be. Or what if the program releases the memory in What sometime later? Since Start is also pointing to the same memory address that What does, it will also be released, behaviour that is almost certainly not desired. Therefore, I feel it is better to copy the member values stored in What into a new Node so if What is changed later in the program, the data/addresses in the list aren't changed as well. I don't know what type of problems you experienced with your code, so I don't know if this concern is part of the problem or not.

    Likewise, I've not thought through the second part of the function as I had enough concern with the first part to feel that redesign of the function was necessary.

  9. #9
    Registered User manofsteel972's Avatar
    Join Date
    Mar 2004
    Posts
    317
    From what I gather you want to traverse the list to the location where? If the location is the first in the list then insert the node at the head if the location is 4 then you traverse 4 nodes and insert it there. If that is true then you need 3 tests one for insert at head of list one for insert in middle and one for insert at tail of list.

    To insert at the head of list you take the node you passed in and assign its next pointer to the head of the list and then assign the head pointer to equal the inserted node
    so
    Code:
    what->next=Start; 
     
    and then 
     
    Start=what;

    That would add the node to the start of the list and make it the 1st node; You shouldn't really need a temp variable.
    Last edited by manofsteel972; 11-26-2004 at 04:33 AM.
    "Knowledge is proud that she knows so much; Wisdom is humble that she knows no more."
    -- Cowper

    Operating Systems=Slackware Linux 9.1,Windows 98/Xp
    Compilers=gcc 3.2.3, Visual C++ 6.0, DevC++(Mingw)

    You may teach a person from now until doom's day, but that person will only know what he learns himself.

    Now I know what doesn't work.

    A problem is understood by solving it, not by pondering it.

    For a bit of humor check out xkcd web comic http://xkcd.com/235/

  10. #10
    Registered User
    Join Date
    Nov 2004
    Posts
    49
    Thanks for the Help Elad and ManOfSteel and all. I Tried what you said before ManofSteel. I get an infinite loop from display function when you Add the same node to the same place. It causes it to point to itself. Or Something. I Need to Take a Break, though. All this tring to learn Linked Lists and how simple the answers are and How I cant figure the answers out. Kinda wears me out LOL . Im just going to mess around and start over The Class I made is a little messy.

  11. #11
    Registered User manofsteel972's Avatar
    Join Date
    Mar 2004
    Posts
    317
    Well you are creating a new node for each item your adding aren't you? or are you just changing the same node and then adding it again. If your doing the latter that is why your are looping indefinitely.

    Code:
    	LinkedList mylist;
     
    	Node node;
    	node.Name="Henry";
     
    	mylist.AddNode(&node,1);
    	Node node2;
    	node2.Name="Charlie";
    	mylist.AddNode(&node2,1);
    	Node node3;
    	node3.Name="Betty";
     
    	mylist.AddNode(&node3,1);
    	Node node4;
    	node4.Name="frank";
    	mylist.AddNode(&node4,1);
    	mylist.DisplayName();
    If you don't want to create a new node each time before you add it you could add code to your AddNode() member function to do it internally (probably preferred). That is basically what Elad was referring to. If you create the nodes outside your list then if or when you modify them outside of the list, it would change the list as well.

    Code:
    	LinkedList mylist;
     
    	Node node;
    	node.Name="Henry";
    	mylist.AddNode(&node,1); 
    	mylist.DisplayName();
    	node.Name="Betty";
    	mylist.DisplayName();// will display Name Betty as first node instead of Henry
    I can see why you might want to pass a node if you have two lists and you want to transfer one node from one list to another. The nodes have already been created internally and you are just removing it from one list and inserting it into the other.
    Last edited by manofsteel972; 11-28-2004 at 01:47 AM.
    "Knowledge is proud that she knows so much; Wisdom is humble that she knows no more."
    -- Cowper

    Operating Systems=Slackware Linux 9.1,Windows 98/Xp
    Compilers=gcc 3.2.3, Visual C++ 6.0, DevC++(Mingw)

    You may teach a person from now until doom's day, but that person will only know what he learns himself.

    Now I know what doesn't work.

    A problem is understood by solving it, not by pondering it.

    For a bit of humor check out xkcd web comic http://xkcd.com/235/

  12. #12
    Registered User
    Join Date
    Nov 2004
    Posts
    49
    THanks Steal of the Man. The Problem I think Was. I was tring to change the pointer of one of the elements in the list to point to another position. and it was already pointing somewhere. So when I start switching the pointers around they get all pointing to wrong spots and the One that use to point to Null Dont point there anymore. And I notice a lot of problems happen when you try to change a Nodes spot in the list. I wasnt creating new nodes each time with the same name. I was just trying to change the nodes Positions I cant seem to do that. It gives me soo many eerrors. if It wasnt for that I think my linked list would work fine. Do you need the &node? When you pass the pointer. I thought you can just pass a pointer with the name and not the & of operator.
    Take Care

  13. #13
    Registered User manofsteel972's Avatar
    Join Date
    Mar 2004
    Posts
    317
    I was creating node objects not node pointers.
    Code:
    Node newnode; //<---creates a node object; it isn't a pointer so I have to pass the address or create a pointer and assign it the address of the node object.
     
    Node* pointer_to_node; //<--doesn't create a node just a pointer to a node object; 
     
    i can create a new node dynamically by using the pointer_to_node;
     
    pointer_to_node= new Node;//<---dynamically creates a node object and initializes pointer_to_node with its address.
    When i used the above code your list added the nodes i made no changes to your code. I don't know how you are creating the nodes that you pass to your class but if you create them dynamically then all you need to do is pass the pointer if you are creating actual objects then you would need to pass the address of the object. You might want to consider a CreateNode member function.

    [edit]
    Little confused? Are you trying to add nodes to the list or do you want to swap nodes already in the list?

    Code:
    same example as above except I am using dynamically allocated nodes
     
    LinkedList mylist;
    Node* node;
    node=new Node;
    node->Name="Frankl";
    node->Next=0;
    mylist.AddNode(node,1);
    node=new Node;
    node->Name="julie";
    node->Next=0;
    mylist.AddNode(node,1);
    mylist.DisplayName();
    //etc etc usually this allocation is done inside the class function as in Elads example.
    Last edited by manofsteel972; 11-28-2004 at 08:21 AM.
    "Knowledge is proud that she knows so much; Wisdom is humble that she knows no more."
    -- Cowper

    Operating Systems=Slackware Linux 9.1,Windows 98/Xp
    Compilers=gcc 3.2.3, Visual C++ 6.0, DevC++(Mingw)

    You may teach a person from now until doom's day, but that person will only know what he learns himself.

    Now I know what doesn't work.

    A problem is understood by solving it, not by pondering it.

    For a bit of humor check out xkcd web comic http://xkcd.com/235/

  14. #14
    Registered User
    Join Date
    Nov 2004
    Posts
    49
    I want to add the nodes to the list that I created and I want to swap them around different places as well. IF I change my mind on the place I want them later on.

  15. #15
    Registered User manofsteel972's Avatar
    Join Date
    Mar 2004
    Posts
    317
    you have to take into account where you are in the list. when you add your node.
    Code:
    if at the head of the list
    node->Next=Start; //make your added node point to start of list
    Start=node; // make the start pointer equal to your added node;
     
    if in middle
    nextnode=temp->Next; // save the pointer to the next node;
    temp->next=node; //change it to point to your added node;
    node->next=nextnode; //now make the added node point to the next node;
     
    if at the end
    temp->next=node; //make last node point to the node your adding
    node->next=NULL; //make the node your adding point to null;
    Last edited by manofsteel972; 11-28-2004 at 06:41 AM.
    "Knowledge is proud that she knows so much; Wisdom is humble that she knows no more."
    -- Cowper

    Operating Systems=Slackware Linux 9.1,Windows 98/Xp
    Compilers=gcc 3.2.3, Visual C++ 6.0, DevC++(Mingw)

    You may teach a person from now until doom's day, but that person will only know what he learns himself.

    Now I know what doesn't work.

    A problem is understood by solving it, not by pondering it.

    For a bit of humor check out xkcd web comic http://xkcd.com/235/

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Getting an error with OpenGL: collect2: ld returned 1 exit status
    By Lorgon Jortle in forum C++ Programming
    Replies: 6
    Last Post: 05-08-2009, 08:18 PM
  2. An error is driving me nuts!
    By ulillillia in forum C Programming
    Replies: 5
    Last Post: 04-04-2009, 09:15 PM
  3. Making C DLL using MSVC++ 2005
    By chico1st in forum C Programming
    Replies: 26
    Last Post: 05-28-2008, 01:17 PM
  4. Connecting to a mysql server and querying problem
    By Diod in forum C++ Programming
    Replies: 8
    Last Post: 02-13-2006, 10:33 AM
  5. Couple C questions :)
    By Divx in forum C Programming
    Replies: 5
    Last Post: 01-28-2003, 01:10 AM