Intro to Singly Linked Lists for the JavaScript Developer
Tags: javascript, algorithms, beginners
Published: 2023-03-25 01:48:14

**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.