Intro
LinkedLists are used to represent sequential data. It’s a linear data structure. Unlike Arrays where they’re stored sequentially in memory, LLs aren’t. Each link in the chain has stores the address of the next link in the chain. This links/nodes collectively form the Linked List.
Basic LLs contain the following info:
- Data or value
- Address of the next node.
- Sometimes the previous node too.
Advantages
If given the position of a node in the LL, inserting a new node is this is because unlike an array, we don’t need to shift other elements in memory. Simply update the next addresses.
Disadvantages
Accessing an element is linear, as we must traverse the entire list to grab the value of a specific node. No indexing like an array… Resulting in access time.
Types
Singly linked list
A linked list where each node points to the next node and the last node points to null.
Doubly linked list
This type’s nodes have two pointers, next and prev. The prev pointer of the first node and the next pointer of the last node point to null.
Circular linked list
Just like the Singly LL but the last node’s next pointer points back to the first node.
There is a Circular Doubly LL, where the prev pointer of the first node points to the last node and the next pointer of the last node points to the first node.
Time complexity
| Operation | Big-O | Note |
|---|---|---|
| Access | O(n) | Linear |
| Search | O(n) | Linear |
| Insert | O(1) | Assumes you have traversed to the insertion position |
| Remove | O(1) | Assumes you have traversed to the node to be removed |
==// Realistically these are all because you need to traverse.==
Common examples
- Counting nodes in an LL.
- Reversing a LL in-place (no copying).
- Finding the middle node using TwoPointerSqueeze (fast and slow)
- Merging two LLs together.
Edge cases
- Empty linked list (head is
null) - Single node
- Two nodes
- Linked list has cycles.
Cycels
Ask the interviewer if there are cycles in the LL, they should be honest with you. If they say no, then inform them you won’t be handling that case.
Techniques
Sentinel/dummy nodes
“Adding a sentinel/dummy node at the head and/or tail might help to handle many edge cases where operations have to be performed at the head or the tail. The presence of dummy nodes essentially ensures that operations will never be done on the head or the tail, thereby removing a lot of headache in writing conditional checks to dealing with null pointers. Be sure to remember to remove them at the end of the operation.”
Two pointers
Read about the TwoPointer pattern in LeetCode Patterns. Commonly used with LLs for:
- Getting the from last node: Have two pointers, where one is nodes ahead of the other. When the node ahead reaches the end, the other node is nodes behind
- Detecting cycles: Have two pointers, where one pointer increments twice as much as the other, if the two pointers meet, means that there is a cycle.
- Getting the middle node: Have two pointers, where one pointer increments twice as much as the other. When the faster node reaches the end of the list, the slower node will be at the middle
In-place and space conservation
Many problems may compel you to create a new LL and add nodes to it. However, that costs memory space… A problem or interviewer may require you to work the LL in-place. Check the Reverse a Linked List problem for insporation.
Elegant modification operations
The non-sequential nature of memory allows for efficient modification of its contents. Unlike arrays where you can only modify the value at a memory position/address, for LLs you can change the value and next pointer.
Common ops include:
- Truncating: Set the
nextpointer tonullat the last element - Swapping values of nodes: Simply swap the value of the two nodes, no need to swap the
nextpointer - Combining two lists: attach the head of the second list to the tail of the first list. // Concatenation.