Linked List

  For more information, see Linked list on Wikipedia. A linked list is a data structure representing a sequence of values, like a list in Scratch, but made of a sequence of nodes which could be located in arbitrary parts of memory and each of which contains an item.

Purpose

Linked lists are useful because they support the efficient insertion and removal of elements at the expense of inefficient element access, as opposed to arrays.

• Element access: $O(n)$
• Insertion: $O(1)$
• Deletion: $O(1)$

When a variable is created, the computer must allocate memory. When an array is created, the computer needs to find contiguous memory locations for each element, because they are stored next to each other. As a result, any element of the array can be accessed by simply adding the index to a pointer (a memory address) to the beginning of the array. However, if the array is to be resized, the computer would have to allocate another chunk of memory and move all of the array's elements to the new location.

A linked list sacrifices the random element access for more efficient insertion and deletion. In a linked list, the elements are not stored in contiguous memory locations. Each node has a pointer to the next node in the list, as well as possibly the previous node. The linked list keeps a pointer to the first node and possibly the last node.

Operations

In order to get an element, the program must follow the "chain" of pointers from the first node to the wanted node. The time complexity of this operation is $O(n)$, meaning that the number of instructions to be executed has a linear relationship with the input.

Given the address of the previous node, in order to insert an element, one must construct a new node and make it "point" to the node that the previous node points to. Then, the previous node must point to the newly inserted node instead. If the nodes also point to the previous node, those pointers need to be adjusted as well.

One can delete an element by recording its address, making the previous element point to the element after the element to be deleted, and finally delete the element.

Scratch Implementation

This block constructs a new linked list and stores its memory address in (new LinkedList):

define LinkedList
add [null] to [LinkedList.front v]
add [null] to [LinkedList.back v]
add [0] to [LinkedList.size v]
set [new LinkedList v] to (length of [LinkedList.begin v])

The following block constructs a new node:

define Node (value) (prev) (next)
add (value) to [Node.value v]
add (prev) to [Node.prev v]
add (next) to [Node.next v]
set [new Node v] to (length of [Node.value v])

The block below gets the address of a node. It is optimized to start from the front or the back such that less steps are taken.

define at (this) (n)
if <(n) < ((item (this) of [LinkedList.size v]) / (2))> then
    set [return v] to (item (this) of [LinkedList.front v])
    repeat (n)
        if <(return) = [null]> then
            stop [this script v] // Index out of bounds
        end
        set [return v] to (item (return) of [Node.next v])
    end
else
    set [return v] to (item (this) of [LinkedList.back v]
    repeat (((item (this) of [LinkedList.size v]) - (n)) - (1))
        if <(return) = [null]> then
            stop [this script v]
        end
        set [return v] to (item (return) of [Node.prev v])
    end
end

The following block inserts a new element, where (node :: custom-arg) is the address of the node the new node should follow:

define insert (this) (node) (value)
new Node (value) (node) (item (element) of [Node.next v]) :: custom
if <(item (node) of [Node.next v]) = [null]> then // The inserted element is the last element
    replace item (this) of [LinkedList.back v] with (new Node)
else
    replace item (item (node) of [Node.next v]) of [Node.prev v] with (new Node) // Make the node after the inserted node point to it
end
replace item (node) of [Node.next v] with (new Node)
replace item (this) of [LinkedList.size v] with ((item (this) of [LinkedList.size v]) + (1))

This block deletes an element:

define delete (this) (node)
if <(item (node) of [Node.prev v]) = [null]> then
    replace item (this) of [LinkedList.front v] with (item (node) of [Node.next v]) // The element is the first one
else
    replace item (item (node) of [Node.prev v]) of [Node.next v] with (item (node) of [Node.next v])
end
if <(item (node) of [Node.next v]) = [null]> then
    replace item (this) of [LinkedList.back v] with (item (element) of [Node.prev v]) // The element is the last one
else
    replace item (item (node) of [Node.next v]) of [Node.prev v] with (item (node) of [Node.prev v])
end
replace item (this) of [LinkedList.size v] with ((item (this) of [LinkedList.size v]) - (1))

Finally, these two blocks are able to add elements at the front and back respectively:

define push_front (this) (value)
new Node (value) [null] (item (this) of [LinkedList.front v]) :: custom
if <not <(item (this) of [LinkedList.front v]) = [null]>> then
    replace item (item (this) of [LinkedList.front v]) of [Node.prev v] with (new Node)
end
replace item (this) of [LinkedList.front v] with (new Node)
replace item (this) of [LinkedList.size v] with ((item (this) of [LinkedList.size v]) + (1))

define push_back (this) (value)
new Node (value) (item (this) of [LinkedList.back v]) [null] :: custom
if <not <(item (this) of [LinkedList.back v]) = [null]>> then
    replace item (item (this) of [LinkedList.back v]) of [Node.next v] with (new Node)
end
replace item (this) of [LinkedList.back v] with (new Node)
replace item (this) of [LinkedList.size v] with ((item (this) of [LinkedList.size v]) + (1))