Singly Linked Lists - DSA Notes 📝

🎯 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

*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)