title: Why isn't deletion O(1) in both Singly Linked Lists and Doubly Linked Lists, when given the node to delete?
body: <p>It's abundantly clear to me that when we want to delete a node in a Linked List (be it doubly or singly linked), and we have to search for this node, the time complexity for this task is O(n), as we must traverse the whole list in the worst case to identify the node. Similarly, it is O(k) if we want to delete the k-th node, and we don't have a reference to this node already.</p>
  
  <p>It is commonly cited that one of the benefits of using a doubly linked list over a singly linked list is that deletion is O(1) when we have a reference to the node we want to delete. I.e., if you want to delete the Node i, simply do the following:
  i.prev.next = i.next and i.next.prev = i.prev</p>
  
  <p>It is said that deletion is O(1) in a singly linked list ONLY if you have a reference to the node prior to the one you want to delete. However, I don't think this is necessarily the case. If you want to delete Node i (and you have a reference to Node i), why can't you just copy over the data from i.next, and set i.next = i.next.next? This would also be O(1), as in the doubly linked list case, meaning that deletion is no more efficient in a doubly linked list in ANY case, as far as Big-O is concerned. Of course, this idea wouldn't work if the node you're trying to delete is the last node in the linked list.</p>
  
  <p>It's really bugging me that no one remembers this when comparing singly and doubly linked lists. What am I missing?</p>
  
  <p><strong>To clarify</strong>: what I'm suggesting in the singly linked case is <strong>overwriting the data at the Node you want to delete</strong>, with the data from the next node, and then deleting the next node. This has the same desired effect as deleting Node <code>i</code>, though it is not what you're doing per se.</p>
  
  <p><strong>EDIT</strong></p>
  
  <p><strong>What I've Learned:</strong></p>
  
  <p>So it seems that I am correct to some extent. First of all, many people mentioned that my solution isn't complete, as deletion of the last element is a problem, so my algorithm is O(n) (by definition of Big-O). I naively suggested in response to get around this by keeping track of the "2nd to last node" in your list - of course, this causes problems once the last node in your list has been deleted the first time. A solution that was suggested, and does seem to work, is to demarcate the end of your list with something like a NullNode, and I like this approach.</p>
  
  <p>Other problems that were presented were referential integrity, and the time associated with copying the data itself from the next node (i.e. presumably, a costly deep copy might be necessary). If you can assume that you don't have other objects using the node that you're copying, and that the task of copying is O(1) in itself, then it seems like my solution works. Although, at this point, maybe its worth it to just use a Doubly Linked List :)</p>