What methods can be used to delete an element from a linked list in constant time?

Removing an element from a linked list in constant time is possible if you have a pointer directly to the node to be removed and, in the case of a singly linked list, to the previous node. Consider the options:

1. Doubly linked list: In a doubly linked list, each node contains references to the previous and next nodes. If you have a pointer to the node to be deleted, you can do it in O(1):

   • change the "next" pointer of the previous node,
   • change the "prev" pointer of the next node,
   • free the memory.

2. Singly linked list: To delete a node in O(1), you need a pointer to the previous node to redirect its "next" to the node after the one to be deleted. If you don't have a pointer to the previous node, you'll need to traverse the list, which takes O(n).

3. Deletion without a pointer to the previous node (only for non-last nodes): You can copy data from the next node into the current node and delete the next node, which effectively deletes the current node in O(1), but this is not possible for the last node.

Example in Python for a doubly linked list:

class Node:
    def __init__(self, val):
        self.val = val
        self.prev = None
        self.next = None

def delete_node(node):
    if node.prev:
        node.prev.next = node.next
    if node.next:
        node.next.prev = node.prev
    # node is now removed from the list

Thus, the key to O(1) deletion is having direct access to the node to be deleted and, if necessary, to its neighbors.