Linked List
Why Linked List?
Arrays can be used to store linear data of similar types, but arrays have following limitations.
- The size of the arrays is fixed
- Inserting a new element in an array of elements is expensive
Advantages over arrays
- Dynamic size
- Ease of insertion/deletion
Drawbacks:
- Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do binary search with linked lists.
- Extra memory space for a pointer is required with each element of the list.
Technique 1: Dummy Head Node
We can create a dummy node to help reduce/remove special cases from linked lists, dummy node is a node that does not hold any value, but is in the list to provide an extra node at the front (and/or rear) of the list.
- Add Two Numbers
Technique 2: Find the middle of the list
Using two pointers, one moves one postion at a time, and the other moves two position at a time.
- Remove Nth Node From End of List
Technique 3: Using stack or vector to save the reverse order
We can use stack or vector to make it easy to check the linked list in reverse order.
- Palindrome Linked List
Technique 4: Use count difference to find the intersection
- Intersection of Two Linked Lists