DEV Community

Colby Sanchez Wagenbach

Posted on

Intro to Singly Linked Lists for the JavaScript Developer

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.

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 = {
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.