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

Thread: Linked Lists and Pointers

  1. #1
    Join Date
    Jul 2013
    Posts
    30

    Linked Lists and Pointers

    Hi guys, I'm trying to learn how to use Linked Lists. I was wondering if you guys can give me pointers here...

    1. Freeing memory allocation - I don't understand the concept of free() that much. I mean, when exactly do I free a node? For example, in the crtNode() function, I used 2 pointers (newNode, curNode). Do I free() them both after I use them in the function?

    Knowing that I'll be using those two pointers again in the future (when the user inserts another data). Should I free those two pointers right after they are used in the crtNode()? But they're carrying address information right? If I were to free() them, then they'd lose the data they're carrying, right?

    It would be different story with the tmpNode in dspNode(), if I'm not mistaken, since that pointer is only used when the user demands to view the data, so I can free() it after every time the dspNode() finishes displaying all the data in the linked list, right?

    Honestly, in the example given to us, the only part that used free() was delNode(). And it freed a temporarily used pointer.

    2. In the code below, when I tried using the display option, it only displayed one number. I'm pretty sure there's something wrong with my crtNode() function. Like, if I input 2, 3, 4, only the 2 appears.

    Code:
    #include<stdio.h>
    #include<alloc.h>
    
    struct Node{
    	int Data;
    	struct Node *next;
    };
    
    struct Node *start;
    int menu();
    void makNull();
    
    void crtNode(int val){
    	struct Node *newNode, *curNode;
    
    	// Create a new node
    	newNode = (struct Node *)malloc(sizeof(struct Node));
    	
    	newNode->Data = val; //save the data to current Data node
    	newNode->next = NULL; //point the next pointer to NULL
    	
    	if(start == NULL){
    		//Re-initialize the start node to point to first node
    		start = newNode;
    		curNode = newNode;
    	} else {
    		//Set the current node to the newly created node
    		curNode->next = newNode;
    		curNode = newNode;
    	}
    }
    
    void dspNode(){
    	struct Node *tmpNode;
    
    	// get the address of the start node
    	// setting it as the temporary starting node
    	// for displaying purposes only
    	tmpNode = start;
    	
    	while(tmpNode != NULL){
    		printf("%d\n", tmpNode->Data);
    		tmpNode = tmpNode->next;
    	}
    	getch();
    	
    	free(tmpNode);
    }
    
    int main(){
    	int opt, val;
    	start = NULL;
    	clrscr();
    	
    	while(1) {
    		clrscr();
    		opt = menu();
    
    		switch(opt){
    			case 1:
    				printf("Enter data: ");
    				scanf("%d", &val);
    				crtNode(val);
    				break;
    			case 2:
    				//delete
    				break;
    			case 3:
    				dspNode();			
    				break;
    			case 4:
    				exit(0);
    			default:
    				break;
    		}
    	}
    }
    
    int menu(){
    	int x, opt;
    	char *m [] = {"Insert", "Delete", "Display", "Exit"};
    
    	printf("Linked List Sample\n");	
    	for(x=0; x<=3; x++){
    		printf("[%d] %s\n", x+1, m[x]);
    	}
    	
    	printf("\nChoose option: ");
    	scanf("%d", &opt);
    
    	return(opt);
    }

  2. #2
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,389

    Re: Linked Lists and Pointers

    Are you using c?

    1) You don't free a node. You free memory pointed to by a pointer variable. Memory is allocated by using malloc/calloc etc. A pointer variable holds the address of the memory allocated. More than one pointer variable can point to the same memory address. Free is used to free-up memory that is no longer required. Free frees the memory that is pointed to by a pointer variable. Only when memory is no longer required do you use free. Just setting a pointer variable to already allocated memory does not mean that you have to free the memory pointed to by that pointer variable.

    So in your dspNode function, you don't free the memory pointed to by tmpNode before the function returns as you don't want memory freed in a purely display function. Incidentially, in this function, when free is used tmpNode is NULL so in this case free(tmpNode) has no effect.

    In crtNode, you are allocating memory to hold a new node which will be linked into your list. So no memory is freed in this function. The allocated memory should be freed in the deleteNode function when the list is traversed and the allocated memory for each node is freed.

    2) Correct! There are problems with the crtNode function. If start is not NULL, then you are using curMode without first setting curNode to point to what it is supposed to. To add new data at the head of the list as I think you are trying to do, you don't need the variable curNode at all. You always need to set start to the head of the list and if start has already been set, then you just need to set newNode->next to the previous list head.

    When working with lists and nodes, it is a good idea to draw the nodes and links on paper and work out before coding what needs to to be done to add/remove nodes to the list. Once you have the design right for adding/removing nodes etc that works on paper then you can code the algorithm from the design and if it doesn't work then you can debug the code against the design and see where the program deviates from that required.
    Last edited by 2kaud; August 25th, 2013 at 07:24 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.

  3. #3
    Join Date
    Jul 2013
    Posts
    30

    Re: Linked Lists and Pointers

    Quote Originally Posted by 2kaud
    2) Correct! There are problems with the crtNode function. If start is not NULL, then you are using curMode without first setting curNode to point to what it is supposed to. To add new data at the head of the list as I think you are trying to do, you don't need the variable curNode at all. You always need to set start to the head of the list and if start has already been set, then you just need to set newNode->next to the previous list head.
    But I did set start to NULL:

    Code:
    int main(){
    	int opt, val;
    	start = NULL;
    	...
    So, it shouldn't have that problem, right? And, not sure by what you meant by "head", but I'm trying to insert data a la queue style (adding entries at the end), but this is not a queue implementation. I'm just trying out how to make a single linked list in C.

  4. #4
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Posts
    12,097

    Re: Linked Lists and Pointers

    Quote Originally Posted by riechan View Post
    But I did set start to NULL:

    Code:
    int main(){
    	int opt, val;
    	start = NULL;
    	...
    So, it shouldn't have that problem, right? And, not sure by what you meant by "head", but I'm trying to insert data a la queue style (adding entries at the end), but this is not a queue implementation. I'm just trying out how to make a single linked list in C.
    Use the debugger to see what's happening. In crtNode, if start is not NULL, curNode is unitialized.

    In a linked list, "head" refers to the first node.

  5. #5
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Posts
    12,097

    Re: Linked Lists and Pointers

    Quote Originally Posted by 2kaud View Post
    Are you using c?

    1) You don't free a node.
    As a clarification for the OP, you would free a node when you delete the node from the list, or you free the list itself.

  6. #6
    Join Date
    Jul 2013
    Posts
    30

    Re: Linked Lists and Pointers

    I tried using the Debug and Watch in Turbo C (used start and val for the watched values) but it said undefined symbol on both instances. Then I tried using Watch on CodeBlocks but it doesn't look like it's being recognized. (?)

    I simplified the code to this:

    Code:
    void crtNode(int val){
    	struct Node *newNode;
    	newNode = (struct Node *)malloc(sizeof(struct Node));
    	
    	//if origin node
    	if(start == NULL){
    		newNode->Data = val;
    		newNode->next = NULL;
    		start = newNode;
    	}
    }
    But dspNode() still displays just the first entered value.

  7. #7
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Posts
    12,097

    Re: Linked Lists and Pointers

    You should worry about fixing the problems upstream before down. If the list isn't getting created properly, it's not likely it's going to display properly.

    You absolutely need to figure out the debugger before you go any further. Its use is not optional. No decent programmer would attempt to code without one.

  8. #8
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,389

    Re: Linked Lists and Pointers

    Quote Originally Posted by riechan View Post
    But I did set start to NULL:

    Code:
    int main(){
    	int opt, val;
    	start = NULL;
    	...
    So, it shouldn't have that problem, right? And, not sure by what you meant by "head", but I'm trying to insert data a la queue style (adding entries at the end), but this is not a queue implementation. I'm just trying out how to make a single linked list in C.
    I know you initially set start to NULL. That is not what I meant.

    Code:
    if(start == NULL){
    		//Re-initialize the start node to point to first node
    		start = newNode;
    		curNode = newNode;
    	} else {
    		//Set the current node to the newly created node
    		curNode->next = newNode;
    		curNode = newNode;
    	}
    The issue with your code, as I explained, is with the else part of this if statement ie when start is not NULL so you are adding a node to an existing list rather than creating the list for the first time.

    Start points to the head of the linked list and you are trying to add new entries at the start which is like a stack rather than a queue. When you get this code to work, if you traverse the list from start to end you will print out the entries in the reverse order they were entered. ie if you entered 1 2 3 4 then your dspNode will print 4 3 2 1. If you want to display the entries in the list in the order they were entered then you need to insert at the tail rather than the head ie keep a pointer variable pointing to the last entry in the list (the one with next equal NULL).
    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.

  9. #9
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Posts
    12,097

    Re: Linked Lists and Pointers

    Quote Originally Posted by 2kaud View Post
    I know you initially set start to NULL. That is not what I meant.

    Code:
    if(start == NULL){
    		//Re-initialize the start node to point to first node
    		start = newNode;
    		curNode = newNode;
    	} else {
    		//Set the current node to the newly created node
    		curNode->next = newNode;
    		curNode = newNode;
    	}
    The issue with your code, as I explained, is with the else part of this if statement ie when start is not NULL so you are adding a node to an existing list rather than creating the list for the first time.

    Start points to the head of the linked list and you are trying to add new entries at the start which is like a stack rather than a queue. When you get this code to work, if you traverse the list from start to end you will print out the entries in the reverse order they were entered. ie if you entered 1 2 3 4 then your dspNode will print 4 3 2 1. If you want to display the entries in the list in the order they were entered then you need to insert at the tail rather than the head ie keep a pointer variable pointing to the last entry in the list (the one with next equal NULL).
    currNode appears unitialized at that point to me. The compiler issued a warning, and the debugger confirmed it.

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

    Re: Linked Lists and Pointers

    Quote Originally Posted by riechan View Post
    I tried using the Debug and Watch in Turbo C (used start and val for the watched values) but it said undefined symbol on both instances. Then I tried using Watch on CodeBlocks but it doesn't look like it's being recognized. (?)

    I simplified the code to this:

    Code:
    void crtNode(int val){
    	struct Node *newNode;
    	newNode = (struct Node *)malloc(sizeof(struct Node));
    	
    	//if origin node
    	if(start == NULL){
    		newNode->Data = val;
    		newNode->next = NULL;
    		start = newNode;
    	}
    }
    But dspNode() still displays just the first entered value.
    Where is your logic for adding nodes to an existing linked list? Where do you set the next part of the node to point to another node so that dspNode can follow the links from start to end? You need the correct logic for when start is not NULL in this function to link the newly created node to the existing nodes in the linked list.

    As I suggested previously, start with a sheet of paper. Draw blocks for the nodes and link the nodes using lines. Work out the logic required to create the initial list with one node when your paper is blank. Then work out the logic required to add a new node to the paper when there is already one or more nodes linked. When you have the necessary logic to do this then ou can translate that logic into code and then debug the code to make sure it performs as expected. The logic to insert a new node at the head is very simple whether it is a new list or an existing one - just 3 lines of code. As this is an exercise see if you can correct your code from the hints we have given.
    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. #11
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,389

    Re: Linked Lists and Pointers

    Quote Originally Posted by GCDEF View Post
    As a clarification for the OP, you would free a node when you delete the node from the list, or you free the list itself.
    When required, you free the memory associated with the 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.

  12. #12
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Posts
    12,097

    Re: Linked Lists and Pointers

    Quote Originally Posted by 2kaud View Post
    When required, you free the memory associated with the node.
    That's just semantics. I know what you meant, but I thought the wording may be confusing to the OP, that's all.

  13. #13
    Join Date
    Jul 2013
    Posts
    30

    Re: Linked Lists and Pointers

    Wait, sorry, let me see if I got this properly. In this code:

    Code:
    	if(newNode != NULL){
    		newNode->Data = val; //save the data to current Data node	
    		newNode->next = NULL; //point the next pointer to NULL
    We set the input value to a new node and then point the newNode pointer to NULL so that we know that it's the tail of the list, right?

    Code:
    		if(start == NULL){
    			//Set start as origin node
    			start = newNode;
    		} else {
    ..
    We set newNode as the start node, because it's the first entry in the list, right? Technically, an origin node of sorts. If there is an entry in the list, after saving the new input data to newNode->Data and setting the pointer to newNode->next=NULL...

    Code:
    } else {
    start->next = newNode;
    }
    This is wrong though, when I tried this, dspNode() gave just the first and last input. It's supposed to connect to the second node.

  14. #14
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,389

    Re: Linked Lists and Pointers

    This is a suggestion for adding new nodes at the head of the list

    Code:
    void crtNode(int val){
    struct Node	*newNode;
    
    	// Create a new node
    	// If problem allocating memory, just return
    	if ((newNode = (struct Node *)malloc(sizeof(struct Node))) == NULL) {
    		return;
    	}
    	
    	//Add at start
    	newNode->Data = val;
    	newNode->next = start;
    	start = newNode;
    }
    Last edited by 2kaud; August 25th, 2013 at 11:52 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.

  15. #15
    Join Date
    Jul 2013
    Posts
    30

    Re: Linked Lists and Pointers

    @2kaud: Thanks for the hint... I tried doing it like this:

    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
    	curNode = start;
    	while(1){
    		if(curNode->next != NULL){
    			// if last node has not been reached yet,
    			// proceed to next node
    			curNode = curNode->next;
    		} else {
    			// if last node has been reached,
    			// the address will have been saved in curNode
    			break;
    		}
    	}
    
    	// create the node
    	if ((newNode = (struct Node *)malloc(sizeof(struct Node))) == NULL) {
    		printf("Memory allocation failed.");
    		getch();
    		return;
    	}
    
    	newNode->Data = val;
    	newNode->next = NULL;	
    	if(start == NULL){
    		start = newNode; // use new node as origin node
    	} else {
    		curNode->next = newNode; // insert node at the tail
    	}
    }
    Are my explanations correct though? I guess what I really was missing out earlier is the pointer that will traverse the whole list.
    Last edited by riechan; August 25th, 2013 at 12:38 PM.

Page 1 of 2 12 LastLast

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