Data Structures: Linked Lists

Linked lists are a common data structure you may receive questions on during a job interview. Let's take a look at what a linked list is at a high level.

What is it?

A linked list is a list of elements (which we'll refer to as nodes) that store some data, as well a pointer (or pointers) to other nodes in the list. This pointing is what creates the list. There are two major types of linked lists: singly and doubly linked lists.

In a singly linked list, each node only knows about the next node in the list. When we reach the last node it points to null. For doubly linked lists each node knows about the previous and next node in the list. This allows traversing of the list forwards and backward, whereas singly linked can only be traversed forwards.

Singly Linked List

Doubly Linked List

Why do this?

Why do we need a linked list when we already have array's built right into JavaScript? Great question, I wondered the same. The major difference between the two is how they are stored in memory. Let's take a look at the pros/cons of each.

Arrays

Arrays elements are stored in contiguous memory locations. Meaning that their elements are stored all in a row.

Linked Lists

Linked lists do not need to be stored in contiguous locations. Due to each node storing the location of the next node, they can be stored anywhere.

Arrays

Pros:

• Random access: since arrays store elements contiguously, accessing an element at a given index is much quicker. (ex. array[3]). No need to traverse the elements, we already know its location.
• Less memory per element: an element in an array does not need to store the location of the next element.

Cons:

• Insertion/Deletion: is much slower because arrays use contiguous memory, adding a new element requires shifting the memory locations of other elements to make room.
• Static Memory Allocation: memory for an array takes place at compile time. It can not be altered dynamically at runtime because that may result in overwriting data.

Linked Lists

Pros:

• Insertion/Deletion: since linked lists use non contiguous memory, these operations are much faster. There's no need to shift anything around, just update where the nodes point.
• Dynamic Memory Allocation: new nodes can be inserted at runtime as soon as they are created.

Cons:

• Sequential Access: finding a given index of a linked list requires traversing the list up to that point, this is much slower than the random access of an array.
• Increased storage: linked list nodes need to store the location of the next node. This increases the storage used per element.

TL;DR

A linked list is a data structure of elements we refer to as nodes. Each node stores the location of the next and this creates a list. While similar to an array it has the advantages of faster insertion/deletion, and can be modified dynamically at run time. The disadvantages in comparison are slower access and increased storage usage, due to each node storing the location of the next.