When is doubly linked list more efficient than singly linked list?

Technology CommunityCategory: Data StructuresWhen is doubly linked list more efficient than singly linked list?
VietMX Staff asked 3 years ago

Short answer: Delete a node in a Single Linked ListO(n)

You don’t know which is the preceeding node so you have to traverse the list until you find it:

deleteNode(Node node){
    prevNode = tmpNode;
    tmpNode = prevNode.next;
    
    while (tmpNode != null) {
        if (tmpNode == node) {
            prevNode.next = tmpNode.next;
        }
        prevNode = tmpNode;
        tmpNode = prevNode.next;
    }
}

Delete a node in a Double Linked ListO(1)

You can simply update the links like this:

deleteNode(Node node){
    node.prev.next = node.next;
    node.next.prev = node.prev;
}

Long Answer:

Insertion is clearly less work in a singly-linked list, as long as you are content to always insert at the head or after some known element. (That is, you cannot insert before a known element, but see below.)

Deletion, on the other hand, is trickier because you need to know the element before the element to be deleted.

One way of doing this is to make the delete API work with the predecessor of the element to be deleted. This mirrors the insert API, which takes the element which will be the predecessor of the new element, but it’s not very convenient and it’s hard to document. It’s usually possible, though. Generally speaking, you arrive at an element in a list by traversing the list.

Of course, you could just search the list from the beginning to find the element to be deleted, so that you know what its predecessor was. That assumes that the delete API includes the head of the list, which is also inconvenient. Also, the search is stupidly slow.

The way that hardly anyone uses, but which is actually pretty effective, is to define a singly-linked list iterator to be the pointer to the element preceding the current target of the iterator. This is simple, only one indirection slower than using a pointer directly to the element, and makes both insertion and deletion fast. The downside is that deleting an element may invalidate other iterators to list elements, which is annoying. (It doesn’t invalidate the iterator to the element being deleted, which is nice for traversals which delete some elements, but that’s not much compensation.)

If deletion is not important, perhaps because the data structures are immutable, singly-linked lists offer another really useful property: they allow structure-sharing. A singly-linked list can happily be the tail of multiple heads, something which is impossible for a doubly-linked list. For this reason, singly-linked lists have traditionally been the simple data structure of choice for functional languages.