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 (optimized) implementation of such a data structure. So generally, never reinvent the wheel and use existing implementations. However, for education purpose, it is interesting to implement a data structure from scratch, as we will do in this article

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.

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

Operations to manipulate data stored in a doubly-linked list are the following:

• initialize – Initializes 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 materialized by means of dictionaries (check this short introduction to dictionaries).

2.1 — Initializing the doubly-linked list and a list element

In the proposed implementation, the initialization of a doubly-linked list consists in defining a dictionary having two keys named head and tail. Such a list contains so-called “elements”, that are dictionaries containing three keys: data, prev and next.

Let’s define a few functions:

"""
    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.
"""

# Needed imports
from typing import Any, Dict, Optional

# Create your own custom type
Element = Dict[str, Any]



def create_element (data: Any) -> Element:

    """
        Creates a new element with the given data.
        In:
            * data: The data to store in the element.
        Out:
            * A dictionary representing the new element.
    """

    # Return the new element
    return {'data': data, 'prev': None, 'next': None}



def initialize () -> Dict[str, Optional[Element]]:

    """
        Initializes an empty doubly-linked list.
        In:
            * None.
        Out:
            * A dictionary representing the doubly-linked list, with 'head' and 'tail' keys.
    """

    # Initialize the default pointers
    return {'head': None, 'tail': None}



def is_empty (dll: Dict[str, Optional[Element]]) -> bool:

    """
        Checks if the doubly-linked list is empty.
        In:
            * dll: The doubly-linked list.
        Out:
            * True if the list is empty, False otherwise.
    """

    # Check if the head pointer is uninitialized
    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.

2.2 — Adding data to the list

When it comes to inserting a new element in a list, several strategies may be envisioned. 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.

Let’s complement the code above with both options:

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.
        In:
            * dll:  The doubly-linked list.
            * data: The data to store in the new element.
        Out:
            * None.
    """

    # Create the element to store
    new_element = create_element(data)

    # Adapt the pointers
    if dll['head'] is None:
        dll['head'] = new_element
        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.
        In:
            * dll:  The doubly-linked list.
            * data: The data to store in the new element.
        Out:
            * None.
    """

    # Create the element to store
    new_element = create_element(data)

    # Adapt the pointers
    if dll['tail'] is None:
        dll['head'] = new_element
        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;
         }
     }

2.3 — 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.

Let’s add removing functions in our code:

def pop_from_beginning (dll: Dict[str, Optional[Element]]) -> Any:
    
    """
        Removes and returns the data of the element at the beginning of the list.
        In:
            * dll: The doubly-linked list.
        Out:
            * The data of the element removed from the beginning of the list.
    """

    # Verify it is not empty
    if is_empty(dll):
        return None
    
    # Extract the data
    data = dll['head']['data']

    # Adapt the pointers
    if dll['head'] == dll['tail']:
        dll['head'] = None
        dll['tail'] = None
    else:
        dll['head'] = dll['head']['next']
        dll['head']['prev'] = None
    
    # Return the data
    return data



def pop_from_end (dll: Dict[str, Optional[Element]]) -> Any:

    """
        Removes and returns the data of the element at the end of the list.
        In:
            * dll: The doubly-linked list.
        Out:
            * The data of the element removed from the end of the list.
    """

    # Verify it is not empty
    if is_empty(dll):
        return None

    # Extract the data
    data = dll['tail']['data']

    # Adapt the pointers
    if dll['head'] == dll['tail']:
        dll['head'] = None
        dll['tail'] = None
    else:
        dll['tail'] = dll['tail']['prev']
        dll['tail']['next'] = None

    # Return the data
    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

3 — Pointers

Dynamic data structures, such 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 or C++ explicitly involve such a data type, whereas it is transparent in Python and Java. This data type is called a “pointer”.

To go beyond

• Pointer (computer programming).

  The Wikipedia page on pointers in computer programming.

• Linked lists.

  A tutorial on linked lists in C.