add_head

Appends an element to the head (start) of the linked list. Begin by creating a ListNode. Store the value and the current head pointer as this node’s next. Point the head pointer to this node.

What happens when you try to add an element?

add_tail

Appends an element to the tail (end) of the linked list. Start by creating a ListNode. Store the value of this pointer and set the next pointer to None. Set the tail’s next to be this node. Set this new node as the new tail.

__getitem__

Returns the element at the current specified position. Unlike arrays, linked lists have a bit of trouble accessing items which are not at the start or the end of the list. Instead, linked lists have to start at the head and access each element one by one until it reaches the desired position. This is because we don’t have references to the nodes in the middle of the list.

To implement this programmatically, start by creating a counter and set this counter to zero. This counter will specify where we are in the list (currently at position zero). Then, create a curr_node specifying which node we’re pointing at in the list. Set the curr_node equal to the head as zero, now we’re at the start of our iteration.

Set a while loop. When our counter is not equal to the desired position, we should set our curr_node equal to our curr_node’s next. Sounds confusing, but this makes it so that our current node is now pointing to the next pointer, essentially moving to the next element.

Increment the counter by one. Once we reach the destination, return the curr_node’s value.

This operation is $O(n)$. Why?

add

Emplaces an element at the specified position. Start by creating a ListNode with the value inside. This is another $O(n)$ operation which requires you to iterate until we reach the desired position - 1 (the -1 here is due to the list being zero-indexed).

The reason why we navigate to the node before our target is because we want to reassign this node’s next pointer to our current node; but not before we store the current next to a temporary variable we call next_element.

We then set our node’s next to next_element.

How would you handle the edge case where our desired position is zero? How about if the desired position is invalid (desired > length)?

pop_head

Removes the element at the start of the list and returns the value. Start by extracting the value of the head and store it to a temporary variable. Reassign the head to the current head’s next. Return the temporary variable.

pop_tail

Removes the element at the end of the list and returns the value. Unlike pop_head, we will need to iterate through the entire list before we can remove the element at the tail. The reason behind this is because we will need to reassign our tail to the new last element.

Unfortunately, because our ListNode only holds the reference to the next element, we are unable to determine which node points to the tail without iterating through the entire list.

Just like the add operation, we will need to query for the node at desired position - 1, which is the position at length - 2(since the last element is always length - 1). Start the counter, set it to zero. Iterate and increment the counter while traversing through the list until we arrive on the node before the tail.

When we find the node before the tail, store the value using a temp variable. Reassign the tail to the node before the tail and return the temp variable. Set this new tail’s next to be None.

pop

Removes and returns the element at a desired index. Start by creating a counter, set it to zero, with the desired value as the target. While iterating, keep track of the previous node using a prev_node pointer. When you arrive at your desired pointer, reassign prev_node’s next to the next of curr_node. Return curr_node’s value.