-
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 :D
If anyone can help me Id Appreciate it :D
THanks
-
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;
}
-
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.
-
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.
-
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.
-
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.
-
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. :)
-
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.
-
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.
-
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 .:D Im just going to mess around and start over :D The Class I made is a little messy.
-
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.
-
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
-
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.
-
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.
-
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;