How to delete a given node from a linked list using Python

Question

I am trying to learn linked list in Using python,

Could someone please guide me how to delete a particular give node from a linked list?

#!/usr/bin/python                                                                                                                                           

class Node(object):
    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next
    def __str__(self):
        return str(self.data)

def print_list(node):
    while node:
        print node,
        node = node.next
    print

def delete_node(node, node_to_remove):
    if first_node == None:
        return
    pass

# way of creating linked list
def create_linked_list1(n):
    linked_list = Node(1)
    head = linked_list
    for i in range(1, n):
        head.next = Node(i)
        head = head.next
    return linked_list

node1 = create_linked_list1(10)

print_list(node1)

Solution 1

The obvious solution is this:

def delete_by_index(node, index):
    for _ in range(index):
        prev_node, node = node, node.next
    prev_node.next = node.next

However, this won't be able to delete the first node. In order to do that, you need to make it return the new list head, which will normally be the old list head, but will instead be the old second node in the case where you deleted the head. So:

def delete_by_index(node, index):
    if not index:
        return node.next
    head = node
    for _ in range(index):
        prev_node, node = node, node.next
    prev_node.next = node.next
    return head

It should be obvious how to simplify this, and you should do so.

Another option is to factor out the "searching" and "deleting" parts. Write an nth function (this should be easy), then you can do this:

def delete_by_index(node, index):
    if not index:
        return node.next
    prev_node = nth(node, index-1)
    prev_node.next = prev_node.next.next
    return node

If you know about recursive functions, you might also want to figure out how to write either delete_by_index or nth recursively (it's one of the easiest recursive functions to write).

You may also want to trap the error caused by deleting, say, the 15th node of a 10-node list and make it something nicer. Figure out what error you would get in that case (or, if you can't figure it out, just run it and see), then try/except that, and raise an IndexError instead.

While you're at it, you may want to add a delete_by_data(node, data) function and maybe a delete_by_identity(node, child_node) for further practice.

Solution 2

Assume the following singly linked list with a pointer, head, to the first node

head ⇢ n0 → n1 → … → n i - 1 → n i → n i + 1 → … → n N-1 → None

def delete(i):
    if i == 0:                      # there is no prev node, increment head
        head = head.next
    else:
        prev = get_node(i-1)        # find prev node, node[i-1]
        prev.next = prev.next.next  # remove node i

Because this is a singly linked list get_node(i-1) will have to start at head and increment i-1 times to find the node.

NOTE: If this was a doubly linked list, given node[i] you can find node[i-1] using node[i].prev.