Linked Lists
What are linked lists? Linked Lists are a linear collection of data elements. Think of linked lists like a train, where all the cars are connected and carry some sort of cargo or passenger. In this image here, the linked list is carrying a giraffe, penguin, tiger, and a zebra. One could describe linked lists as a sequence of nodes/data. You can put mostly anything inside a linked list, even other data structures such as: lists, stacks, queues, associative arrays, and S-expressions.
Parts of a Linked List
Like a hook that connects train cars together, there is a part of the linked list called the reference. The reference serves as the pointer between nodes and always points to the next node. At the very front or top of your linked list is the head, and at the end or bottom is the tail. The dynamic array equivalent of the head would be index 0. As for the tail, the equivalent would be index n-1. Anything after the tail would be NULL, as linked lists end at the tail.
Linked Lists vs Dynamic Arrays
So why do we use Linked Lists? Linked lists are extremely useful for storing data because of how easy it is to store and delete information. Unlike dynamic arrays, in which the indexes change with every insertion, the indexes stay the same in Linked Lists, making it much more efficient to find data. Dynamic arrays always assume elements stored are the same size, while linked lists do not. So it is much easier to store data of all sizes in a linked list! Speaking of size, linked lists can easily expand and shrink, while an array’s size must be set ahead of time. This means that elements can be stored in a linked lists indefinitely, while dynamic arrays may fill up and need to be resized.
Basic Functions
One of the most basic functions for a linked lists is the length() function. What it does is count how many nodes there are in your linked list. What this snippet of code does is check if the node is empty first. If not, add 1 to the count. So, if you call the length() function, it will return the count of how many nodes are in your linked list.
This is the append() function. A standard function that allows you to add nodes to your linked list. In the append function however, it will add to the end of the list, and if you remember from earlier, this is called the tail. So it will add the node after the current tail, and whatever is the last node afterwards will be the new tail. So when implementing your append() function, make sure to assign the new node as the new tail!
Prepend is just like the append, just instead of adding after the tail, we’re adding before the head. Whatever node is put before the head will become the new head. Why is this? The very first node in your linked list will always be the head. So when implementing your prepend() function make sure you assign this new node as your new head!
Now this one is called the find() function. This will make it easy to find whatever node you need. To find data, the system loops through the linked list until it finds the data that matches the query. If the data cannot be found, it will return nothing.
Last but not least, the delete() function. Deleting a node from a linked list is a bit more complicated than adding one. To delete a node, you must find the node you wish to delete first. After finding the node, you can delete the node, but you won’t be quite done yet. After deleting the node, you need to reassign the head and tail, as well as change the size of your linked list. After deleting an item from the linked list, you need to find whatever is at the front or the top after removing the node. That will be the new head. Delete what the head was before and assign the head as whatever is at the front. If you were to delete the head, then the node afterwards would be your new head. The same can be said for the new tail. After deleting your node, make sure whatever node is at the bottom/end is your new tail. Just like the head, if you delete the tail, you have to assign whatever node that came before the tail as the new tail.
Conclusion
Linked lists are very useful for storing data, and are very fast/efficient. Just think of linked lists like a train. You can add new train cars and hook them on to the others, and if you remove a train car, you have to close the gaps. When looking for something in a train car, you go through each car until you find the contents you were looking for.
