Unable to delete the last node in Linked List

Question

This module that I wanted to create was to delete values that are in the linked list, however I can't seem to delete the last value that is in the list. Here is my current code and well as my linked list

(The rest of the elements in the linked list are able to be deleted)

def delete(value):

    global startpointer
    global freepointer


    current = startpointer
    prepointer = -1
    flag = False
    while current != -1 and flag == False:
        if list[current] == value:
            if current == startpointer:
                startpointer = pointer[current]
                list[current] = ""
            else:
                prepointer = current
                current = pointer[current]
                list[prepointer] = ""
            flag = True
        else:
            prepointer = current
            current = pointer[current]



    if flag == False:
        print("your value is not in the list")

if __name__ == '__main__':
    startpointer = 2
    freepointer = 0
    list = ["None","B","A","None","E","D","F"]
    pointer = [3,5,1,-1,6,4,-1]

I do actually know the reason for why I can't delete the last value; It's because my current value will not actually equal to -1. However, I do not know how to fix this issue and it seems I might have to change the entire solution.

Sorry in advance if this solution seems imprudent, I'm new to programming and this is my own solution.

Answer 1

There are several issues in your attempt:

• When you have found the value, it is wrong to set prepointer = current, because now prepointer will reference an index that is no longer part of the data. Instead prepointer should remain unchanged, because after the removal, it should be regarded as the predecessor of the next "current" node.

• When you have found the value, the link from the previous node should be updated, so it no longer points to the deleted node. This can be done with pointer[prepointer] = pointer[current].

• Deleted nodes should be added to the free list, but your code is not doing that. freepointer should be updated to link to the deleted node, and the deleted node should point to the next entry in that free list.

You can deal with these problems by replacing the following code:

        if list[current] == value:
            if current == startpointer:
                startpointer = pointer[current]
                list[current] = ""
            else:
                prepointer = current
                current = pointer[current]
                list[prepointer] = ""
            flag = True

with:

        if list[current] == value:
            if current == startpointer:
                startpointer = pointer[current]
            else:
                # rewire the list to exclude the current node
                pointer[prepointer] = pointer[current]
            list[current] = ""
            # add the deleted node to the free list
            delindex = current
            current = pointer[delindex]
            pointer[delindex] = freepointer
            freepointer = current

            flag = True

This will solve the issues. However, there are still some remarks:

• It is bad practice to use the list name for your own structure, as that is the name of a native function/type. Use another name.

• It is not good practice to use global variables inside your function. Instead, pass the relevant references as arguments, or even better, create a class for your linked list, so these references can be attributes of that class.

• flag is not necessary. You can use break to break out of the loop, or even return out of the function

• Printing a message in a method like delete is not really nice. Better return a boolean to indicate success/failure, and leave it to the caller to print a message if they want to.

• Using "None" looks odd: it would be more natural to use None or the empty string.