Doubly Linked List (in C)

---

Double-linking adds an extra pointer (previous) and makes it easier to modify your linked lists or traverse them in reverse.



***

Welcome! I post videos that help you learn to program and become a more confident software developer. I cover beginner-to-advanced systems topics ranging from network programming, threads, processes, operating systems, embedded systems and others. My goal is to help you get under-the-hood and better understand how computers work and how you can use them to become stronger students and more capable professional developers.

About me: I'm a computer scientist, electrical engineer, researcher, and teacher. I specialize in embedded systems, mobile computing, sensor networks, and the Internet of Things. I teach systems and networking courses at Clemson University, where I also lead the PERSIST research lab.

More about me and what I do:

To Support the Channel:
+ like, subscribe, spread the word

Want me to review your code?

You can also find more info about code reviews here.

[JaimeWarlock]

I started working at a new job on a word processing program that used recursive double linked lists after the previous team all quit together. Code was 8086 assembly and used a memory expander card since the documents could exceed several megabytes. The memory expander card could only show 64K or ram at a time, you had to set a register to change which 64K of ram you were looking at. This created interactions between data segments and memory expander pages when deleting a double linked list item that crossed boundaries. This bug was rare (could take hours to show up, but would crash the computer) and if you changed the program at all to try and hunt the bug down, it would just disappear till you found a new sequence to make it show up.

Everything else in the program worked and everyone was just waiting for me to solve this last bug before shipping. My boss was complaining and my home life sucked at the time making concentration hard. I just couldn't take the pressure and eventually just walked out to never be seen again. I always wondered where the original team came up with this twisted data structure. I thought it was unique to that job. I still have nightmares about it.

Seeing this video makes me realize double linked lists weren't unique. Somebody dreamed it up, but I imagine it is a lot easier to work with in a linear address space.

[____sammy____]

Thank you very much Jacob, without you i wouldnt finish my Data Structures class with such a good implementation, and i definitely wouldnt improved so much in C programming.

[mandeath]

Thank you Jacob, you've been a good teacher

[AinurEru]

For remove_node() I found this to be simpler easier to follow:

void remove_node(node_t **head, node_t *node_to_remove) {
if (node_to_remove->prev) node_to_remove->prev->next = node_to_remove->next;
if (node_to_remove->next) node_to_remove->next->prev = node_to_remove->prev;
if (node_to_remove == *head) *head = node_to_remove->next;

node_to_remove->prev = node_to_remove->next = NULL;
}


You can look at it a bit and see that all the edge-cases are handled by that.

[Pompiq]

your videos are incredible! the best i have seen on youtube so far. You even made me comment! I hope that more people see these!

[alexhaight]

Incredibly excited I'm still able to get my necessary dose of Dr. Sorber while he's away

[switchcraft]

Very good tutorial.

There is a bug in the insert_after_node() function. It should be: "newnode->next->prev = newnode;" instead of "newnode->next->prev = node_to_insert_after;"

[ViniciusTeixeira]

I don't think removing a node in a simply linked list is that hard, you can just check if Node->next->value is the one you're looking for. Then create a pointer that points to the node you want to remove (let's call it remover) and then do node->next = remover->next. Then just do free(remover) and there ya go :)

[homayounshokri]

Can you please make tutorial about kernel data structures?

[周辉-np]

Hi Jacob, I have a question regarding the `remove_node` function. Why do we not include `free(node_to_remove);` at the end of this function to release the memory of the node being removed?

Additionally, I noticed that the program lacks a `free_all_nodes` function to free all nodes after the linked list has been utilized, here's my version:

```c
void free_all_nodes(node_t **head) {
while (*head != NULL) {
node_t *temp = *head;
*head = (*head)->next;
free(temp);
}
*head = NULL;
}
```

[ginko]

should we free the remove node? Rather the just NULL

[Silverdragon]

Awesome stuff! Where would you find yourself using linked lists over arrays primarily Jacob?

[lmaox]

How come it's writte as newnode->next->prev instead of just newnode->prev ?

[dominikklon]

If the coding video isn't speeded up... Wow, I'd love to code so fast one day too.

[praenubilus]

remeber you switched from Atom to VSCode at some time point. Is there an episode talking about how you configure your vscode for C?

[benpicone]

Hi Jacob,
I am still a little shaky on the usefulness of a pointer to another pointer. I have a decent grasp on the concept and how to use them but I guess I just do not see the point (lol). I tried changing the double pointer argument to your remove_node function to a single pointer to a head and adjusted the syntax inside that function as well as the function call inside main accordingly and ended up with the same output. Could you explain why it is useful in this context? Or maybe I got lucky with my code and it really shouldn't be working

[pedroraposo]

Amazing video. I was looking for a simple tutorial on this issue and I'm very glad that I could find your channel. I followed your video (and adapted my code a little) and I was able to attain the same result as yours but with a minor error in my final result.

I've inserted a node in the middle of the double-linked list and then removed the node right after this new one. The problem is when I removed the node the program also deletes the newly added node. It only happens if you try to remove the node right after the new one.

Could you lend me a hand?

[inminutes]

In the insert_after_node() function despite using newnode->next->prev=newnode it gives me a derefrencing error... Please help
Ps... Great video btw

[acetech]

Great video! Youtube could use a good video on circular doubly linked lists if you are up for it! Thank you for your contribution!

[lordadamson]

To delete a node in a singly linked list you swap its value with the next one and delete the next one instead :D


if the next is null then I guess you have to iterate over the whole list.