Linked lists

Immutable linked lists

This is recap from the “Recursion” round of CS-A1120 Programming 2. Immutable linked lists are used in many functional programming languages to store and manipulate sequences of elements. Once created, the lists are not modified: if a list is, for instance, filtered with some predicate, then a new list representing the result is returned and the original list stays unmodified. In Scala, immutable lists are implemented in the class collection.immutable.List.

The idea was simply to have, for each element in the sequence, a list node object that stores (i) the element, and (ii) a reference to the node of the next element in the sequence (for the last element, the reference is either “null” or the next node is a special “Nil” node having no element). In the immutable case, list entries can be shared between different lists.

Example

The figure below shows an object diagram for an immutable linked list l of three integers.

Making a list k that is obtained from l by removing the first element is easy: k is simply the reference to the next nodeof the first node in l.

On the other hand, building the list m obtained from l by adding 11 after 21 requires us to copy the prefix of the list into a new sequence of nodes:

Properties:

Constant-time element insertion and removal in the beginning of the list, provided that allocating the memory for the new list node takes constant time.
Adding elements at the end takes linear time.
Random access, meaning finding the element at an index \(i\), takes linear time. Thus the Scala expression l(i) for a list l can be very slow. And be aware that a Seq can be a List in Scala.

Example: Inefficiency of random access on linked lists

Mutable linked lists

One can also have a mutable version of linked lists. In such lists, the list nodes are not shared between different lists. Furthermore, it is common to have a separate object for maintaining more information:

the reference the first node in the list,
the reference the last node in the list, and
the current list length (note: this is not always done, always check the documentation of the list class before assuming that length of the list can be queried in constant time).

With such additional information, one can add elements both in the beginning and at the end of the list in constant time.

Example: Mutable linked lists

The object diagram of a mutable linked list of three integers:

The same list after adding the element 11 at the end:

A doubly-linked variant of mutable linked lists adds, to each node, a reference pointing to the previous node. Such list can be efficiently traversed in reverse order, and one can also remove elements from the end in constant time.

Example: Mutable doubly-linked lists

A doubly-linked variant of the list in the previous example is shown below.

Given a pointer to a list node anywhere in the list, removing it or adding an element before/after it is also easy due to the forward and backward references.

Example

The simple code below shows how a mutable linked list can be created and modified by using iterators in C++.

#include <iostream>
#include <list>

int main() {
  std::list<int> l;

  for(int i = 1; i <= 5; i++)
    l.push_back(i);

  std::cout << "Before:";
  for(auto v: l) std::cout << " " << v;
  std::cout << std::endl;

  // Remove odd numbers and insert 2*v after each even v
  for(auto it = l.begin(); it != l.end(); ) {
    int v = *it;
    if((v & 0x01) == 1) it = l.erase(it);
    else l.insert(++it, 2*v);
  }
  
  std::cout << "After:";
  for(auto v: l) std::cout << " " << v;
  std::cout << std::endl;

  return 0;
}

The output is

Before: 1 2 3 4 5
After: 2 4 4 8

Mutable linked lists in some standard libraries:

In Scala, ListBuffer implements singly-linked list.
In C++, list implements doubly-linked lists.
In Java, java.util.LinkedList implements doubly-linked lists.