Linked lists

In brief

Article summary

The main goal of a data structure is to store values and to maintain a certain organisation between them. Among the various strategies for doing this, the linked list is a fairly generic solution. Most high-level languages (such as Python or Java) provide at least one (optimised) implementation of such a data structure. So genereally, never reinvent the wheel and use existing implementations. However, for education purpose, it is interesting to implement a data structure from scratch. In this course we will focus on doubly-linked lists. Two entry points to access the stored values are maintained, one to the last added value and one to the first added value. In addition, you can move from one element of the list to its preceding and succeeding elements. To illustrate the usefulness of such a data structure, consider that you want to store a collection of images in your program to build an image navigator. Doubly-linked lists are particularly relevant in this case, providing the ability to start navigation from the first or last image, and also to navigate forward and backward.

For pedagogical purpose, an implementation (from scratch) of a doubly-linked list is presented on this page.

Main takeaways

• Doubly-linked lists are data structures providing an access to the first and last added elements.

• From each element of the list, one can access its preceding and succeeding elements.

Article contents

1 — What is a doubly-linked list?

A doubly-linked list is a data structure where stored values are chained together. Each stored value is linked to its preceding and succeeding values. As shown in the following figure, two entry points are provided: one to the head of the list and one to its tail.

2 — Primitives

Primitives to manipulate data store in a doubly-linked list are the following:

• initialise – Initialises an empty list.
• insert_at_beginning – Adds an element to the beginning of the list.
• insert_at_end – Adds an element to the end of the list.
• pop_from_beginning – Returns and removes the head element of the list.
• pop_from_tail – Returns and removes the tail element of the list.
• is_empty – Returns true if the list does not contain any data.

A possible implementation of these primitives to manage a doubly-linked list is proposed below. The list and its elements (values + links to the preceding and succeeding elements) are materialised by means of dictionaries, check this short introduction to dictionaries.

Initialising the doubly-linked list and a list element

In the proposed implementation, the initialisation of a doubly-linked list consists in defining a dictionnary having two keys named head and tail. Such a list contains so-called Elements, that are dictionaries containing three keys data, prev and next.

"""
This module provides functions to manipulate a doubly-linked list.
The list is represented as a dictionary with 'head' and 'tail' keys pointing to the first and last Elements, respectively.
Each Element is also represented as a dictionary with 'data', 'prev', and 'next' keys.
"""

from typing import Any, Dict, Optional

# Define the Element structure
Element = Dict[str, Any]

def create_Element(data: Any) -> Element:
    """
    Create a new Element with the given data.

    Args:
        data (Any): The data to store in the Element.

    Returns:
        Element: A dictionary representing the new Element.
    """
    return {'data': data, 'prev': None, 'next': None}

def initialise_list() -> Dict[str, Optional[Element]]:
    """
    Initialise an empty doubly-linked list.

    Returns:
        Dict[str, Optional[Element]]: A dictionary representing the doubly-linked list with 'head' and 'tail' keys.
    """
    return {'head': None, 'tail': None}

def is_empty(dll: Dict[str, Optional[Element]]) -> bool:
    """
    Check if the doubly-linked list is empty.

    Args:
        dll (Dict[str, Optional[Element]]): The doubly-linked list.

    Returns:
        bool: True if the list is empty, False otherwise.
    """
    return dll['head'] is None

/**
 * This class provides methods to manipulate a doubly-linked list.
 * The list is represented with a head and tail pointing to the first and last nodes, respectively.
 * Each node is represented with data, prev, and next fields.
 */

 import java.util.Optional;

 class DoublyLinkedList {
     // Define the Node structure
     static class Node {
         int data;
         Node prev;
         Node next;
 
         Node(int data) {
             this.data = data;
             this.prev = null;
             this.next = null;
         }
     }
 
     private Node head;
     private Node tail;
 
     // Initialise the list
     public DoublyLinkedList() {
         this.head = null;
         this.tail = null;
     }

    /**
     * Check if the list is empty.
     *
     * @return true if the list is empty, false otherwise.
     */
    public boolean isEmpty() {
        return head == null;
    }
     //Continuation here
     //...
 }

Determining if a list is empty is simply a matter of checking that the head is not linked to an item.

Adding data in the list

When it comes to insert a new element in a list, several strategies may be envisaged. It is first considered here that a new element can be added at the head or tail of the list. The crucial point here is to maintain the links between the elements and the references to the head and tail of the list.

def insert_at_beginning(dll: Dict[str, Optional[Element]], data: Any) -> None:
    """
    Insert a new Element with the given data at the beginning of the list.

    Args:
        dll (Dict[str, Optional[Element]]): The doubly-linked list.
        data (Any): The data to store in the new Element.
    """
    new_Element = create_Element(data)
    if dll['head'] is None:
        dll['head'] = dll['tail'] = new_Element
    else:
        new_Element['next'] = dll['head']
        dll['head']['prev'] = new_Element
        dll['head'] = new_Element

def insert_at_end(dll: Dict[str, Optional[Element]], data: Any) -> None:
    """
    Insert a new Element with the given data at the end of the list.

    Args:
        dll (Dict[str, Optional[Element]]): The doubly-linked list.
        data (Any): The data to store in the new Element.
    """
    new_Element = create_Element(data)
    if dll['tail'] is None:
        dll['head'] = dll['tail'] = new_Element
    else:
        new_Element['prev'] = dll['tail']
        dll['tail']['next'] = new_Element
        dll['tail'] = new_Element

    /**
      * Insert a new node with the given data at the beginning of the list.
      *
      * @param data The data to store in the new node.
      */
     public void insertAtBeginning(int data) {
         Node newNode = new Node(data);
         if (head == null) {
             head = tail = newNode;
         } else {
             newNode.next = head;
             head.prev = newNode;
             head = newNode;
         }
     }
 
     /**
      * Insert a new node with the given data at the end of the list.
      *
      * @param data The data to store in the new node.
      */
     public void insertAtEnd(int data) {
         Node newNode = new Node(data);
         if (tail == null) {
             head = tail = newNode;
         } else {
             newNode.prev = tail;
             tail.next = newNode;
             tail = newNode;
         }
     }

Removing data in the list

As for the insertion of new elements, poping the head or tail element requires to pay attention to maintain an access to the remaining content of the list. In practice, the element to remove from the list is still stored in memory, only the references from the adjacent elements are updated.

def pop_from_beginning(dll: Dict[str, Optional[Element]]) -> Any:
    """
    Remove and return the data of the Element at the beginning of the list.

    Args:
        dll (Dict[str, Optional[Element]]): The doubly-linked list.

    Returns:
        Any: The data of the Element removed from the beginning of the list.
    """
    if dll['head'] is None:
        return None
    data = dll['head']['data']
    if dll['head'] == dll['tail']:
        dll['head'] = dll['tail'] = None
    else:
        dll['head'] = dll['head']['next']
        dll['head']['prev'] = None
    return data

def pop_from_end(dll: Dict[str, Optional[Element]]) -> Any:
    """
    Remove and return the data of the Element at the end of the list.

    Args:
        dll (Dict[str, Optional[Element]]): The doubly-linked list.

    Returns:
        Any: The data of the Element removed from the end of the list.
    """
    if dll['tail'] is None:
        return None
    data = dll['tail']['data']
    if dll['head'] == dll['tail']:
        dll['head'] = dll['tail'] = None
    else:
        dll['tail'] = dll['tail']['prev']
        dll['tail']['next'] = None
    return data

  /**
     * Remove and return the data from the node at the head of the list.
     *
     * @return The data from the node at the head of the list, or -1 if the list is empty.
     */
    public int popFromHead() {
        if (head == null) {
            throw new RuntimeException("Empty list");//notion of Exception seen in prog session 
        }
        int data = head.data;
        head = head.next;
        if (head != null) {
            head.prev = null;
        } else {
            tail = null;
        }
        return data;
    }

    /**
     * Remove and return the data from the node at the tail of the list.
     *
     * @return The data from the node at the tail of the list, or -1 if the list is empty.
     */
    public int popFromTail() {
        if (tail == null) {
            throw new RuntimeException("Empty list");
        }
        int data = tail.data;
        tail = tail.prev;
        if (tail != null) {
            tail.next = null;
        } else {
            head = null;
        }
        return data;
    }

To go further

To go beyond

Dynamic data structures, as lists, stacks, queues, trees, etc., rely on links between their elements. These links are called references and concretely correspond to memory addresses indicating where the data (i.e. the elements) are stored in main memory. A reference is a specific value that can be assigned to a variable and that corresponds to an address in main memory. Languages, like C and C++, explicitly involve such a data type whereas it is transparent in Python and Java. Below a link to better understand this pointer data type and its use for building dynamic data structure in languages like C.

• Introduction to pointers.
• A tutorial on linked lists in C