❗A linked list is a collection of values arranged in a linear unidirectional sequence. A linked list has several theoretical advantages over contiguous storage options such as the Swift Array:
✅ Constant time insertion and removal from the front of the list.
✅ Reliable performance characteristics.
❗A linked list is a chain of nodes. Nodes have two responsibilities:
✅ Hold a value.
✅ Hold a reference to the next node. A nil value represents the end of the list.
import UIKit
struct LinkedList {
var head :Node?
var tail :Node?
var isEmpty :Bool {
return head == nil
}
mutating func push(_ value :Value) {
head = Node(value: value, next: head)
if tail == nil {
tail = head
}
}
func node(at index:Int) -> Node? {
var currentIndex = 0
var currentNode = head
while(currentNode != nil && currentIndex < index) {
currentNode = currentNode?.next
currentIndex += 1
}
return currentNode
}
func insert(_ value :Value, after node :Node) {
node.next = Node(value: value, next: node.next)
}
mutating func append(_ value :Value) {
guard !isEmpty else {
push(value)
return
}
let node = Node(value: value)
tail!.next = node
tail = node
}
mutating func pop() -> Value? {
defer {
head = head?.next
if isEmpty {
tail = nil
}
}
return head?.value
}
mutating func removeLast() -> Value? {
guard let head = head else {
return nil
}
guard head.next != nil else {
return pop()
}
var prev = head
var current = head
while let next = current.next {
prev = current
current = next
}
prev.next = nil
tail = prev
return current.value
}
mutating func remove(after node: Node) -> Value? {
defer {
if node.next === tail {
tail = node
}
// 10 -> 3
node.next = node.next?.next
}
return node.next?.value
}
init() { }
}
extension LinkedList :CustomStringConvertible {
var description :String {
guard let head = head else {
return "Empty List"
}
return String(describing: head)
}
}
class Node {
var value :Value
var next :Node?
init(value :Value, next :Node? = nil) {
self.value = value
self.next = next
}
}
extension Node :CustomStringConvertible {
var description :String {
guard let next = next else {
return "\(value)"
}
return "\(value) -> " + String(describing: next) + " "
}
}
var list = LinkedList()
list.append(10)
list.append(3)
list.append(12)
list.append(100)
print("Before removing")
print(list)
let index = 1
let node = list.node(at: index - 1)!
let removedValue = list.remove(after: node)
print("After removing")
print(list)