LinkedList in Kotlin
Overview
A LinkedList is a linear data structure where elements are stored in nodes, and each node points to the next node in the sequence. Kotlin provides both the standard library implementation and the ability to create custom implementations.
Implementation from Scratch
class Node<T>(
var value: T,
var next: Node<T>? = null
)
class LinkedList<T> {
private var head: Node<T>? = null
private var tail: Node<T>? = null
var size = 0
private set
fun add(value: T) {
val newNode = Node(value)
if (head == null) {
head = newNode
tail = newNode
} else {
tail?.next = newNode
tail = newNode
}
size++
}
fun addFirst(value: T) {
val newNode = Node(value)
newNode.next = head
head = newNode
if (tail == null) {
tail = newNode
}
size++
}
fun removeFirst(): T? {
if (head == null) return null
val value = head?.value
head = head?.next
size--
if (head == null) {
tail = null
}
return value
}
fun find(value: T): Boolean {
var current = head
while (current != null) {
if (current.value == value) return true
current = current.next
}
return false
}
override fun toString(): String {
return buildString {
var current = head
append("[")
while (current != null) {
append(current.value)
if (current.next != null) append(", ")
current = current.next
}
append("]")
}
}
}
Using Kotlin's Built-in LinkedList
fun main() {
// Creating a LinkedList
val linkedList = LinkedList<String>()
// Adding elements
linkedList.add("First")
linkedList.add("Second")
linkedList.addFirst("New First")
// Accessing elements
println(linkedList.first) // New First
println(linkedList.last) // Second
// Removing elements
linkedList.removeFirst()
linkedList.removeLast()
// Checking size and emptiness
println(linkedList.size) // 1
println(linkedList.isEmpty()) // false
}
Stack in Kotlin
Overview
A Stack is a LIFO (Last-In-First-Out) data structure. While Kotlin doesn't have a built-in Stack class, we can implement one using various approaches.
Custom Stack Implementation
class Stack<T> {
private val elements = mutableListOf<T>()
fun push(element: T) {
elements.add(element)
}
fun pop(): T? {
if (elements.isEmpty()) return null
return elements.removeAt(elements.lastIndex)
}
fun peek(): T? {
return elements.lastOrNull()
}
fun isEmpty() = elements.isEmpty()
fun size() = elements.size
override fun toString() = elements.toString()
}
// Usage example
fun main() {
val stack = Stack<Int>()
stack.push(1)
stack.push(2)
stack.push(3)
println(stack.pop()) // 3
println(stack.peek()) // 2
println(stack.size()) // 2
}
Using Kotlin Collections as Stack
fun main() {
// Using MutableList as a stack
val stack = mutableListOf<Int>()
// Push operations
stack.add(1) // push
stack.add(2) // push
// Pop operation
val lastElement = stack.removeLastOrNull()
// Peek operation
val topElement = stack.lastOrNull()
}
Queue in Kotlin
Overview
A Queue is a FIFO (First-In-First-Out) data structure. We'll implement both a basic Queue and a more advanced implementation with Kotlin's features.
Basic Queue Implementation
class Queue<T> {
private val elements = mutableListOf<T>()
fun enqueue(element: T) {
elements.add(element)
}
fun dequeue(): T? {
if (elements.isEmpty()) return null
return elements.removeAt(0)
}
fun peek(): T? = elements.firstOrNull()
fun isEmpty() = elements.isEmpty()
fun size() = elements.size
override fun toString() = elements.toString()
}
Advanced Queue Implementation with Circular Buffer
class CircularQueue<T>(private val capacity: Int) {
private val elements = Array<Any?>(capacity) { null }
private var front = 0
private var rear = -1
private var size = 0
fun enqueue(element: T): Boolean {
if (isFull()) return false
rear = (rear + 1) % capacity
elements[rear] = element
size++
return true
}
@Suppress("UNCHECKED_CAST")
fun dequeue(): T? {
if (isEmpty()) return null
val element = elements[front] as T
elements[front] = null
front = (front + 1) % capacity
size--
return element
}
@Suppress("UNCHECKED_CAST")
fun peek(): T? = if (isEmpty()) null else elements[front] as T
fun isEmpty() = size == 0
fun isFull() = size == capacity
fun size() = size
}
HashTables in Kotlin
Overview
HashTables (or HashMaps in Kotlin) are key-value data structures that provide constant-time average case complexity for insertions and lookups.
Custom HashTable Implementation
class HashTable<K, V>(private val capacity: Int = 16) {
private data class Entry<K, V>(
val key: K,
var value: V,
var next: Entry<K, V>? = null
)
private val buckets = Array<Entry<K, V>?>(capacity) { null }
private var size = 0
private fun hash(key: K): Int {
return Math.abs(key.hashCode() % capacity)
}
fun put(key: K, value: V) {
val index = hash(key)
val entry = Entry(key, value)
if (buckets[index] == null) {
buckets[index] = entry
size++
return
}
var current = buckets[index]
while (current != null) {
if (current.key == key) {
current.value = value
return
}
if (current.next == null) {
current.next = entry
size++
return
}
current = current.next
}
}
fun get(key: K): V? {
val index = hash(key)
var current = buckets[index]
while (current != null) {
if (current.key == key) {
return current.value
}
current = current.next
}
return null
}
fun remove(key: K): Boolean {
val index = hash(key)
var current = buckets[index]
var prev: Entry<K, V>? = null
while (current != null) {
if (current.key == key) {
if (prev == null) {
buckets[index] = current.next
} else {
prev.next = current.next
}
size--
return true
}
prev = current
current = current.next
}
return false
}
fun size() = size
fun isEmpty() = size == 0
}
Using Kotlin's Built-in HashMap
fun main() {
// Creating a HashMap
val map = HashMap<String, Int>()
// Adding entries
map["one"] = 1
map["two"] = 2
map.put("three", 3)
// Accessing values
println(map["one"]) // 1
println(map.get("two")) // 2
println(map.getOrDefault("four", 0)) // 0
// Removing entries
map.remove("one")
// Checking containment
println(map.containsKey("one")) // false
println(map.containsValue(2)) // true
// Iterating over entries
for ((key, value) in map) {
println("$key = $value")
}
// Using with nullable values
val nullableMap = HashMap<String, Int?>()
nullableMap["nullable"] = null
}
Performance Characteristics
LinkedList
- Access: O(n)
- Search: O(n)
- Insertion at beginning: O(1)
- Insertion at end: O(1) with tail reference
- Deletion at beginning: O(1)
- Deletion at end: O(n)
- Space complexity: O(n)
Stack
- Push: O(1)
- Pop: O(1)
- Peek: O(1)
- Space complexity: O(n)
Queue
- Enqueue: O(1)
- Dequeue: O(1) with proper implementation
- Peek: O(1)
- Space complexity: O(n)
HashTable
- Insert: O(1) average, O(n) worst
- Delete: O(1) average, O(n) worst
- Search: O(1) average, O(n) worst
- Space complexity: O(n)
Best Practices and Tips
-
Choose the Right Collection:
- Use LinkedList when frequent insertions/deletions at both ends are needed
- Use Stack for LIFO operations
- Use Queue for FIFO operations
- Use HashTable for key-value associations with fast lookups
-
Memory Considerations:
- LinkedList requires extra memory for node references
- CircularQueue can help manage memory in fixed-size scenarios
- HashTable size should be balanced against expected number of elements
-
Thread Safety:
- These implementations are not thread-safe by default
- Use Collections.synchronizedList() or other concurrent implementations for thread safety
-
Performance Optimization:
- Initialize collections with expected capacity when possible
- Consider using specialized implementations for specific use cases
- Monitor load factor in HashTable implementations
Top comments (0)