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.

  • ​ Random access, ie. finding the element at an index \(i\), takes linear time.

  • ​ Adding elements at the end takes linear time.

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 some addional information: (i) the reference the first entry in the list, (ii) the reference the last entry in the list, and (iii) the current list length. With such additional information, one can add and remove elements both in the beginning and at the end of the list in constant-time. Furthermore, finding out the size of the list is easy as well.

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 as well.

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.