7.5 Removing Nodes from a Linked List

An item can be removed from a linked list by removing or unlinking the node containing that item. Consider the linked list from the previous section and assume we want to remove the node containing 18.

First, we must find the node containing the target value and position an external reference variable pointing to it

After finding the node, it has to be unlinked from the list, which entails adjusting the link field of the node's predecessor to point to its successor. The node's link field is also cleared by setting it to None. The two steps required are illustrated below:

Accessing the node's successor is very simple using the next link of the node. But we must also access the node's predecessor in order to change its link. The only way we can do this is to position a second external reference simultaneously during the search for the given node

The result after removing the node containing value 18 is shown below:

Removing the first node from the list is a special case since the head pointer references this node. There is no predecessor that has to be relinked, but the head reference must be adjusted to point to the next node, as illustrated below.

We now step through the code required for deleting a node from a singly linked list. The curNode external reference is initially set to the first node in the list, the same as is done in the traversal and search operations. The predNode external reference is set to None since there is no predecessor to the first node in the list.

predNode = None

curNode = head

A loop is used to position the two temporary external reference variables

while curNode and curNode.data != target : 

  predNode = curNode

  curNode = curNode.next                    

As the curNode reference is moved along the list by the statements in the body of the loop, the predNode reference follows behind. Thus, predNode must be assigned to reference the same node as curNode before advancing curNode to reference the next node.

After positioning the two external references, there are three possible conditions: (1) the item is not in the list; (2) the item is in the first node; or (3) the item is somewhere else in the list. If the target is not in the list, curNode will be null, having been assigned None@ via the link field of the last node. This condition is evaluated by an if statement

if curNode is not None :           

  # the target was found

To determine if the target is in the first node, we can simply compare curNode to head and determine if they reference the same node. If they do, we set head to point to the next node in the list

  if curNode is head :  

    head = curNode.next 

  else :           

    predNode.next = curNode.next

If the target is elsewhere in the list, we simply adjust the link field of the node referenced by predNode to point to the node following the one referenced by curNode. This step is performed in the else clause of the condition as shown above. If the last node is being removed, the same code can be used because the next field of the node pointed to by predNode will be set to None since curNode will be null. We combine the code from above to create the complete implementation for finding and removing a node from a singly linked list is provided below.

# Given the head reference, remove a target from a linked list.

predNode = None

curNode = head

while curNode and curNode.data != target : 

  predNode = curNode

  curNode = curNode.next                    

if curNode is not None :           

  if curNode is head :  

    head = curNode.next 

  else :           

    predNode.next = curNode.next

Question 7.5.1

Does the code segment above for removing a node from the linked list have a best case? If so, when does the best case occur and when does the worst case occur?

Yes. The best case occurs when the head node is removed from the list. The worst case occurs when the last node is removed from the list.

Question 7.5.2

What is the worst case time-complexity for removing a node from a linked list?

Select the correct answer below by clicking on the appropriate box.

O(1)
O(log n)
O(n)
O(n²)

The worst case occurs when the last node is removed. Since we do not have direct access to that node, the loop must iterate through the entire linked list, once for each node in the list. Assuming the linked list contains n nodes, the worst case time-complexity will be linear or O(n).

Question 7.5.3

What is the best case time-complexity for removing a node from a linked list?

Select the correct answer below by clicking on the appropriate box.

O(1)
O(log n)
O(n)
O(n²)

The head node can be removed in constant time since the target will be found immediately and the loop never executes. Unlinking the node only requires constant time.

7.4 Prepending Nodes to a Linked List

Chapter 7. Linked Structures

7.6 Revisiting The Bag ADT