Is your technical interview only a few days away? Need to bone up real quick on data structures? Cool, let’s get started! Here’s what you need to know about Singly Linked Lists:
What are they?
Think of pearls on a string. Each pearl is connected to the next pearl by means of the strong. The string has a starting point, an ending point, and a total number of pearls or length.
Now let’s look at a picture of the the actual data structure:
In “computer talk” each pearl is now called a “node”. The node contains data. That data could be a number, a string, or even a copy of “War and Peace.” Each node points to the next node. That means each node “knows” which node follows it ( as indicated by the arrows in the picture above).
The first node in the linked list is called the head. The last node is called the tail. The tail, being the last node in the linked list, points to nothing, or in “computer talk” the value of null.
Before we go any further, you may be thinking, “This linked list seems a lot like a regular array.” Well, you’d be right!
Let’s look at a few of the pros and cons of arrays vs. singly linked lists:
-
An array has indices. A singly linked list does not.
If you want a certain item in the array, all you need is the index and you’ll find it quick. A linked list does not have indices, so the only way you can access an element is to start at the head of the linked list and loop through until you find what you’re looking for.
- Memory storage: think of arrays as chocolate bars of a certain size. They have to be stored “as is” in memory. You can’t just break them up and put a piece here and another piece there ( I wouldn’t be breaking up my chocolate!) . Arrays must be stored in a contiguous memory location.
On the other hand, linked lists can be stored in small chunks here and there in memory. It’s no problem because each element of the linked list “remembers” through its pointer which element comes after it.
This means that linked lists can be stored in non-contiguous memory locations. Think of how much more you can stuff into poor memory with linked lists!
- Lastly and maybe the most important for your interview is that inserting and deleting is much slower with an array. Think of it: say you have a 100 item array. You delete the item at index 10. Now all the rest of the items of the array, from the former index 11 to 99, have to move over one spot to take up the hole left by the removed item. Same idea for insertion. You have to insert the item in the desired location and then “push” all the remaining items over to make room for the new item. Try inserting and deleting from a row of 100 dominos, each standing on its thin edge--not fun!
Insertion and deletion is such a breeze with linked lists. All you have to do is find the first free memory space in memory-- remember it doesn’t have to be contiguous with anything else in the list-- then just readjust the pointers. So easy and quick!
Bonus Difference to Really Impress Your Interviewer
As a JS Developer you might not be expected to know this, but an array actually is allocated a specific amount of memory when it is declared. For example, if you were working in Java, you’d have to declare that your array with the variable name myArr was 10 elements long, for example. Array size is allocated in JS as well, but you don’t see it or have to deal with it.*
So anyway, with an array, memory is allocated as soon as it is declared, at compile time. This is known as Static Memory Allocation.
On the other hand, for a Linked List, memory is allocated at runtime as new nodes are added. This is known as Dynamic Memory Allocation. So this is a much more flexible arrangement of memory allocation than that static ol’ array!
Ok, enough talk. Let’s get down to code. Your interviewer could very well ask you to implement a singly linked list!
All this data structure stuff uses classes, so make sure you’re up on your basic OOP technique.
To code out our Linked list, we’ll actually need TWO classes. The first class will be to create a node (Our linked list will consist of nodes which will point to the next node).
Each node will have two properties: a value (val) and a "next node," or pointer. How ‘bout we call the pointer “next”. Here’s the code:
class Node {
constructor(val) {
this.val = val
this.next = next
}
}
Next think is we need to construct our second class which we’ll name “SinglyLinkedList.”
We want each instance of our SinglyLinkedList class to have a length, a head and a tail. We’ll start each instance off with a length of zero; and set both its head and tail to “null”. Nothing like a clean start!
Here’s the code. The SinglyLinkedList class is right under our previous “Node” class:
class Node {
constructor(val) {
this.val = val
this.next = next
}
}
class SinglyLinkedList {
constructor() {
this.length = 0
this.head = null
this.tail = null
}
}
By now in your interview, you’ll be workin’ that black marker like you own the place! You go!!!
Stay tuned for more interview prep….
*One of the best things I did for my general knowledge as a JavaScript developer was to take a couple of Java courses. It’s like going from driving an automatic stick shift (JavaScript) to a manual stick shift (Java). Just remember to find a quiet street to try it out on!
Check out part 2 where we take a look at the tortoise and the hare...
Top comments (0)