Linked Lists

Question

So I've been playing around with linked lists and was wondering why this doesn't work (the node was not added to the front of the list)

int main() {
    node_t *linkedList = malloc(sizeof(node_t));
    linkedList->value = 1;
    linkedList->next = NULL;
    addToEndOfLinkedList(linkedList, 10);
    addToEndOfLinkedList(linkedList, 32);
    addToFrontOfLinkedList(linkedList, 83);
    printLinkedList(linkedList);
}

but when I changed it to this it did work (the node is added to the front and printed out).

int main() {
    node_t *linkedList = malloc(sizeof(node_t));
    linkedList->value = 1;
    linkedList->next = NULL;
    addToEndOfLinkedList(linkedList, 10);
    addToEndOfLinkedList(linkedList, 32);
    node_t *updatedList = addToFrontOfLinkedList(linkedList, 83);
    printLinkedList(updatedList);
}

The 'addToEndOfLinkedList' returns a pointer to the second last node and the 'addToFrontOfLinkedList' returns a pointer to the head of the list. I didn't include all my code since it's saved on a different computer but will update if needed so you can see my functions. I'm also aware of memory leaks and have free'd the list in my code. This is just from the top of my head. The print function just iterates through the list and prints the value at each node.

one more question, do I have to typecast malloc?

my code

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
	int value;
	struct Node *next;
} node_t;


void printLinkedList(node_t *head) {
	int elementCounter = 1;
	node_t *current = head;
	
	while (current != NULL) {
		printf("Value at Node %d is %d\n", elementCounter, current->value);
		elementCounter++;
		current = current->next;
	}
}

node_t *addToFrontOfLinkedList(node_t *linkedListHead, int valueToSet) {
	
	node_t *newHead = malloc(sizeof(node_t));
	
	if (newHead == NULL) {
		printf("Memory can't be allocated for the new node");
		return NULL;
	}
	else {
		newHead->value = valueToSet;
		newHead->next = linkedListHead;
		linkedListHead = newHead;
		
		return linkedListHead;
	}
		
}

node_t *addToEndOfLinkedList(node_t *linkedListHead, int valueToSet) {
	
	node_t *NodeToBeAdded = malloc(sizeof(node_t));
	
	if (NodeToBeAdded == NULL) {
		printf("Unable to allocate memory to NodeToBeAdded");
		return NULL;
	}
	else {
		NodeToBeAdded->value = valueToSet;
		NodeToBeAdded->next = NULL;
		
		node_t *current = linkedListHead;

		while (current->next != NULL) {
			current = current->next;
		}
		
		current->next = NodeToBeAdded;
		
		return current;
	}
}

​

Posted Jul 18, 2020, 10:18 AM UTC · edited

310
soniduino•

Is this a library you're using? Your own creation? Something from a website? Can you provide the source for the linked list to maybe help us understand it's implementation?

5
ap_100OP•

i was following along with this - https://www.learn-c.org/en/Linked_lists

I'm just trying to revise linked lists. Sorry, updated with my code now.

3
lmlight77•

C is call by value, so your call to “addToFrontOfLinkedList()” doesn’t update “linkedList”. You should assign the return value back to “linkedList”. Even though the call to “addToEndOfLinkedList()” was not saved, your code works as the linked list was not empty to begin with before the first call, so the head of the list is unaffected by the call.

5
ap_100OP•

oh that makes a lot sense, thanks man!

3
AnastaciusWright•

Hi. Please add all your code, so we can see how those functions are constructed. Also, no, malloc does not need cast there.

3
ap_100OP•

Done, and when should it?

2
AnastaciusWright•

I think it is a matter of scope. When you return that pointer, current, if you do not asign it to sth, you lose it. It is destroyed when you get out of the function. When you are doing that assignation, you keep the value of the pointer. I will check this tomorrow so I can be sure.

1
das_cow•

I think the first use is wrong, since you are returning the head of the list and not modifying it when you print it only shows from the second position, the other value exists but since you didn't store that pointer you can't access it.

1
nerd4code•

You don't have to cast void * to any other pointer type, and any pointer type will similarly corce to const volatile void *, though code pointers might not give you sensible results. In the general case, opinions differ as to whether one should or shouldn't cast, with roughly equal points on either side.

If you're doing something like a create_new(T) macro, then you should cast, because the compiler can trivially check to make sure you're not assigning to something other than a T *. Where being more specific with your types helps w/ reading, debugging, or maintenance, cast.

Another thing to consider: C++ has different rules, but C headers are frequently included in C++ code. C++ has the same to-void * coercion rules as C, but going from void * to another ptr type does require a cast, typically of the static_- variety. So if you're doing inlines or macros in a multi-language header, always cast.

1
ap_100OP•

Thanks a lot!

1