C++

Forum

 
Pointers and linked lists

riechan (48)
Hi guys! I'm trying to learn about linked lists and pointers and I'm kind of confused right now. In the code below

1
2
3
4
 
	// *ptr points to val node?
	ptr->val = val;
	// *next points to NULL?
	ptr->next = NULL;


Did I get the comment/explanation right of how I understood the concept? Also, can you guys help explain to me how this pointer concept works in sort of layman words (and possibly with a diagram of sorts)? Sorry if I'm asking for too much, but I'd really like to get a much more "basic" explanation. I mean, I'm using this:

http://www.thegeekstuff.com/2012/08/c-linked-list-example/

as a resource, but it would be nice if someone could illustrate it to a more basic level. I'd really appreciate if anyone of you guys do!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
#include<stdio.h>

struct ts{
	int val; // contains the value
	struct ts *next; // pointer to the next node, must connect to a structure of the same type
}

int main(){
	// create a new node
	// *ptr contains the address of the new node
	struct ts *ptr = (struct ts*)malloc(sizeof(struct ts));
	
	// *ptr points to val node?
	ptr->val = val;
	// *next points to NULL?
	ptr->next = NULL;

	return 0;
}
LB (13399)
On line 14, val doesn't exist in that scope, so the code doesn't even compile.

Also, are you trying to learn C or C++? Because it looks like you're trying to learn C.
Smac89 (1727)
There should be a semicolon after the declaration of struct ts on line 6.
riechan (48)
@Smac89: fixed!

@L B: Wait, don't the variables inside the ts structure work "globally"?

On line 14, val doesn't exist in that scope, so the code doesn't even compile.

Also, are you trying to learn C or C++? Because it looks like you're trying to learn C.
riechan (48)
Wait, sorry, in this code:

1
2
3
4
5
6
 
struct node {
      int data;
      struct node *next;
}*start = NULL;

struct node *new_node,*current;


*start = NULL; - Declared a global variable of type node. “start” is used to refer the starting node of the linked list.

^ because *start is equals to NULL value, right?

start->next - Access the 2nd Node of the linked list. This term contain the address of 2nd node in the linked list. If 2nd node is not present then it will return NULL.

^ I'm confused. When we created the structure of node, was next already pointing to a second node? Or are we simply connecting the start node to a next node, which is technically NULL? So does this mean that *next is also a node, and not a pointer? I thought pointers just pointed (contained the address) to another node??

start->data - It will access “data” field of starting node.

^ It accessed the data field because it's not a type node (and it's an int type), right?

start->next->data - It will access the “data” field of 2nd node.

^ So, from the start node, it will access the data of the second node because the next node is connected to the second node?

current = start->next - Variable “current” will contain the address of 2nd node of the linked list.

^ sort of understood this because of the start->next statement up there. current should now contain an address as specified by start->next.

start = start->next; - After the execution of this statement, 2nd node of the linked list will be called as “starting node” of the linked list.

^ So, technically, start became the "starting node" because we initialized it's value to NULL, and for easy tracking/debugging purposes, we called it start, right? But, I have a question, when the program is first run (and node is created for the first time), where does *next point to and what is its value?

1
2
3
4
 
struct node {
      int data;
      struct node *next;
}*start = NULL;


Using this resource, btw:
http://c4learn.com/tutorials/data-structure/linked-list/terms-used-in-linked-list-concept/
LB (13399)
riechan wrote:
*start = NULL; - Declared a global variable of type node. “start” is used to refer the starting node of the linked list.

^ because *start is equals to NULL value, right?

start->next - Access the 2nd Node of the linked list. This term contain the address of 2nd node in the linked list. If 2nd node is not present then it will return NULL.
If start is null, then it is unsafe to dereference it with either *start or start->
riechan (48)
L B wrote:
If start is null, then it is unsafe to dereference it with either *start or start->


So you mean to say that the *start = NULL in line 4 is not a good thing to do, and it should've been like this instead?

1
2
3
 
struct node{
..
} *start;
Last edited on
LB (13399)
No, that's even worse - now instead of a null pointer which you can detect and deal with, you now have an uninitialized variable. That pointer could contain any random address and you would never be able to tell that it wasn't safe to dereference.

I think the idea you're missing is that you need to initialize data for that pointer to point to.

Also, you still haven't answered - do you want to learn C or C++? This is a very important distinction.
Last edited on
riechan (48)
I'm doing this in C. I was wondering, with the example that was given to us, *start was initialized as NULL in main(). Is that a much better course of action, instead of initializing it right away in the struct declaration?

1
2
3
4
 
int main(){
...
*start = NULL;
... }
cire (8284)
I'm doing this in C. I was wondering, with the example that was given to us, *start was initialized as NULL in main(). Is that a much better course of action, instead of initializing it right away in the struct declaration?


start should not exist in the global namespace, so yes, defining and initializing it in main should be preferred. Avoid the use of global variables.
riechan (48)
Okay, so I did this thing:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
#include<stdio.h>
#include<alloc.h>

struct Node{
	int x;
	struct Node *next;
};

struct Node *start;

void createNode(){
	char ch;
	struct Node *newNode, *curNode;

	// Create a new node
	newNode = (struct Node *)malloc(sizeof(struct Node));
	
	do {
		printf("Enter data: ");
		scanf("%d", &newNode->x); //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;
		}
		
		printf("Add more? ");
		ch = getche();
	} while(ch != 'n');
}

int main(){
	start = NULL;
	clrscr();

	createNode();
	
	return 0;
}


Is any part of the code wrong? Which ones should I correct to follow a certain standard? This is just for creating new nodes, btw.

EDIT: I have a question, in line 29-30,

1
2
 
curNode->next = NULL;
curNode = newNode;


I understand that we're setting the current node to the newly created node, but what happens to the curNode->next pointer (line 28) after curNode = newNode (line 29)? Does it point to a NULL value after we set the curNode to newNode in line 29?
Last edited on
Daleth (1030)
Try keeping your variables scoped in a function. If you need them in some other function, just pass them.
1
2
3
4
 
int main(){
   struct Node* start = NULL;
   createNode(start);
}


I'm a little confused on why you're doing what you're doing in your createNode function. Couldn't you just do something like:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
struct Node* createNode(){
   struct Node* toreturn = (struct Node*)malloc(sizeof(struct Node));
   toreturn->next = NULL;
   return toreturn;
}

int main(){
   struct Node* node = NULL, *currNode = node;
   char ch = '\0';
   while(1){
      currNode = createNode();
      //Ask user to enter info...
      scanf("%d", &currNode->x);
      //Ask if user wants to add more...
      if(ch == '\n') break;
      currNode = currNode->next;
   }
   currNode = NULL;
   //print nodes and clean up resources
   return 0;
}


I would like to note that your current code is not freeing the memory it allocates. After you're done using the data, free the pointers with free();

Also, I think getche() is non-standard. Use getchar() instead.
Last edited on
riechan (48)
Honestly, I didn't know that you could structure it like this:

1
2
3
4
5
 
struct Node* createNode(){
   struct Node* toreturn = (struct Node*)malloc(sizeof(struct Node));
   toreturn->next = NULL;
   return toreturn;
}


Still learning the ropes. But for the mean time, I'd like to go over this on a more basic route and then amp it up as I go over everything. But thanks for pointing that out :)
Last edited on
riechan (48)
Daleth wrote:
I would like to note that your current code is not freeing the memory it allocates. After you're done using the data, free the pointers with free();


1. Does that statement imply that I should free all pointers by the time I exit the program? 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?

EDIT: 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?

EDIT2: 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
 
#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);
}
Last edited on
riechan (48)
I'm trying to get the origin node to connect to the succeeding node, but when I try to display the contents of the list, it only shows the first and last contents:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
void crtNode(int val){
	struct Node *newNode, *curNode;

	// Create a new node
	newNode = (struct Node *)malloc(sizeof(struct Node));
	newNode->Data = val;
	newNode->next = NULL;
	
	if(newNode != NULL){
		if(start == NULL){
			//Set start as origin node
			start = newNode;
		} else {
			//Set the current node to the newly created node
			start->next = newNode;
		}
	} else {
		printf("Failed to allocate memory.");
	}
}
Daleth (1030)
crtNode():
You don't use that curNode variable, so you can delete it.

I also suggest that you keep that start variable in main() and then pass it to the function as a parameter. There is no reason for start to be a global variable.
Also, what would happen if start->next turns out to already point to a node?
This might be the reason why you are only seeing the first and last Node contents. You keep cutting off the Nodes after the first with each function call before attaching the new one, leaving them orphaned and causing a memory leak.
I suggest using a loop to find the last node in the list before attaching the new one.

dspNode():
I see it does indeed free a pointer. However, it only frees the very last Node in the list. That means you'd have to call the function many times to clean up the entire list, which is not practical since it always prints the entire list.
Just make a cleanup() function or something to do all that work in one call. Or write a delNode() function as you have mentioned.

I mean, when exactly do I free a node?

When you free the memory depends on when you are finished using it.
1
2
3
4
5
6
7
 
int* var = (int*)malloc(sizeof(int));
*var = 5;
printf("%d\n", var);
*var = 7;
printf("%d\n", var);
free(var); //Done using the memory pointed to by var, so free it
var = NULL; //Set to NULL to avoid using it again

If you can possibly reuse the memory, then don't free it. Keep using it until you no longer need it. It is after you no longer need the memory that you should free your pointers.

When it comes to two pointers pointing to the same allocated memory, do not free both of them. You need only free one, but make sure to set both pointers to NULL.

The rule of thumb is: for every call to malloc(), there should be a call to free().

So if you just call malloc() once, you need to call free() just once.
Smac89 (1727)
Just a few comments regarding what I believe to be your insert function:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
void crtNode(int val){
	struct Node *newNode, *curNode;

	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){
		start = newNode;
		curNode = newNode; /*What is the purpose of doing this? curNode is not global*/
	} else {
		/*i.e. start is not equal to null so start can have something like 1 -> 2 -> 3 -> NULL*/
		curNode->next = newNode; //This is a seg fault as curNode is not pointing to a valid object
		curNode = newNode;
		//Where have you connected start to the new node created?
		/*i.e. you should have something like:
		 currNode->next = start;
		 start = curNode; */
		
		/* This also means you will be appending new nodes to the top of the list.
		 If you want to append to the last node in the list, you have to do the insert
		 differently*/
	}
}


EDIT: Saw your current insert. More comments

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
void crtNode(int val){
	struct Node *newNode, *curNode;

	// Create a new node
	newNode = (struct Node *)malloc(sizeof(struct Node));
	newNode->Data = val;
	newNode->next = NULL;
	
	if(newNode != NULL){
		if(start == NULL){
			//Set start as origin node
			start = newNode;
		} else {
			start->next = newNode; /*This overwrites the original start->next
			This should look like:
			newNode->next = start;
			start = newNode; */
		}
	} else printf("Failed to allocate memory.");
}
Last edited on
cire (8284)
I would expect a C linked list interface to look more like the following:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
 
#include <stdlib.h>
#include <stdio.h>

typedef int data_type ;  // If this typedef is changed, List_Print must also be changed.

struct node_type
{
    struct node_type* next ;
    data_type data ;
};

typedef struct list_type
{
    struct node_type* head ;
} List ;

List List_Create()
{
    List list = { NULL } ;
    return list ;
}

int List_AddItem(List* list, data_type item)
{
    struct node_type* newNode = malloc(sizeof(struct node_type)) ;

    if ( newNode )
    {
        newNode->data = item ;
        newNode->next = list->head ;
        list->head = newNode ;
        return 1 ;
    }

    return 0 ;
}

void List_Destroy(List* list)
{
    struct node_type* curNode = list->head ;

    while ( curNode )
    {
        list->head = curNode->next ;
        free(curNode) ;
        curNode = list->head ;
    }
}

void List_Print(const List* list)
{
    const struct node_type* curNode = list->head ;

    while ( curNode )
    {
        printf( "%d\n", curNode->data) ;
        curNode = curNode->next ;
    }
}

int main()
{
    List list = List_Create() ;

    for ( int i=0; i<10; ++i )
        List_AddItem(&list, i);

    List_Print(&list) ;
    List_Destroy(&list) ;
}


http://ideone.com/tMxWSh
Topic archived. No new replies allowed.