Data Structures — Linked Lists
Hello, in this tutorial, I’m going to talk about linked lists. It’s one of the most basic data structures and I think almost everyone would need to know about it. By the end of this post, you will know what linked lists are and why we should use them.
A linked list will put the values in each of these boxes, and these boxes are all linked together. And when I say linked, it means that each of the boxes contains an address indicating where the next node is. So it would look more like this:
Let’s compare this to an array, each box in an array is indexed, and the indexed boxes are physically next to each other, in the memory space.
This means if you want to change a value in an array, for example, let’s say you want to change the fourth element 15 to 16. You can simply say “go to index 3 of the array, and change the value to 16”.
It’s very simple.
But when it comes to linked lists, we need to start at the head, and then follow along each node on the link list to access the fourth node. Only then we are able to change the value of the fourth node. So it would be slower. The number of steps we need to take will increase linearly if the node if further away from the head.
Then why would we use linked lists? If you use a linked list, adding and deleting an element at the beginning, is going to be pretty fast, It would only take constant time.
In other words, adding or deleting a node at the beginning of the list, will be very fast whether if we’re dealing with a small list or a very long list.
Adding or deleting a node at the beginning of the list, will be very fast whether if we’re dealing with a small list or a very long list.
When I was mentioning arrays, remember how I said the boxes are physically next to each other in memory space? This means that if I want to insert something at the beginning of the array, all the other elements in the array will have to shift. But for a linked list, you don’t need to go through all that trouble, and this can be very useful in some applications
The linked list we just saw is called a singly linked list. There is also another type of linked list called a doubly-linked list. A node in a doubly-linked list also contains the address of the previous node.
In a single linked list, it was easy for us to insert or delete an element at the beginning. But if we want to add or delete something at the tail, we’ll have to go through the whole list. A doubly linked list can solve that issue for us because adding or deleting at the tail would be easy and cheap.
So those are the basic things you need to know about linked lists. If you are a Golang lover like me, you can see the process of implementing a linked list in the video below.
