Computer Science 101 - Introduction to Linked Lists

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:

1. 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.
2. 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:

1. 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.
2. 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:

• Linked List - Wikipedia
• Linked List Kata Series on Codewars

* among other things, of course :p

Comments

[Prgrmman]

Just curious if your pseudo code was inspired by Haskell

[Donald Sebastian Leung]

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.

[Prgrmman]

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