IF YOU ARE HERE FOR A PLAIN ENGLISH/JS EXPLANATION OF DATA STRUCTURES AND LINKED LISTS, PLEASE SCROLL PAST INTRODUCTION
Introduction
I'm beginning this series with the intended audience of JavaScript developers emerging fresh from a web development boot camp. Many boot camp graduates are unaware that they already possess the skills necessary to construct the very data structures they may be asked about in interviews. This series is meant to be a guide to translating your hands-on JavaScript skills into the abstract (and needlessly inaccessible!) world of algorithms.
Data Structures
A linked list represents a particular type of a data structure. Both "linked list" and "data structure" are terms coming from computer science. A data structure at it's most simple is a collection of values, the relationships between those values, and the means available to act upon those values. Data structures are built upon the simpler primitive types. An array represents the data structure most familiar to JavaScript developers.
Linked Lists
If arrays are collections of elements (individual data points) in a set order, where each element may be accessed individually by its index, how do linked lists differ? A linked list is a linear collection of nodes. Each node contains two elements, a value and a pointer. (Doubly linked lists have two pointers and will be discussed in a later post.) A node's value is the data point itself, and a node's pointer indicates the next node in the list. The first node in a linked list we call the head, and the final node in a list we call the tail. Here is an example of a linked list, myLinkedList, in the form of a JavaScript object.
const myLinkedList = {
head: {
value: 10,
next: {
value: 15,
next: {
value: 20,
next: {
value: 25,
next: {
value: 30,
next: null
}
}
}
}
}
}
The value associated with each node increments by 5, starting at 10 and ending at 30. The head key indicates the first node in the list. Each node is itself an object with two properties, value and next, next being the pointer. The value of the value property is the data point itself, while the next property's value is a nested object, the next node in the list! This is the "pointing" done by the pointer. The tail of the linked list points to null, indicating the end of the list.
Contrasts with Arrays
First, and most importantly, a given node in a linked list can not be accessed by some given index. To explain this further, consider myLinkedList with the same data points laid out in an array: [10, 15, 20, 25, 30]. If we wanted to access the data point with a value of 25, we might grab its index based on its distance from the start array[3], or knowing it's proximity to the end of the array, we might say array[array.length - 2]. It's almost as if the pointer is built into arrays. You don't need to tell the element after element[0] that it's element[1], it just is. Regardless, there is an index that allows us to grab the individual element. Let's return to myLinkedList. If we wanted to grab the 25 value, we could access it with myLinkedList.head.next.next.next.value. Not only is this cumbersome and impractical (.next.next.next.next . . .), but what if we don't know the contents of a list beforehand, or its length?
Unlike arrays, linked lists must be traversed. This method of navigating through a list will become more clear with demonstration in the next post, when we begin to design a generic singly linked list.
Why Linked Lists Now?
You likely made it through boot camp without once encountering a linked list. Web developers do not often need to be familiar with the nuances of computer science, although data structures certainly mark an element of CS one can expect to confront in engineering interviews.
To most immediately answer the question: Why haven't I done this yet throughout my web dev journey? The point is that this is abstract. That's why you haven't done it and might not have been taught it. What you'll come to see is that you were certainly taught all the tools in boot camp, the matter at hand is properly understanding the task you are assigned.
In the next post, we'll go over using class constructors to design and build our own custom Linked List class.
Top comments (1)
Good read