every good programmer should know how to code this data structure (its easy)

Every new programmer should learn how to make a linked list in C. Linked lists not only demonstrate proficiency with pointers in lower level languages, but also act as a tool that you can take with you to other projects that require dynamic storage that is both searchable and fast.

In this video, we discuss what a linked list is, the various operations you perform using a linked list, and how linked lists can be built in C.

🏫 COURSES 🏫

🔥🔥🔥 SOCIALS 🔥🔥🔥

[esra_erimez]

For those interested in fundamental data structures and algorithms, I highly recommend "Algorithms + Data Structures = Programs" by Niklaus Wirth. It is the seminal authority on the the topic.

[alistair.foggin]

In removeNode, you only free the removed node if it is in the middle or the end of the list. If it is the head, it is not freed so there is still a memory leak. Other than that, this is a fantastic tutorial! Keep up the good work!

[chossuh]

Due to caching linked lists are usually slower than a simple contiguous vector.

Bi-directional Linked lists typically require 3x the number of bytes as a simple vector structure, so they hurt performance for even medium sized lists.

[lennonmclean]

I left a PR that fixes a couple issues with the code. As Alistair Foggin said, there is a memory leak in removeNode, and the call to malloc() in addNode only needs to occur in one place. Additionally, as noted by Mohammad Salman, the insertNode() function does not interate through the list each time the position variable is decremented. This means that insertNode only ever inserts into the second position.

[misterrreco]

My favourite implementation of a linked list is a circular doubly linked list. Here the nodes have 2 references, previous and next. The head of the list is not a part of the list (its data is unimportant), instead it points to the first node and the last node as its next and previous references, respectively. If the list is empty, then the head points to itself on both previous and next. The reason why I like this is because, being circular, there are no edge cases. Removing the first element is the same as removing an element in the middle of the list or the end. Inserting an element is the same regardless if the list is empty, you are inserting at the start, end or middle. This simplicity makes fixing bugs and adding more functionality to the list much easier.

[pqsk]

Doesn't matter how long I've been programming, there's something about implementing and viewing the code for a linked list that's just fascinating. Great stuff. I was taught to always have a head and tail node. So I always code that out of habit. It does complicate the code just a little bit though.

[darkfire]

I would definitely agree that a programmer should know and be able to implement a linked list but that being said, linked lists are almost never the best solution to a problem. Due to the expensive heap allocations, CPU cache, deref iterations and a bunch of other things linked lists are generally "slow as shit" except in a few very rare cases

[dagoberttrump]

You don't need to branch if head points to NULL, just assign head to the new node, if its NULL so be it.
Also position 0 should semantically mean "before the first", it seems now you can only insert after the first element (you can add though but add can be implemented in terms of insert as a simplified function)

[maruseron]

why are we appending to the front? why are we using void pointers? why are we nesting if + switch instead of using a guard clause or just letting the menu default? we are duplicating mallocs in different branches of addNode, we have a memory leak in removeNode, we're not handling negative values for position NOR EVER MOVING THE CURRENT NODE in insertNode (no wonder it literally doesn't work)
this implementation is borderline insane and it's even crazier that you had the balls to upload this

[ekenedilichukwuekeh]

I noticed your new use of transitions since I’m a part time videographer as well. Your production quality is up from last year! Keep it up. I’m loving the consistency!!

[no-one]

I love how clean this tutorial is. Keep it up 👍

[twentyeightO]

I think to append a node in constant time, we can maintain a tail pointer. So in push() we push new node into head pointer if it's null and make tail equal to heads next, else we push new node into tail and make tail equals to tails next.

[rafaelveronezi]

There's an issue with the insertion code, it's missing an instruction on the initial loop to update the `current` reference, just like that:

while (current != NULL && position != 0)
{
position--;
current = current->next;
}

Without this, the code will just run down the position, but the item will always be inserted as the next from the head, since the current never changes. Other than that pretty cool video, thank you!

[odealianaffairs]

im learning how to code using the cs50 course on youtube and the section about linked lists absolutely stumped me. After watching this tutorial i realized my understanding of the syntax in C was wrong and i finally figured it out. thank you so much.

[yochayken]

You are doing an amazing videos! I would just suggest that if you want to append element in the list you could do it in complexity of O(1) by creating a pointer named “tail” which points to the last node. 😊

[glennmiller]

I use extra pointers. One for the last and one for the previous. It allowed me to walk forward or backward and I didn't have to walk the list to get to the end. It was especially helpful for large lists. The code to keep the pointers current is less than one might expect.

[TheMrKeksLp]

With how horrendously bad linked lists are for cache efficiency and auto vectorization the thumbnail is actual clickbait. I thought I was about something interesting

[khroomlet]

A fun followup to this is a fibonacci heap, which heavily uses linked list concepts but is O(1) for many of its operations!

[manvardhan]

hey just wanna let u know im watching ur channel since last year and i really appreciate ur content, thx for making quality videos

[refeals]

Man this content takes me back to first year of college, having to create all these different data structures from scratch. Good times.
A lot of people using high level languages dont realize how important it is to have a good grasp on how all this works behind the scenes.