Linked Lists

Overview

A linked list is a linear data structure in which elements (called nodes) are stored in separate objects, each pointing to the next one in the sequence. Unlike arrays, linked lists do not store elements contiguously in memory, which makes insertion and deletion operations more efficient in some cases.

In Swift, linked lists are not part of the standard library, but they can be implemented easily using classes or structs.

Why Use Linked Lists?

Linked lists are ideal when:

• You frequently insert or delete elements at the beginning or middle of a collection.

• You don’t know the final size of the collection in advance.

• Memory reallocation (as in arrays) is a performance concern.

Singly Linked List Structure

In a singly linked list, each node holds a value and a reference to the next node.

class ListNode<T> {
	var value: T
	var next: ListNode?

	init(value: T, next: ListNode? = nil) {
		self.value = value
		self.next = next
	}
}

Linked List Container

class LinkedList<T> {
	private var head: ListNode<T>?

	var isEmpty: Bool {
		return head == nil
	}

	func append(_ value: T) {
		let newNode = ListNode(value: value)
		if let tail = getTail() {
			tail.next = newNode
		} else {
			head = newNode
		}
	}

	func prepend(_ value: T) {
		let newNode = ListNode(value: value, next: head)
		head = newNode
	}

	func getTail() -> ListNode<T>? {
		var node = head
		while node?.next != nil {
			node = node?.next
		}
		return node
	}

	func printList() {
		var node = head
		while let current = node {
			print(current.value)
			node = current.next
		}
	}
}

Common Operations

Insertion

• append(_:) – Adds a value to the end.

• prepend(_:) – Adds a value to the front.

• Inserting in the middle requires traversing to the desired node first.

Deletion

func delete(_ value: T) where T: Equatable {
	var current = head
	var previous: ListNode<T>? = nil

	while let currentNode = current {
		if currentNode.value == value {
			if previous == nil {
				head = currentNode.next
			} else {
				previous?.next = currentNode.next
			}
			return
		}
		previous = current
		current = current?.next
	}
}

Search

func contains(_ value: T) -> Bool where T: Equatable {
	var node = head
	while let current = node {
		if current.value == value {
			return true
		}
		node = current.next
	}
	return false
}

Performance Characteristics

Doubly Linked List

Each node holds references to both the next and previous nodes. This allows bidirectional traversal.

class DoublyListNode<T> {
	var value: T
	var next: DoublyListNode?
	var prev: DoublyListNode?

	init(value: T) {
		self.value = value
	}
}

Doubly linked lists are useful when:

• You need to traverse both forward and backward.

• You frequently delete from the end or middle.

Use Cases for Linked Lists

• Queue and Stack implementations.

• LRU Cache (using doubly linked list + hashmap).

• Implementing Undo/Redo features.

• Memory-constrained systems where dynamic allocation is needed.

Limitations

• No direct indexing.

• More memory per element due to pointer overhead.

• Less cache-friendly compared to arrays (due to non-contiguous memory).

Best Practices

• Prefer structs for value semantics, classes for reference-based structures.

• Always be cautious of memory leaks due to reference cycles—use weak references for prev pointers if needed.

• Use generics to make your list reusable for any type.

Conclusion

Linked lists provide flexibility for dynamic memory management and efficient insertions/deletions. While they may not be as commonly used as arrays in Swift (especially due to the power of the standard library), understanding how they work is crucial for mastering data structures and algorithms.

In the next chapter, we’ll implement Stacks and Queues using linked lists and arrays, and compare their trade-offs.