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 entry object that stores (i) the element, and (ii) a reference to the entry of the next element in the sequence (for the last element, the reference is either “null” or the next entry is a special “Nil” entry having no element). In the immutable case, list entries can be shared between different lists.

Example

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

_images/ilist-1.png

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

_images/ilist-1-tail.png

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 entries:

_images/ilist-2.png

Properties:

  • ​ Constant-time element insertion and removal in the beginning of the list, provided that allocating the memory for the new list entry takes constant time.

  • ​ Adding elements at the end takes linear time.

  • ​ Random access, ie. 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.

Mutable linked lists

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

  • ​ the reference the first entry in the list,

  • ​ the reference the last entry 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:

_images/list-1.png

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

_images/list-3.png

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

Example: Mutable doubly-linked lists

A doubly-linked variant of the list in the previous example:

_images/dlist-3.png

Given a pointer to a list entry 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.