Objectives

By the end of this chapter, you should be able to:

• Compare and contrast arrays and singly linked lists
• Diagram inserting and removing from a singly linked list
• Implement insertion, removal, pushing, popping, finding, and accessing an element using a singly linked list

Linked Lists vs Arrays

In the previous chapter we saw how arrays are stored in memory contiguously. That property makes arrays great for accessing elements at an arbitrary index. But we saw that there's a downside with this approach as well: because arrays have to be stored contiguously in memory, in general they are O(n) for operations like remove, insert, and push.

This means that if the size of your data set is going to be changing significantly, an array may not be the best way to store data. In this case, there's another data structure that may be more appropriate: a linked list.

So what's a linked list? A linked list is an ordered list of data, just like an array. The difference between the two is how a linked list is stored in memory. A linked list is not stored contiguously. Instead, a linked list stores the data for a particular index as well as a pointer to the next element in the list.

For example, suppose we had a linked list with the following elements in it: 8, 6, 20, -2. We've already seen that an array would need to store these values contiguously in memory. But a linked list can store the values in any order, provided each memory address contains not only a value, but also a pointer to the memory address containing the next value! In the present example, the list might be stored in memory like this:

Notice that each cell has the data for the element plus a reference to the memory slot for the next element in the list.

If you start with the first element in the list, often referred to as the head, and follow the links to the next element, you will end up with a ordered list, just like an array!

Linked List Advantages, Disadvantages

Advantage - O(1) shift, unshift operations. Since a linked list is not stored contiguously, each node only takes up one memory slot at a time. Therefore, doing operations like shift are always constant time. Moreover, if you keep a reference to the last element (also known as the tail) of the list, pushing is also a constant time operation. And in a doubly linked list, which we'll discuss later, popping is constant time too.

Disadvantage - O(n) element access. A linked list is not stored contiguously and we only have a reference to the head (and possibly the tail) node. That means that finding an element at a specific index requires iterating through the list until that node is reached. This is a O(n) operation, but it is a constant time operation in an array.

Linked List Vocabulary

There are some important vocabulary words to know when using linked lists:

• Node: each element in the list is called a node
• Head: the first element in the list
• Tail: the last element in the list
• Next: usually referring to the pointer to the next node in the list
• Previous: in a doubly linked list, the pointer to the previous element in the list (more on this later)

Singly Linked Lists

Now that we understand how linked lists are stored, let's talk about a type of linked list called a singly linked list. A singly linked list consists of nodes in which each node only has a next pointer. There is a reference to the first node, typically called the head. Optionally a tail reference might also be tracked.

The conceptual diagram below shows how a singly linked list is constructed:

Each node appears in sequential order in the diagram, but in reality the nodes are scattered all over memory (as we learned earlier). The arrow from one node to the next is a pointer that holds a reference to the next element.

A singly linked list node might be created like this in JavaScript:

function Node(val) {
    this.val = val;
    this.next = null;
}

The code below shows how to create the list that was diagramed above:

var head = new Node(30);
head.next =  new Node(-85);
head.next.next = new Node(10);
head.next.next.next = new Node(0);
head.val;  // evaluates to 30
head.next.next.val;  // evaluates to 10

The singly linked list has some drawbacks. For example, if you wanted to access an element that was 2nd to last in the list, you would have to start from the front of the list and iterate through each item. Also, an operation like pop is O(n) because you must iterate from the front to find the element before the last.

To solve some of these problems, you could use a doubly linked list. But let's not get ahead of ourselves. Before learning about a new data structure, let's practice implementing some common methods on singly linked lists.

In the exercises you will also be implementing a constructor function for a SinglyLinkedList along with some common methods on Singly Linked Lists. The constructor function should have a head, tail and length property. You will also be using the Node constructor function from above to add nodes to the list.