Whenever I come back to implementing the most basic method for singly linked lists (push), I'm always scratching my head, thinking to myself, "how did I implement that again?". So here I am once again my friends, typing out concepts I don't fully understand in order to make sense of them.
Linked lists at their core are simply alternatives to using a basic array. Why might we choose a linked list over an array, you ask? Let's go over the benefits:
1.) More efficient insertion/deletion processes (typically an O(1) time complexity) over standard arrays
2.) Useful for datasets where the exact number of items isn't known; this makes for a much more flexible data structure that can be changed more efficiently
3.) Serialization (conversion from an object into bytes for transfer) is more efficient with linked lists than arrays
As with all data structures however, there are downsides to using them and linked lists are no exception. When might we NOT want to use a linked list? Let's go over the drawbacks:
1.) If your dataset requires a lot of data inquiries (look-ups), linked lists will perform worse than arrays. This is due to the fact that their location in memory (e.g., an index position) doesn't typically exist (but it can; the efficiency of that look-up will still perform worse than a basic array though)
2.) Smaller datasets won't necessarily benefit from any of the reasons for using a linked list. It may be more useful to simply use an array if the cost/benefit in time and space complexity for insertions/deletions won't be a cause for concern
So in summary for its use-cases:
- Linked lists are good for when you have a large dataset and it will mainly be used for insertion/deletion of data
And for its drawbacks:
- It probably won't be of much use if you have a small dataset that will mainly be used for searches and data-manipulation
Alrighty, let's dive into implementing the basic structure of a linked list and its most basic push method:
We first have our two constructor functions that will be the backbone in building our linked list; the LL will be where we have our head, tail and length properties.
The head is our entry point into the linked list. All data will be passed through the head in order to populate our list.
The tail is our terminal point for the linked list. The tail will always contain the very last data point in our list. We don't necessarily need to have a tail in a singly linked list, but it does make it more efficient with finding the very end of the list.
The length property is simply what it sounds like. It'll let us know how many items are contained within the list.
As for the Node constructor, its sole purpose is to add onto the linked list. It will contain some data (val) and a next pointer that will be linked to the subsequent node in the list. The default value for next will be null to accommodate any future node insertions.
Now let's explore our first method:
PUSH
If you're seeing LL.prototype.push and are thinking "the heck is a prototype?", this is a great resource. It's a bit lengthy, but I can almost guarantee it will cement the concept for you.
And if you're wondering why I'm not using ES6+ class syntax, it's because I'm exercising my constructor/prototype muscles, as they're getting flabby.
ANYWHO
What we're trying to accomplish with the push method is very similar to the built-in array method by the same name in JavaScript; we simply want to add some data to the end of our list. This is first accomplished by assigning the desired piece of data (or node) to a new instance of our Node constructor we defined previously:
After that, the first thing we want to check for is if we even have anything assigned to our head property, which as you remember, is the entry point into our linked list. If we don't have anything assigned to head, then we'll want to populate it first, as well as assigning that same piece of data to our tail property:
The reason we want to assign this.tail to this.head is because any new piece of data (newNode) that we are inserting into the end of our list will need to mirror our tail. This will become more apparent once we dive further into this method. Bare with me, I know it's confusing as heck the first few (or dozen+) times you're trying to make sense of this.
So now that we have our node to insert and we've checked our head to see if it's empty, let's see what we do once our head is actually occupied:
This is a duplicate assignment we're doing for two different properties. this.tail.next is being populated by the Node constructor with what we've assigned to our constant variable newNode.
The reason our LL and Node constructors are linked is thanks to the previous line of code we performed:
this.tail.next is essentially just this.head.next
Read that again.
And then again.
And then look at the code and then read it again.
⁽ˢᵉʳᶦᵒᵘˢˡʸ ᵖˡᵉᵃˢᵉ ᵈᵒ ᶦᵗ⁾
That previous point is essentially the crux of how this is all working. We have our Node constructor which will be assigned to the this.head and this.tail properties in our LL constructor and all future data will be passed through both of those properties once our initial head is populated.
Once we've arrived to our third push invocation of data insertion, we'll only be working from the tail from that point on. The head exists to initially populate our list and then act as a liaison to transfer its population onto the proceeding tail properties.
Again, to reiterate, once we've populated this.head and assigned this.tail to this.head, we're simply populating the tail and the inherent next property that the tail has with any subsequent data.
If that's not fully making sense, don't worry. Even upon taking my time and typing all of this out, I'm having to second-guess what I'm typing out. This are very unintuitive concepts.
BUT if you were able to make sense of that, congratulations! Either you knew about that already or I, by some miraculous intervention, clarified that a little for you. All that's left to do is return out from the method and increment the this.length property on the LL constructor to signify that we've populated our list:
Some implementations of the push method have multiple sections where they increase the this.length property, but I like this rendition as it adheres to the fabled DRY principle.
And that's all I have to give, friends. You can bet your bottom dollar I'll be back with the 𝓈𝓅𝑜𝑜𝓀𝓎 pop method for linked lists when I get around to it.
~ Thanks for stoppin' by! ~
<3<3
Top comments (0)