When you are learning to program, right after the initial print hello world and learn how to handle primitive data types (integer, booleans, strings), you will progress into learning the composite data types, and the most fundamental is the “list”.
When you start your journey as a coder, you tend to tie your knowledge to a particular computer language that you are learning, but if you learn the programming concepts dissociated from any language, not only you will have a better understanding of how it works but also you will to be able to easily switch between multiple languages.
A “list” and “linked lists” are abstract data types, that is, they represent a collection of data which hold certain properties and aren’t dependent on specific implementation in any computer languages.
To have a better understanding of what it means for a list to be an abstract data type: a list can be a yellow post-it stuck on the fridge with the stuff that needs to be bought as well as a lineup of cars at a factory ready for production. Although the previous examples look quite different, both of them can be represented by a list within a computer program, since both are sequences of elements.
To make things more confusing in some computer languages, it’s called lists to arrays, making it hard for learners to understand, and this article will decrypt this computer jargon.

Lists

In computer science, a list is a collection of elements stored in a sequence.
It sounds very generic, because it is, later as we will delve into specific types of lists, it will become clear.

The key points regarding lists are:

  • The elements must be arranged in a series and not in parallel.
  • Unlike primitive data types, lists can hold multiple elements.


That is, to be considered a list it must allow you to store an element, followed by another element, and then another element, and so one, always one in front of the other.

A list can:

  • Have no elements, in this case, it’s called an empty list.
  • Have only one element, in this case, it’s still a list but it’s represented in a different manner from a primitive data type.

Example in php of a primitive type vs a list with one element.

$i = 5;     // $i variable hold number 5.
$l = [5];   // $l is a list with only the number 5.

In the image below are represented different types of lists:

  • A continuous sequence of elements of the same data type, in this case of integer values.
  • A continuous sequence of elements of different data types, in this case an integer value, followed by text, and then a date and then number with decimal digits, known as a float.
  • A sequence of elements connected to the next one by a link, also known as a pointer. In this case, it’s a linked list explained on the Linked Lists section.


In the image below, none of the diagrams represents a list because:

  • element 56 has two child elements, in this case it’s a tree, not a list. Don’t mistake it with a doubly linked list where an element is connected to the previous element and the next element.
  • The element 20 is connected to element 30 and vice-versa, but 20 doesn’t have a double connection to 10.
  • element 15 isn’t connected to element 67 nor to element 89.


👉️ Usually, lists are represented in diagrams as a single horizontal row of squares.
While other structures such as trees and graphs are represented in two dimensions.

Arrays

An array is an implementation of a list where each element or its key occupies the same memory size.

Pros:

  • An array has random access to each element.
  • It’s the composite data structure with the fastest access to any element.

Cons:

  • Insert and remove requires reallocating the entire array, and in the case of insert it can require creating a temporary copy of the array during the process.

Arrays with Fixed-Length Elements

In statically typed languages such as Java, C and Rust, it’s possible to have arrays with fixed-length elements for certain primitive data types (integer, floats, booleans).
In this case, each element occupies exactly the same amount of memory.

Pros:

  • It’s the implementation that requires less memory.
  • It’s the fastest to access data.

Cons:

  • Doesn’t support elements of different data types.
  • Doesn’t support textual elements.


👉️ In most languages, arrays start with index 0.
However, in some languages such as R, arrays start with index 1.
In Pascal it can be defined as the lower index.

In the image above, it's an array with 4 elements on a 64-bit processor.
In the following Java code:
public class Main {
    public static void main(String[] args) {
        int[] numbers = {54, 130, 5, 18};
        int element = numbers[2];
        System.out.println("Element at index 2: " + element);
    }
}


How it works:
Internally the processor will multiply the index number by the number of bytes required to represent the data type.
In the example depicted in the image above , it will retrieve data from memory position 8 (=2*4) to 11 (2*4 + 3).

The same example as above in C:
#include <stdio.h>

int main() {
    int numbers[] = {54, 130, 5, 18};
    int element = numbers[2];
    printf("Element at index 2: %d\n", element);
    return 0;
}

👉️Although Python lists and JavaScript arrays don’t support fixed-length elements, in both of these languages it’s possible to have these types of arrays using the arrays package in Python, and SharedArrayBuffer in JavaScript.

Arrays with Variable-Length Elements

Languages that aren’t statically typed languages such as Python, JavaScript and PHP, the arrays can have elements of different data types, known as mixed-type arrays, for this case it requires a different implementation.
Also in case of statically typed languages when handling arrays of text, it’s not possible to have the same implementation as before since text will vary in length.
Since the fundamental property of arrays is to have random access to each element, the implementation is done by still having an array as previously but instead of holding the data itself, each element will be a pointer to a memory containing the actual element.
Some languages have a more complex mechanism such as PHP but it’s beyond the scope of this article.

Pros:

  • Support for mixed-type elements.
  • Support for textual (strings of text) elements.

Cons:

  • It requires more memory than arrays with fixed-length elements.

Array examples

Examples of using arrays in JavaScript, Python and PHP

let numbers = [54, 130, 5, 18];
let element = numbers[2];
console.log("Element at index 2:", element);

# List in python are arrays of multiple data types
numbers = [54, 130, 5, 18]
element = numbers[2]
print("Element at index 2:", element)

👉️ In Python, the default arrays are called lists.

<?php
$numbers = [54, 130, 5, 18];
$element = $numbers[2];
print("Element at index 2: $element\n");

Fixed Arrays vs Dynamic Arrays

When it comes to the number of elements in arrays, they can have a fixed number called Fixed Arrays or can grow or shrink in the number of elements, in this case called Dynamic Arrays.
In languages such as C and Java, the default arrays are fixed Arrays, however, both in these languages as well as any other language, there is a possibility to create Dynamic Arrays outside the default array mechanism provided.

In Java code example bellow:

  • It created a fixed array named ratings of two integers.
    In this case, it’s possible to read and change the values but not grow or shrink.
  • It created an empty dynamic array named stars and then added more and afterwards removed the last element.

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        // Fixed-size array
        int[] ratings = {24, 56};
        // Dynamic array using ArrayList
        ArrayList<Integer> stars = new ArrayList<>();
        stars.add(24);  // Append 24
        stars.add(56);  // Append 56
        stars.remove(stars.size() - 1); // Removes the last element
    }
}

Linked Lists

While arrays allow fast access to any element within the array, for every insert and remove it requires for the entire array to shrink or grow and for large arrays this can be a computational expensive operation.
For the cases where the random access isn’t required, such as iterations and for operations that heavily depend on insert and remove, linked lists provide a viable alternative.

A linked list represents a collection of data where each element contains 2 fields: the value and the pointer (or reference)  to the next element.

Pros:

  • Allows fast insert and removal of elements.

Cons:

  • It doesn’t allow random access to each element.
  • To insert/remove an element might require a pointer/reference of the previous element.


The variable holding the linked list is a pointer for the first element. To retrieve the next element, we fetch the next field, and keep iterating until reaching the last element.
Typically it’s used two variables, one for the first element and other as an iterator.

Inserting elements

When it comes to insert an element in a linked list, there are 3 cases:

  1. It’s the first element - the next field of the new element, will point to the old first element, and the variable will point to the new element.
  2. It’s after the current element - the next field of the current element  will point to the new element, and the next field of the new element will point to the previous next field of the current element.
  3. It’s before the current element - in this case, it requires that when you iterate it must have a variable to the previous element, and then it uses the same process as defined in point 2. Using doubly linked lists, it avoids this problem.


In the Python code bellow:

  • The Node class represents an element structure within a LinkedList.
  • The root is the first element.
  • The current is the third element and previous the element before, in this case is the second element.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

# Assuming that root is the first element
current = root # current is now the first element
current = current.next # current is now the second element
previous = current  # previous is also the second element
current = current.next # current is now the third element

# 1. Insert as the first element
new_node = Node(10)

new_node.next = root # root is the previous element
root = new_node

# 2. Insert after the current element
new_node = Node(20)
new_node.next = current.next # current is any element within the linked list
current.next = new_node

# 3. Insert before the current element
new_node = Node(5)
new_node.next = current
previous.next = new_node # previous is an element pointing to current element.

Removing elements

Removing elements also has three cases just like inserting elements but with a few tweaks.

  1. It’s the first element - the new root will point to the current root.`next`.
  2. It’s after the current element - the next field of the current element will point to the next of the next of the current element.
  3. It’s before the current element - the next field of the previous element will point to the next of the current element.

# 1. Remove the first element
root = root.next

# 2. Remove after the current element
current.next = current.next.next

# 3. Insert before the current element
previous.next = current.next

Doubly linked list

A doubly linked list is a variation of a linked list where instead of a single pointer to the next element, it will also have a pointer usually called previous pointing to the previous element.

Pros:

  • Allows iteration in both directions.
  • Inserting before element N doesn’t require an extra variable.

Cons:

  • It requires managing an extra pointer during insert and remove operations.

Inserting elements

This example is similar to the Python code on the Linked Lists but in this case, it’s no longer necessary to use an extra variable named previous.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None
        self.prev = None  # Adds the `prev`` pointer

current = root # current is now the first element
current = current.next # current is now the second element
current = current.next # current is now the third element
# previous variable isn't required

# 1. Insert as the first element
new_node = Node(10)
new_node.next = root
root.prev = new_node  # Set the previous of the current root to the new node
root = new_node

# 2. Insert after the current element
new_node = Node(20)
new_node.next = current.next
if current.next:
    current.next.prev = new_node
current.next = new_node
new_node.prev = current

# 3. Insert before the current element
new_node = Node(5)
new_node.next = current
new_node.prev = current.prev
current.prev = new_node

Removing elements

Removing elements in doubly linked lists just like inserting elements doesn’t require an extra variable but it requires updating the prev field.

# 1. Remove the first element
root.next.prev = None
root = root.next

# 2. Remove after the current element
current.next.next.prev = current
current.next = current.next.next

# 3. Remove before the current element
current.prev.prev.next = current
current.prev = current.prev.prev