If you've done any programming before, chances are that you've stumbled upon the term "linked list" at least once. And if you're a Computer Science major who has completed at least one semester at university, you should probably be deeply familiar with them by now. But for those of you with no prior Computer Science background, this article aims to introduce you to the concept of "linked lists" and how to work with them. So what are they, why are they important and how can we work with them?

A linked list is basically one of many possible ways to represent a sequence of items. For example, if you have a list of numbers `1, 3, 2`

, there are at least two (standard) ways you could represent it in your program - 1) by using an array (which you should already know) or 2) by using a linked list. Anyway, a linked list is special in that it is a *recursive* data type, i.e. it can be defined in terms of itself, and a typical definition is as follows:

- Base case - Let an empty linked list be one that denotes a sequence of
`0`

elements. This is usually defined as`null`

/`nil`

/`NULL`

/etc. in most programming languages. - Recursive case - Let any non-empty linked list be a
`Node`

(an entry in our list) that contains a head element`data`

and a tail which is the rest of the linked list - we'll call our tail`next`

.

So the empty linked list would simply be denoted as `NULL`

and our list `1, 3, 2`

of integers (in that order) could be represented by:

```
oneThreeTwo : Node // oneThreeTwo is a Node, i.e. a linked list
oneThreeTwo =
data: 1
next:
data: 3
next:
data: 2
next:
NULL
```

Note that the "tail" (i.e. the `next`

field) of `oneThreeTwo`

is itself a linked list:

```
threeTwo : Node
threeTwo = tail oneThreeTwo // or threeTwo = oneThreeTwo.next
// threeTwo =
// data: 3
// next:
// data: 2
// next:
// NULL
```

And so is the tail of `threeTwo`

(a list containing a head element `2`

with its tail being `NULL`

) as well as the tail of `tail threeTwo`

(which is just `NULL`

, a linked list itself by definition). *N.B.* `NULL`

*is also trivially considered a* `Node`

*albeit a special one.*

By now you should be wondering why we aren't using an array instead. After all, arrays seem much simpler to define without all that recursion and jargon. This is because linked lists offer multiple advantages over plain arrays in certain situations:

- Prepending an element to an existing linked list is trivial and efficient - you just have to define a new
`Node`

containing the given element whose tail or`next`

field is the original linked list. In contrast, prepending an element to an array requires all previous elements to shift rightward by one place in most implementations which could be time-consuming. - The length of a linked list is automatically encoded in its definition; in contrast, array implementations in most programming languages require a separate number to be stored alongside the sequence of items (though they usually hide this implementation detail from the programmer)

Speaking of which, here could be a pseudocode example of how `prepend`

is defined (which prepends a single element to an existing list):

```
prepend : (T, Node) -> Node // prepend takes an item of type T (if such
// a type needs to be specified) and an existing list, returning a new list
prepend (elem, list) =
data: elem
next:
list
```

... and `length`

can be defined recursively as such:

```
length : Node -> Size // length takes a linked list and returns a number
// representing its length/size in terms of number of elements
length list
= 0 if list == NULL
= 1 + length list.next otherwise
```

What the above code example means is that if `list`

is the empty list (denoted by `NULL`

in most cases) then it has `0`

items. Otherwise, it is not empty and the number of items is exactly `1`

greater than the number of items in the rest of the list (`list.next`

/ `tail list`

).

There are many more possible operations that can be defined on linked lists (such as transforming every element of a linked list recursively using a custom-defined mapping function, filtering items in a linked list by a predicate, sorting elements of a linked list in ascending order, etc.) but we will not discuss them in this post. We will conclude the following post with a non-exhaustive list of real-world use cases of linked lists:

- Many efficient stacks are represented internally as a linked list
- Queues can also be implemented efficiently using a clever wrapper around a linked list - more of that in future posts (maybe ;)
- Double-ended queues aka "deque"s (a generalization of stacks and queues) can be implemented efficiently using a wrapper around a doubly-linked list (a special type of linked list not covered in this post)
- Hash tables / associative arrays (e.g. java.util.HashMap, Python dictionaries, Ruby hashes) could be implemented as an (growable) array of linked lists (though the term "buckets" is usually used in favor of "array")

And here comes the shocker - **Blockchains** (yes, *that* Blockchain powering many modern cryptocurrencies) are basically glorified linked lists (with a security feature called "hashing")! So if you master linked lists*, you *might* just be able to make a lot of money ;)

I hope this article gave you a brief overview of what linked lists are and why they are useful - feel free to share your thoughts in the comments :D

External resources:

* among other things, of course :p

Posted on Aug 25 '18 by:

### Donald Sebastian Leung

A Year 2 Computer Science and Engineering undergraduate at The Hong Kong University of Science and Technology

## Discussion

Just curious if your pseudo code was inspired by Haskell

Indeed it was, good observation :) I didn't want to provide code examples that worked straight out of the box in any language (for fear of spoiling online code challenges) so I just kinda mixed in a bit of JavaScript-ish notation with Haskell-like syntax.

Nice! That was pretty clever. It was kind of cool to see them explained from a functional point of view.