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

💪 LeetCode Problems

• 707. Design Linked List (Link)


• 1472. Design Browser History (Link)