Close. Your while loop should be
as initially, start is NULL so curNode could be NULL.Code:while(curNode){
Printable View
Close. Your while loop should be
as initially, start is NULL so curNode could be NULL.Code:while(curNode){
You can, however, simply this code. Note that you are not checking if malloc failed.
For every new node inserted, you traverse the links each time to find the tail of the linked list. If there are many nodes in the list, this is inefficient. It would be better if you keep a pointer to the tail of the linked list so for insertion you don't need to traverse the list each time. A possible way would beCode:void crtNode(int val){
struct Node *newNode,
*curNode;
// curNode must be initialized at start node
// because it will traverse the whole list
// to find the last node
for (curNode = start; curNode && curNode->next; curNode = curNode->next);
// create the node
newNode = (struct Node *)malloc(sizeof(struct Node));
newNode->Data = val;
newNode->next = NULL;
if (start == NULL) {
// use new node as origin node
start = newNode;
} else {
// Insert node at the tail
curNode->next = newNode;
}
}
Code:void crtNode(int val){
struct Node *newNode;
static struct Node *tail = NULL;
// Create a new node
// If problem allocating memory, just return
if ((newNode = (struct Node *)malloc(sizeof(struct Node))) == NULL) {
return;
}
//Add at end
newNode->next = NULL;
newNode->Data = val;
if (start == NULL){
start = newNode;
} else {
tail->next = newNode;
}
tail = newNode;
}
Questions/Clarifications:
This is the same as while(curNode != NULL) right?Code:while(curNode)
I didn't know that static can be used in C programming. As far as I can remember, the only time I used one was in Java (correct me if I'm wrong though).Code:static struct Node *tail = NULL;
And I also did one for delNode(). This time it should delete from the tail of the list:
Everything correct in there? I mean, it did work when I ran it, but just making sure.Code:void delNode(){
// delete the node at the tail
struct Node *curNode, *prvNode;
curNode = start;
prvNode = start;
// traverse to the tail of the list
while(curNode->next != NULL){
prvNode = curNode;
curNode = curNode->next;
}
if(curNode == start){
start = curNode->next;
} else {
prvNode->next = curNode->next;
}
free(curNode);
}
Yes.Quote:
This is the same as while(curNode != NULL) right?Code:while(curNode)
static is part of both c and c++. When used in a function as a data type modifier, it instructs the compiler to create permanent storage for the local variable that it precedes. This enables the specified variable to maintain its value between function calls. When static is used with global variables, access to them is restricted to the file in which they are declared.Quote:
I didn't know that static can be used in C programming. As far as I can remember, the only time I used one was in Java (correct me if I'm wrong though).Code:static struct Node *tail = NULL;
Close! :D You should check for start being NULL at the beginning of the function and just return if it is because you can't delete from an empty list!Quote:
And I also did one for delNode(). This time it should delete from the tail of the list:
Everything correct in there? I mean, it did work when I ran it, but just making sure.
You have the same performance issue with delNode as you have with crtNode - namely having to traverse to the end of the linked list in order to remove the last node. With large lists, this can be very inefficient - especially if you are deleting many nodes.
There are a possible 2 solutions for this. One is to maintain global tail and tailprev pointers. This makes crtNode slightly more complicated but not much. Both crtNode and delNode can then perform their operations direct at the tail of the linked list without the penalty of list traversal.
The other more complicated solution is to maintain just global head and tail pointers but also store a pointer to the previous node in the node as well as a pointer to the next node. This is called a doubly linked list. This means that you can traverse either backwards or forwards in the list by following either the prev or next pointers. This makes the coding of crtNode and delNode more complicated but also offers more flexibility.
Yup, edited them. Thanks. :)Quote:
Originally Posted by 2kaud
I have a question, this will possibly clear up all of my confusion in the crtNode(), or make it even more confusing for me (hopefully not). Taking your code as an example (and disregarding the tail variable, for the mean time):
curNode was initialized as start to have it start traversing the list from the start node, right? Now, whenever curNode traverses from one node to another, it (somewhat automatically?) connects those nodes to the start node until it reaches the last node (pointing to NULL), where we connect the newNode when it is created, to which newNode will be pointed to NULL after being connected, right? Did I get all that properly?Code:void crtNode(int val){
struct Node *newNode,
*curNode;
// curNode must be initialized at start node
// because it will traverse the whole list
// to find the last node
for (curNode = start; curNode && curNode->next; curNode = curNode->next);
// create the node
newNode = (struct Node *)malloc(sizeof(struct Node));
newNode->Data = val;
newNode->next = NULL;
if (start == NULL) {
// use new node as origin node
start = newNode;
} else {
// Insert node at the tail
curNode->next = newNode;
}
}
Also, are any of these not possible?
I tried using strcpy() and I got a type mismatch. I tried assigning a like how I did it in my previous code (which was an int type), but I got a lvalue error. I'm guessing you can't assign the data just like that to a data node?Code:struct Node{
char ACNM[60];
struct Node *next;
} *start;
void cacheData(char a){
strcpy(a, newNode->ACNM);
newNode->ACNM = a;
... }
a is of type char and can hold 1 character. strcpy(..) requires a type char* (pointer to char) to which to copy characters to. The syntax of strcpy is strcpy(char* to, const char*from) which copies from the memory pointed to by 'from' to the memory pointed to by 'to' all characters upto and including the null terminator. So I think what you actually mean isQuote:
I tried using strcpy() and I got a type mismatch. I tried assigning a like how I did it in my previous code (which was an int type), but I got a lvalue error. I'm guessing you can't assign the data just like that to a data node?Code:struct Node{
char ACNM[60];
struct Node *next;
} *start;
void cacheData(char a){
strcpy(a, newNode->ACNM);
newNode->ACNM = a;
... }
which stores the data pointed to by a to the ACNM char array in the newNode node.Code:struct Node{
char ACNM[60];
struct Node *next;
} *start;
void cacheData(const char* a){
strcpy(newNode->ACNM, a);
... }
Wait, I tried doing this:
I was able to pass the values now, but was that wrong? I see that you used a const modifier for the a parameter. And thatCode:void cacheData(char a[60]){
...
strcpy(newNode->ACNM, a);
... }
means that it's a string, right? Oh, and I always just seem to interchange the strcopy() parameters. It should always be strcopy(destination, source). Geez.Code:char*
Yes. curNode now points to the memory address of the beginning of the node that is the first in the linked list.Quote:
curNode was initialized as start to have it start traversing the list from the start node, right?
Not quite. It doesn't 'connect' the nodes traversed to the start node. To traverse from one node to another, curNode is set to point to the value contained in curNode->next - which is the memory address associated with the beginning of the memory of the next node in the linked list. When this memory address is NULL the end of the linked list has been reached. A node is just a block of memory somewhere in the computers memory whose start address is allocated by the malloc(..) function.Quote:
Now, whenever curNode traverses from one node to another, it (somewhat automatically?) connects those nodes to the start node until it reaches the last node (pointing to NULL),
When the end of the linked list is reached, curNode points to the memory associated with the beginning of the last node in the linked list (if there are any nodes at all in the list ie start is not NULL - if start is NULL then the value of curNode is undefined). If start is NULL (no existing nodes) then start is simply set to newNode (start points to the memory address of the first node in the linked list). If start is not NULL (ie there is already at least 1 node in the linked list) then curNode is valid and points to the last node and has its next element NULL. So to add the new node simply set the value of the next element to the value of the memory address of the beginning of the new node.Quote:
where we connect the newNode when it is created, to which newNode will be pointed to NULL after being connected, right?
Correctly manipulating linked lists is all about understanding pointers and memory usage.
char a; // a is of type character
char *ap; // ap is of type pointer to char ie holds the address of a memory location which can hold a character.
I used a type of const char * so that you can pass a string literal to cacheData ie
is valid. if const is not used then this would not be allowed by the compiler as it would assume that the contents of the memory pointed to by a is modifyable which is not the case with a string literal.Code:cachedata("riechan");
When dealing with passing pointers to char, it is usual to use char* rather than the char[] format. If the contents of memory pointed to by the pointer variable are to be changed, use char *. If the contents are not going to be changed then use const char*.
Thanks, for that very detailed explanation 2kaud! Looks like I have a huge lot to learn about linked lists (among other things). I'll try to digest this for a while :)