Linked List

4.5. Linked List#

A linked list is a data structure to hold a sequence of elements.

4.5.1. Recommended Video (10 minutes)#

4.5.2. Concept#

Linked lists are a recursive array type, which consist of linked nodes. Each node:

contains the data at the given position in the list
a reference to the next node

The first node is called the head node. The end of the linked list is indicated by a node not containing a valid reference to another node i.e. has the value of None.

This is visualised in the diagram below.

4.5.3. Time Complexity#

Compared to other data types, linked lists allow for fast insertion or removal at the start of the list.

Access

To access an element at a given index, i, we must go through each node in turn until we reach node i. A sketch of this process is below:

count = 0
current_node = head
while count < i:
    current_node = current_node.next
    count = count + i

Therefore to access an element at index i it takes i operations. The average time complexity is given by the time taken for each value of i i.e.

\[\frac{1 + 2 + \dots + n}{2} = \frac{(n(n+1)/2)}{n} = \frac{n+1}{2} = O(n)\]

In the above calculation we have shifted indices by :math:`+1` to make use of the formula for the sum of natural numbers.

Search

Searching is the same process as accessing in a linked list, except instead of counting we perform the comparison on each node in turn.

Insertion and Deletion

In our analysis we ignore the process of finding the position to insert or node to delete, because has the same cost as a list or array.

Inserting and deleting elements from a linked list only requires updating the next value of a node. Therefore it has time complexity \(O(1)\).

To insert at position i we do the following:

Traverse to node i-1, call this previous_node
Create a new node called new_node set it’s next node to previous_node.next
Set previous_node.next = new_code

To delete at position i we do the following:

Traverse to node i-1, call this previous_node
Traverse to node i+1, call this next_node
Set previous_node.next = next_node

4.5.4. Space Complexity#

A linked list only requires one node per element in the list. The nodes only require the given data value and a reference to the next node i.e. \(2 \times n\) pieces of data. This simplifies to \(O(n)\).

Code Challenge: Linked List

Using the Node class from the Nodes example, complete the provided LinkedList class.

LinkedList Specifications

Attributes

head, a reference to the first element in the list

Methods

retrieve(self, index), return element at position index
prepend(self, data), add data to the start of the list and return None
append(self, data), add data to the end of the list and return None

Instructions

Note

Look for the TODO items in the provided code!

Copy and paste the Node implementation from the Nodes example to the top of the script
Complete the prepend method:
- Create a new node with the data and next = head
- Set the head of the linked list to the new node
Complete the append method:
- When the list is empty set the head to the new node
- Otherwise set the last node’s next value to the new node

Usage Example
>>> names = LinkedList()
>>> names.append("Bill Gates")
>>> names.append("Steve Jobs")
>>> print(names.retrieve(1))
Steve Jobs

Here is some code for you to start with:

class Node():

    # TODO: Add your Node class implementation here

class LinkedList():

    def __init__(self):
        self.head = None

    # Get element at index
    def retrieve(self, index):
        counter = 0
        current = self.head

        # Until we reach index or end of the list
        while current != None and counter < index:
            current = current.next
            counter += 1

        # If end of list reached before i
        if current == None:
            return None

        # Otherwise return the data
        return current.data

    # Add element to the start of the list
    def prepend(self, data):
        # TODO:
        # 1. Create a new node with the data and next = head
        # 2. Set the head to the new node

    # Add element to the end of the list
    def append(self, data):

        new_node = Node(data, None)

        current = self.head

        # If list is empty
        if current == None:
            # TODO: Set head to the new node

        # List not empty
        else:
            # Until we reach the end of the list
            while current != None:
                prev = current
                current = current.next

            # TODO: Set prev.next to the new node


# Test code
names = LinkedList()

names.append("Turnbull")
names.append("Morrison")

names.prepend("Albanese")

print(names.retrieve(1))