Singly Linked List 'Push' Method for Dummies (me)
Tags: singly, linkedlist, push, javascript
Published: 2024-01-04 04:31:40

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

---

<u>So in summary for its use-cases:</u> 

- Linked lists are good for when you have a **_large dataset_** and it will mainly be used for **_insertion/deletion of data_**

<u>And for its drawbacks:</u>

- 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:

---

![JavaScript code snippet for basic linked list structure](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/9rcisjzjvvsvao6bua87.JPG)

---

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

---

![code snippet for linked list push method](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ymjudvmwr09gd33nyoff.JPG)

---

If you're seeing `LL.prototype.push` and are thinking "_the heck is a prototype?_", [this](https://www.youtube.com/watch?v=GewOrG12pt4) 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:
![node instance snippet for linked list](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/x4wjchawpufk5allrdyy.JPG)

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:
![conditional statement to check if our linked list's head it established](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/bkfw44h0w2fktkb5mar4.JPG)
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:
![else statement to populate our list if the head is already occupied](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/074t0jehwfkbo7d0bkcs.JPG)

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:
![conditional statement to check if our linked list's head it established](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/i3hxpee9qkty41l2p26p.JPG)

---

`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:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/z0f3xir3q8fbp7uz8t71.JPG)


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](https://en.wikipedia.org/wiki/Don%27t_repeat_yourself) 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