Doubly linked list

A doubly linked list is a type of linked list where each node contains references to both the next and previous nodes in the list. This allows for efficient traversal of the list in both directions, as it is possible to move backwards and forwards through the list.

Complexity of singly linked list

The time complexity of doubly linked list operations depends on the specific operation being performed. Here is a summary of the time complexity of common doubly linked list operations:

• Accessing an element by index: O(n), as the list must be traversed from the head to the desired element.
• Searching for an element: O(n), as the list must be traversed to find the element.
• Insertion at the beginning or end of the list: O(1), as the next and prev fields of the head or tail node can be adjusted to point to the new element.
• Insertion in the middle of the list: O(1), as the next and prev fields of the surrounding nodes can be adjusted to point to the new element.
• Deletion at the beginning or end of the list: O(1), as the next and prev fields of the head or tail node can be adjusted to skip over the element being deleted.
• Deletion in the middle of the list: O(1), as the next and prev fields of the surrounding nodes can be adjusted to skip over the element being deleted.

The space complexity of a doubly linked list is O(n), as the list requires a separate node for each element being stored.

Overall, the time complexity of doubly linked list operations is generally O(1), as most operations can be performed in constant time. The space complexity is always O(n).