Linked lists are the second most common data structure in coding interviews after arrays. They test your ability to work with pointers, handle edge cases, and think about memory. In this article, you will learn how linked lists work, how to implement them, and how to solve classic interview problems.
We show every example in Kotlin, Python, and Go.
What is a Linked List?
A linked list is a collection of nodes. Each node stores two things: a value and a pointer (reference) to the next node. Unlike arrays, linked list nodes are not stored next to each other in memory. They can be anywhere in memory, connected through pointers.
Think of a linked list like a treasure hunt. Each clue (node) tells you the location of the next clue. You must follow the chain from start to finish. You cannot jump to the middle directly.
Singly Linked List
In a singly linked list, each node points to the next node. The last node points to null (nothing). You can only move forward — from the head (first node) to the tail (last node).
Node Definition
Kotlin:
class ListNode(var value: Int, var next: ListNode? = null)
Python:
class ListNode:
def __init__(self, value: int, next=None):
self.value = value
self.next = next
Go:
type ListNode struct {
Value int
Next *ListNode
}
Insert at the Head
Adding a new node at the beginning is O(1) — you create a new node and point it to the current head.
Kotlin:
fun insertAtHead(head: ListNode?, value: Int): ListNode {
val newNode = ListNode(value)
newNode.next = head
return newNode
}
Python:
def insert_at_head(head, value):
new_node = ListNode(value)
new_node.next = head
return new_node
Go:
func insertAtHead(head *ListNode, value int) *ListNode {
newNode := &ListNode{Value: value, Next: head}
return newNode
}
Insert at the Tail
Adding a node at the end is O(n) because you must walk to the last node first.
Kotlin:
fun insertAtTail(head: ListNode?, value: Int): ListNode {
val newNode = ListNode(value)
if (head == null) return newNode
var current = head
while (current?.next != null) {
current = current.next
}
current?.next = newNode
return head
}
Python:
def insert_at_tail(head, value):
new_node = ListNode(value)
if head is None:
return new_node
current = head
while current.next is not None:
current = current.next
current.next = new_node
return head
Go:
func insertAtTail(head *ListNode, value int) *ListNode {
newNode := &ListNode{Value: value}
if head == nil {
return newNode
}
current := head
for current.Next != nil {
current = current.Next
}
current.Next = newNode
return head
}
Linked List Operations and Time Complexity
| Operation | Time | Why? |
|---|---|---|
| Access by index | O(n) | Must walk from head |
| Search | O(n) | Must check each node |
| Insert at head | O(1) | Update one pointer |
| Insert at tail | O(n) | Walk to the end first |
| Delete at head | O(1) | Update head pointer |
| Delete by value | O(n) | Find the node first |
Arrays vs Linked Lists
| Feature | Array | Linked List |
|---|---|---|
| Access by index | O(1) | O(n) |
| Insert at beginning | O(n) | O(1) |
| Insert at end | O(1) amortized | O(n) |
| Memory | Contiguous block | Scattered nodes |
| Extra memory | None | Pointer per node |
| Cache performance | Excellent | Poor |
Use arrays when you need fast random access and your data size is predictable. Use linked lists when you need frequent insertions and deletions at the beginning.
Reverse a Linked List
This is the single most common linked list interview question. You will see it in almost every coding interview.
The idea: walk through the list and reverse each pointer. Keep track of three nodes — the previous node, the current node, and the next node.
Kotlin:
fun reverseList(head: ListNode?): ListNode? {
var prev: ListNode? = null
var current = head
while (current != null) {
val next = current.next
current.next = prev
prev = current
current = next
}
return prev
}
Python:
def reverse_list(head):
prev = None
current = head
while current is not None:
next_node = current.next
current.next = prev
prev = current
current = next_node
return prev
Go:
func reverseList(head *ListNode) *ListNode {
var prev *ListNode
current := head
for current != nil {
next := current.Next
current.Next = prev
prev = current
current = next
}
return prev
}
Time complexity: O(n) — we visit each node once. Space complexity: O(1) — we only use three pointers.
Doubly Linked List
A doubly linked list has nodes with two pointers: one pointing to the next node and one pointing to the previous node. This lets you move both forward and backward.
Kotlin:
class DoublyNode(
var value: Int,
var next: DoublyNode? = null,
var prev: DoublyNode? = null
)
fun insertAtHead(head: DoublyNode?, value: Int): DoublyNode {
val newNode = DoublyNode(value)
newNode.next = head
head?.prev = newNode
return newNode
}
Python:
class DoublyNode:
def __init__(self, value, next=None, prev=None):
self.value = value
self.next = next
self.prev = prev
def insert_at_head(head, value):
new_node = DoublyNode(value)
new_node.next = head
if head:
head.prev = new_node
return new_node
Go:
type DoublyNode struct {
Value int
Next *DoublyNode
Prev *DoublyNode
}
func insertAtHead(head *DoublyNode, value int) *DoublyNode {
newNode := &DoublyNode{Value: value, Next: head}
if head != nil {
head.Prev = newNode
}
return newNode
}
Doubly linked lists use more memory (extra pointer per node), but they make deletion easier. If you have a pointer to a node, you can delete it in O(1) without walking from the head.
Circular Linked List
A circular linked list is a linked list where the last node points back to the first node instead of null. This creates a cycle. Circular linked lists are useful for problems that involve rotation or round-robin scheduling.
Head -> 1 -> 2 -> 3 -> back to Head
Fast and Slow Pointer Technique
The fast and slow pointer technique (also called Floyd’s algorithm) is the most important pattern for linked list problems. You use two pointers:
- Slow pointer moves one step at a time
- Fast pointer moves two steps at a time
Detect a Cycle
If a linked list has a cycle, the fast pointer will eventually catch up to the slow pointer. If there is no cycle, the fast pointer will reach the end (null).
Kotlin:
fun hasCycle(head: ListNode?): Boolean {
var slow = head
var fast = head
while (fast?.next != null) {
slow = slow?.next
fast = fast.next?.next
if (slow == fast) return true
}
return false
}
Python:
def has_cycle(head):
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
Go:
func hasCycle(head *ListNode) bool {
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
if slow == fast {
return true
}
}
return false
}
Time complexity: O(n). Space complexity: O(1).
Find the Middle Node
The slow pointer is at the middle when the fast pointer reaches the end. This is because the fast pointer moves twice as fast.
Kotlin:
fun findMiddle(head: ListNode?): ListNode? {
var slow = head
var fast = head
while (fast?.next != null) {
slow = slow?.next
fast = fast.next?.next
}
return slow
}
Python:
def find_middle(head):
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
Go:
func findMiddle(head *ListNode) *ListNode {
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
return slow
}
Merge Two Sorted Lists
Given two sorted linked lists, merge them into one sorted list. This is another classic interview question.
Kotlin:
fun mergeTwoLists(l1: ListNode?, l2: ListNode?): ListNode? {
val dummy = ListNode(0)
var current = dummy
var p1 = l1
var p2 = l2
while (p1 != null && p2 != null) {
if (p1.value <= p2.value) {
current.next = p1
p1 = p1.next
} else {
current.next = p2
p2 = p2.next
}
current = current.next!!
}
current.next = p1 ?: p2
return dummy.next
}
Python:
def merge_two_lists(l1, l2):
dummy = ListNode(0)
current = dummy
while l1 and l2:
if l1.value <= l2.value:
current.next = l1
l1 = l1.next
else:
current.next = l2
l2 = l2.next
current = current.next
current.next = l1 if l1 else l2
return dummy.next
Go:
func mergeTwoLists(l1, l2 *ListNode) *ListNode {
dummy := &ListNode{}
current := dummy
for l1 != nil && l2 != nil {
if l1.Value <= l2.Value {
current.Next = l1
l1 = l1.Next
} else {
current.Next = l2
l2 = l2.Next
}
current = current.Next
}
if l1 != nil {
current.Next = l1
} else {
current.Next = l2
}
return dummy.Next
}
The dummy node trick simplifies the code. Instead of handling the head as a special case, create a dummy node and build the list after it. Return dummy.next at the end.
Why Interviewers Ask Linked List Questions
Linked list questions test:
- Pointer manipulation — can you update references without losing nodes?
- Edge cases — empty list, single node, cycle at the head
- Algorithmic thinking — the fast/slow pointer technique shows you know patterns
- Memory awareness — understanding heap allocation and references
Practice Problems
Try these problems on LeetCode:
- Reverse Linked List (LeetCode #206) — the most classic linked list problem
- Linked List Cycle (LeetCode #141) — fast and slow pointer
- Merge Two Sorted Lists (LeetCode #21) — dummy node technique
- Middle of the Linked List (LeetCode #876) — fast and slow pointer
- Remove Nth Node From End (LeetCode #19) — two pointers with a gap
What’s Next?
In the next article, we cover Stacks and Queues — two data structures built on top of arrays or linked lists that follow specific rules about how you add and remove elements.
Next: DSA Tutorial #3: Stacks and Queues
Full series: DSA from Zero to Interview Ready