Linked Lists aren’t a headache
Data Structures are kind of confusing and strange at first I’m not going to lie. In an attempt to further my understanding of them and learn about them more, I’m going to try explaining them to someone else. Maybe if I can explain it well I’ll learn some things and so will anyone who finds themselves sorry enough to read this.
Linked Lists are a linear data structure like arrays. We all know and love arrays as our favorite linear data structure where I can go through it one at a time by incrementing through the indexes. It’s called a linear structure because I can store a fixed amount of homogeneous data in a linear list. Arrays are a very powerful tool but it has some shortcomings. When I declare an array I take up a fixed amount of storage even if the array is empty. This is not so great for storage management and scalability because while there are nice and friendly methods adjust the size of the array in any direction, this in many instances can cost your program storage and efficiency. Array resizing also leads to shifting which is not always necessarily what you want. This is where linked lists come in. A linked list consists of nodes that have two pieces of data. One being the actual data you want to store, and the other being the location of the node in front of it. This makes it so you can scale the list as the data grows. Here’s a nice handy chart to help you out.
So lets take a look at all this.
In order to advance in the linked list, you go through each node in order to find where the next piece of data is. This means it can be slower to find data in the linked list versus finding it in the array each situation (as it always is in coding) is going to unique to the problem, but sometimes a linked list can suit you better.
Now this concept is all fine and dandy but lets actually make some practical use out of this lets build a linked list. A lot of languages have a linked list class built in but the point isn’t to learn how to call functions, it is to learn what those functions do. Lets define a node class. I will be using Ruby for this example.
We initialize the node with a value and an optional parameter in the off chance you know the next node to go to. If not it defaults to nil. I make my accessors for the variables and I make a to string method that will return the contents of one node. Now that we have out handy dandy node class, lets make our linked list class.
We make our class and in the initialize we set the head = nil and the size = 0. We set the head (or first node in list) to be nil so that on creation we can have an empty list. Size is something that can be useful in some methods and a list should generally know how long it is. Lets add some data to our list.
This append method takes in a value for the data you want to store. The great thing about Ruby is that you don’t need to declare data types so passing through objects is no big deal. If you were to write this in Java or C# you would need to utilize generics which is a whole other can of worms. Since our list is empty at the start, we must account for that by checking if the head is = to nil. If that’s the case then we want to make the head a new node with the data we wanted to append. If not then we need to go to the next empty node. We do this by looping so that if the current node we are on does not have a next node to go to (current_node.next_node != nil) then the current node becomes the next node and now we check if the new current node has a next node. We do this until there is no longer a next node meaning we’ve reached the end of our list. We then simply create a next node thus appending the list by one. Let’s remove a value.
First the remove function has to check if the head contains the value we want to remove. If it does then we simply want to set the head to equal the next node thus eliminating the current node containing the data we wanted to delete. If it’s not the head then we are going to have to go through all the nodes. We exit this loop then the next node is nil meaning we have reached the end, or if the next node contains the value we want. If we have reached the end, we know we will not find the data to remove in the list and we exit. If there is a next node and it’s value is equal to the value we are searching for, we want to set the next node equal to the next next node thus removing the next node from the chain and therefore the value we wanted to remove. A little weird to look at in code but sketch it out visually and it should make more sense. Remember that in a linked list the data only knows where the next data in front of it is.
Try building out your own linked list class and avoid looking at this code. Also try making extra methods that incorporate size. Thinking through what actually is happening is crucial to understanding what linked lists are and why we care. Ruby also makes it a little easier to visualize in code try looking up an example in another language too. Linked lists are a very popular interview concept as well so a good understanding goes a long way there and when it comes to learning other data structures.
MORE READING
