Doubly Linked Lists - DSA Notes 📝

🎯 Learning Goals

• What are doubly linked lists?
• What are its operations’ time complexities?

---

🧠 Key Concepts (aka My Notes)

• Two pointers (next and prev)
  • Null prev means it is the head of the list

Insertion at End

• Same as Singly Linked
• But, make sure to update prev pointer too
• The order is important
  • Don’t update the tail pointer without updating the old tail’s next and NewListNode’s prev)

tail.next = NewListNode
NewListNode.prev = tail
# Update tail pointers
tail = tail.next

⌚ Time complexity is O(1)

Deletion at End

• Deletion means just not having anything point to that last node
• For this one, important to save the pointer to the node before the tail
  • So that, we can set the tail pointer to that node.

Here, ListNode2 is just a variable name. It can be temp or anything.

ListNode2 = tail.prev
ListNode2.next = null
tail = ListNode2

⌚ Time complexity is O(1)

O(1) insertion and deletion means that theoretically we can use these guys are implement Stacks.

Access

• Same as Singly Linked List, but can go both directions

⌚ Time complexity is O(n)

⌚ Time Complexities

Operation	Big-O
Access	O(n)
Search	O(n)
Insertion (end)	O(1)
Deletion (end)	O(1)

💪 LeetCode Problems

• 707. Design Linked List (Link)
• 1472. Design Browser History (Link)