Linked Lists for Absolute Beginners
From a slightly-less-than-absolute beginner.
So the first time I tried to operate on a linked list, I had no idea what the heck’n heck I was doing. Shall we just revisit the terrible code I wrote?
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} list1
* @param {ListNode} list2
* @return {ListNode}
*/
var mergeTwoLists = function(list1, list2) {
const newList = [];
for (const number in list1){
if(list2[0] <= number){
newList.push(list2[0]);
list2.splice(0, 1);
}
else newList.push(number);
list1.splice(list1[0])
};
};
return newList;
};Here’s the deal. Linked lists are not arrays. I didn’t know this at the time, but you can gather hints about how to work with them in the ListNode definition — that bit about this.val and this.next.
Okay, I’m getting ahead of myself here. First…
What is a Linked List?
I dunno. Something about…memory storage…pointing to the next location in memory…only one way…
Here’s what I do know:
- Linked lists are made up of nodes — i.e. that ListNode definition I referenced earlier. Each ListNode has a value (this.val) and a pointer to the next ListNode (this.next). If you want to see it all written out, here’s an example of a list that looks like 1 -> 2 -> 3 -> 4 -> 5: let list = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5))))). So pretty, no? 😉 Basically, it’s saying the variable list is a ListNode with a value of 1, which points to a new ListNode with a value of 2, which points to…you get it. Hopefully.
- You can’t reference specific Linked list nodes by index like you can in an array! This is key. Essentially, your toolbox is to go down the chain one ListNode at a time to find and do what you want to find and do.
- You can only move forward in a Linked List (or really, a singly linked list, but this isn’t getting into doubly linked lists, which I really haven’t worked with very much). So if you need to do something like delete a node with a specific value, you’d better be darn sure it’s in your sights before you land on it. That’s where this.next comes in handy.
Which brings me to…
The Rules for Working With Linked Lists
AKA what I wish Neetcode would have told me at the beginning of my Grind75 journey.
- Don’t operate on the list itself! Here’s why. By the time you’ve reached the end of the list after manipulating it however you want, you won’t have a list to return! I wish I could explain this in a way that makes sense, but honestly it doesn’t even make sense to me. Just think of it as a chain necklace that you’re destroying as you investigate each link one by one. Or, you know what? Maybe don’t. If I try to explain it it doesn’t make sense.
- Do (as an alternative to the above) create a curr variable that initializes itself as the list, and then operate on curr rather than list. In less-fancy words: let curr = list. Just do it. It’ll work. I promise.
- Do, in some cases, create a new ListNode — a dummy head — and copy the list you intend to work with to the next pointer. When will you know do this? In cases where you might have to operate on the head of the list. So, for example, if you need to delete all nodes with a certain value, the head of the list could very likely be that certain value. The easiest thing to do, in that case, is create a new list with a dummy head (I always initialize it to 0, but it doesn’t really matter what it is) and the next pointer pointing to list. Then do the same thing #1 tells you to do — create a curr variable that points to dummyHead, and operate on curr for the rest of the problem.
- Do, if the above is the case, return dummyHead.next. Since dummyHead’s value is whatever/unrelated to the problem, you don’t want to return it. By returning dummyHead.next, you’re returning the entire chain of ListNodes after the whatever value.
And voila. Hopefully this has been somewhat helpful and not made things even more confusing. Linked lists are slippery little beasts, but if you can get the general rules for working with them down, you can wrangle them okay.
I’m hoping to do more short posts each day about what I learn during my time in Formation, so stick with me! (And also, today I’ve got a mock front-end interview, so if I never return to this blog, just know it’s because I ended up drowning my sorrows and probably also my entire body in a vast pool of Ben & Jerry’s ice cream.)
mins
read
