Basics of Computer Engineering: Linked List
Hi, how are you?
I`m Teo (aka Teogenes moura), and starting from this post, I`ll try to give a quick yet complete overview of several data structures, algorithms and other topics related to computer science/engineering.
Today we`re gonna talk a little bit about a very fundamental data structure used a lot in computing: The linked list. To give a very general overview, a linked list is that very simple list you see everyday in your day-to-day life (a list of goods to get in a grocery store, for example) but with the difference that each element on that list is connected to each other. For example, if your grocery store list was a linked list, it would look something like this:
strawberrys -> Hersheys -> comic books -> soda->NULL
(at least thats how mine looks haha ☺)
(Wondering what is that NULL doing there? It represents the end of our list, so that algorithms running on it know when to stop)
The advantage of having each element linking to the next one is that this approach easily allow us to go through our list to insert elements, remove them or just to print every and each one of the values inside of it. So, in code, how do we do that?
We use a very important characteristic of linked lists: it is recursive. When creating our element of the list code, we make it so that it contains a reference to the next element on the list so we never lose track of all of them. Let us make a little piece of code as an example:
struct linkedlist{
char* grocery_item;
struct linkedlist* next_item;
}
typedef struct linkedlist List;
In this little snippet of code, we created a structure called linkedlist, and each element of this structure contains a char* element, in which we can store the names of the things we`re going to buy and a reference to the next item on the list, so that we can go back and forth on the list easily. Before talking about inserting, removing and going through elements though, it is important to say that there are some different types of linked lists:
Singly linked list: Is the one we just described. It contains one or more elements and a reference to next element on the list.
Doubly linked list: Very similar to the singly linked list, but each element contains a reference to both the next and previous elements. That allow us to go through the list upwards and backwards, beginning from the first element or the last and going all the way to the opposite side of the list.
Circular linked list: The only difference between the circular linked list and the ones above is that on the very last node it contains a reference to the first node. That means that when we`re going through the list, instead of hitting a NULL value we’re headed back to the first one.
There are several other types of linked lists, but these are the ones I`ve came across the most and also are the ones that I`ve most frequently used.
We’ll continue to discuss insertion, print and several other functions used with linked lists in the next posts (I’ll update here with the link!). Also, I’ve written a example of code using linked list that you might want to check out:
