🎯 Learning Goals

  • What are the characteristics of Singly Linked Lists?
  • What are its time complexities?

🧠 Key Concepts (aka My Notes)

What is a ListNode?

  • Has a value and a next pointer
    • next is a reference to another ListNode
  • Order in memory may not be contiguous (unlike arrays which are)

Traversal

Simple while loop with a current pointer can be used:

cur = ListNode1
while cur:
    cur = cur.next

⌚ Time complexity is O(n) , where n is the number of nodes in the linked list

Now if the Linked List is circular (i.e. last node points back to first) traversing like this would cause an infinite loop.

  • It would be helpful if we’re keeping track of the head and the tail of the linked list using pointers

Insertion

  • Advantage over array is that inserting is always O(1) even if we insert in middle.

Let’s say we wanna add at the end or tail :

tail.next = NewListNode
tail = NewListNode
# or this line 'tail = tail.next', both are correct

⌚ Time complexity is O(1)

Deletion

  • Removing any node is constant time ASSUMING we have a pointer to the previous node.

Let’s say we wanna remove the second node:

head.next = head.next.next
# Just set the next pointer of head to the one after the deleted node
  • Can be assumed that garbage collection will take place for the deleted node

⌚ Time complexity is O(1)

For both of these operations, the caveat is if we don’t have a reference to the node at the desired position (head or tail), the time will still be O(n)

⌚ Time Complexities

Operation Big-O
Reading/ Access O(n)
Traversal/ Search O(n)
Insertion O(1)*
Deletion O(1)*

*Assumes you have a reference to the node at the position (if not it is O(n) )

💪 LeetCode Problems

  • 206. Reverse Linked List (Link)
  • 21. Merge Two Sorted Lists (Link)