Linked Lists and Pointers - Page 2
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 2 of 2 FirstFirst 12
Results 16 to 26 of 26

Thread: Linked Lists and Pointers

  1. #16
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,364

    Re: Linked Lists and Pointers

    Close. Your while loop should be

    Code:
    while(curNode){
    as initially, start is NULL so curNode could be NULL.
    Last edited by 2kaud; August 25th, 2013 at 12:53 PM.
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  2. #17
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,364

    Re: Linked Lists and Pointers

    You can, however, simply this code. Note that you are not checking if malloc failed.

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

    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;
    }
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  3. #18
    Join Date
    Jul 2013
    Posts
    30

    Re: Linked Lists and Pointers

    Questions/Clarifications:

    Code:
    while(curNode)
    This is the same as while(curNode != NULL) right?

    Code:
    static struct Node *tail = NULL;
    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).

    And I also did one for delNode(). This time it should delete from the tail of the list:

    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);
    }
    Everything correct in there? I mean, it did work when I ran it, but just making sure.

  4. #19
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,364

    Re: Linked Lists and Pointers

    Code:
    while(curNode)
    This is the same as while(curNode != NULL) right?
    Yes.

    Code:
    static struct Node *tail = NULL;
    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).
    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.
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  5. #20
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,364

    Re: Linked Lists and Pointers

    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.
    Close! 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!

    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.
    Last edited by 2kaud; August 26th, 2013 at 06:27 AM.
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  6. #21
    Join Date
    Jul 2013
    Posts
    30

    Re: Linked Lists and Pointers

    Quote Originally Posted by 2kaud
    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.
    Yup, edited them. Thanks.

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

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

    Also, are any of these not possible?

    Code:
    struct Node{
    	char ACNM[60];
    	struct Node *next;
    } *start;
    
    void cacheData(char a){
         strcpy(a, newNode->ACNM);
         newNode->ACNM = a;
    ... }
    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?
    Last edited by riechan; August 26th, 2013 at 08:28 AM.

  7. #22
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,364

    Re: Linked Lists and Pointers

    Code:
        struct Node{
        	char ACNM[60];
        	struct Node *next;
        } *start;
    
        void cacheData(char a){
             strcpy(a, newNode->ACNM);
             newNode->ACNM = a;
        ... }
    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?
    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 is

    Code:
    struct Node{
    	char ACNM[60];
    	struct Node *next;
    } *start;
    
    void cacheData(const char* a){
         strcpy(newNode->ACNM, a);
    ... }
    which stores the data pointed to by a to the ACNM char array in the newNode node.
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  8. #23
    Join Date
    Jul 2013
    Posts
    30

    Re: Linked Lists and Pointers

    Wait, I tried doing this:

    Code:
    void cacheData(char a[60]){
    ...
    strcpy(newNode->ACNM, a);
    ... }
    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 that

    Code:
    char*
    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.

  9. #24
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,364

    Re: Linked Lists and Pointers

    curNode was initialized as start to have it start traversing the list from the start node, right?
    Yes. curNode now points to the memory address of the beginning of the node that is the first in the linked list.

    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),
    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.

    where we connect the newNode when it is created, to which newNode will be pointed to NULL after being connected, right?
    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.

    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.
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  10. #25
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,364

    Re: Linked Lists and Pointers

    Quote Originally Posted by riechan View Post
    Wait, I tried doing this:

    Code:
    void cacheData(char a[60]){
    ...
    strcpy(newNode->ACNM, a);
    ... }
    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 that

    Code:
    char*
    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.
    I used a type of const char * so that you can pass a string literal to cacheData ie

    Code:
    cachedata("riechan");
    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.

    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*.
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  11. #26
    Join Date
    Jul 2013
    Posts
    30

    Re: Linked Lists and Pointers

    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

Page 2 of 2 FirstFirst 12

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center