Data Structure and Linked Lists
I have been going down a journey of learning some computer science since finished my Bootcamp. I think it is integral to know what you are using whilst writing your code. It is great to know when to use an array and when to use a hash table, two topics I have covered in previous blogs.
With static arrays, we only have a certain amount of data or memory that can be allocated next to each other. However, dynamic arrays and static arrays can increase their memory and double up. However, doubling up an array will have a performance issue of O(n). We also remember insertion or deletion on an array for any element that is not the first or the last being O(n). Why? Well, we would need to loop through the rest of the elements after the insertion or deletion and moves the indexes.
Hash tables could store something wherever we wanted in memory, meaning we didn’t have to worry about insertion or deletion as we didn’t have to move around indexes, therefore having a Big O of O(1). However, the trade-off is…. hash tables are unordered!
So…. linked lists, where do they come in. Remember in the last blog, we said solving the issue of collision for hash tables could be resolved via linked lists.
This table is used a lot for explaining hash tables in other articles, I saw it a lot especially when I was learning and researching hash tables myself… but no one really explained what happens post-collision (after the red number). It may be in another blog of theirs so I won’t judge! But I feel it is good to know what your data structure is doing even if you don’t need to use it. So let’s explain it.
Linked lists aren’t actually built into Javascript unless you build one yourself. They are more common in lower-level languages like Java where you also have to be aware of and manage your memory space/garbage collection! So what is a linked list?
As defined by geeksforgeeks ‘A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers as shown in the below image:
In simple words, a linked list consists of nodes where each node contains a data field and a reference(link) to the next node in the list.’
We will discuss one of the two types of linked lists in this blog: singly-linked lists. We will discuss doubly-linked lists in the next blog.
A singly linked list contains a set of nodes. Nodes are formed of two parts, the value (shown as data below) and a pointer.
The first node is called the head and the last node is called the tail. Linked lists are also called null-terminated, meaning the last node simply points to Null!
A great visual learner that was brought to my attention thanks to Udemy and Master the Coding Interview: Data Structures and Algorithms is Visualgo. Have a play around with the hash tables, arrays and linked lists, it’s incredibly informative and interesting to watch a visual perspective of what is happening.
You may be wondering what the difference is between linked lists and arrays? A big difference is array elements are found next to each other in memory whereas linked list elements are scattered. Computers usually have a caching system which means reading from sequential memory faster than reading through scattered memory. So iterating through a linked list can be slower than iterating through an array even though they are both O(n)… however, insertion and deletion are a lot faster. Regarding, hash tables the one benefit linked-lists have is that although the data is scattered there is some form of order. If you look at the diagram above each node points to the next node. To give you a better understanding of the Big O — take a look at this table.
Now you may be looking at the deletion of a singly linked list and wondering why it is O(1)… There is a very good discussion on stack overflow here → https://stackoverflow.com/questions/14048143/why-is-deleting-in-a-single-linked-list-o1.
Let’s move onto the next part of learning about linked lists. The pointer! Or in the diagram earlier, the arrow.
I have created a pointer here. mySecondFavouriteObject has a reference to an object. So the pointer is the reference to the memory space. We aren’t copying myFavouriteObject into another space in memory. When we look at our RAM, there is only one entry for {name: “JimBob”}. Both myFavouriteObject and mySecondFavouriteObject point to {name: “JimBob”}. If you don’t fully understand that, don’t worry, use the visual below.
Okay, so this returns { name: ‘Jimbob’ } with the number 1 or 2 after it… what does this prove? Well, follow the next code snippet below to confirm that both objects simply point to the same { name: ‘Jimbob’ } in memory.
The name changes for both! It works if you also change mySecondFavouriteObject.name instead.
One final test, let’s delete myFavouriteObject and see if mySecondFavouriteObject still retains the key/value pairing.
It should still keep the reference!
This should give you a better understanding of how a single linked-list works.
Next, building your own linked-list in Javascript. So we understand the concept of what a single linked-list should be, but how do we design one, with a basic append and prepend.
Well firstly, we would need to create the beginning of the linked list which is the head node (which would also be the tail node for the first data entry).
So, this should be fairly self-explanatory. But we are passing our class linkedList a value, the constructor creates the first node using the value being passed in, it’s pointer (next) is then set to null as the end of a single linked-list must point to null.
Now we have the beginning of a linked-list let’s create an append and prepend method.
A lot is going on here but it is all fairly standard method and class stuff. We simply create a method function called append which takes a value. This is used to create a new node that will be at the end of our single linked-list, therefore we know this node must point to null.
We then set our current last node to point to the newNode being made and make our newNode the tail!
See if you can figure out the prepend method as it’s fairly similar!
The only real difference here is that our next value needs to be set to the current head node before we change our newNode to the head of the linked-list!
I haven’t done insertion or deletion, but have a go at those yourself. I learned the majority of this knowledge via Udemy and the Master the Coding Interview. Truly is a great breakdown of everything.
