Linked List Implementation in Swift
Swift 5.0, Xcode 10.3
I have written an implementation for a doubly linked list in Swift. As well, I decided to make the node class private and thus hidden to the user so they don't ever need to interact with it. I have written all of the algorithms that I needed to give it MutableCollection, BidirectionalCollection, and RandomAccessCollection conformance.
What I Could Use Help With
- I am pretty sure that my
LinkedListtype properly satisfies all of the time complexity requirements of certain algorithms and operations that come hand in hand with linked lists but am not sure. - I was also wondering if there are any ways I can make my Linked List implementation more efficient.
- In addition, I am not sure if there are and linked list specific methods or computed properties that I have not included that I should implement.
- I have some testing but if you do find any errors/mistakes in my code that would help a lot.
- Any other input is also appreciated!
Here is my code:
public struct LinkedList<Element> {
private var headNode: LinkedListNode<Element>?
private var tailNode: LinkedListNode<Element>?
public private(set) var count: Int = 0
public init() { }
}
//MARK: - LinkedList Node
extension LinkedList {
fileprivate typealias Node<T> = LinkedListNode<T>
fileprivate class LinkedListNode<T> {
public var value: T
public var next: LinkedListNode<T>?
public weak var previous: LinkedListNode<T>?
public init(value: T) {
self.value = value
}
}
}
//MARK: - Initializers
public extension LinkedList {
private init(_ nodeChain: NodeChain<Element>?) {
guard let chain = nodeChain else {
return
}
headNode = chain.head
tailNode = chain.tail
count = chain.count
}
init<S>(_ sequence: S) where S: Sequence, S.Element == Element {
if let linkedList = sequence as? LinkedList<Element> {
self = linkedList
} else {
self = LinkedList(NodeChain(of: sequence))
}
}
}
//MARK: NodeChain
extension LinkedList {
private struct NodeChain<Element> {
let head: Node<Element>!
let tail: Node<Element>!
private(set) var count: Int
// Creates a chain of nodes from a sequence. Returns `nil` if the sequence is empty.
init?<S>(of sequence: S) where S: Sequence, S.Element == Element {
var iterator = sequence.makeIterator()
guard let firstValue = iterator.next() else {
return nil
}
var currentNode = Node(value: firstValue)
head = currentNode
var nodeCount = 1
while true {
if let nextElement = iterator.next() {
let nextNode = Node(value: nextElement)
currentNode.next = nextNode
nextNode.previous = currentNode
currentNode = nextNode
nodeCount += 1
} else {
tail = currentNode
count = nodeCount
return
}
}
return nil
}
}
}
//MARK: - Copy Nodes
extension LinkedList {
private mutating func copyNodes() {
guard let nodeChain = NodeChain(of: self) else {
return
}
headNode = nodeChain.head
tailNode = nodeChain.tail
}
}
//MARK: - Computed Properties
public extension LinkedList {
var head: Element? {
return headNode?.value
}
var tail: Element? {
return tailNode?.value
}
var first: Element? {
return head
}
var last: Element? {
return tail
}
}
//MARK: - Sequence Conformance
extension LinkedList: Sequence {
public typealias Iterator = LinkedListIterator<Element>
public __consuming func makeIterator() -> LinkedList<Element>.Iterator {
return LinkedListIterator(node: headNode)
}
public struct LinkedListIterator<T>: IteratorProtocol {
public typealias Element = T
private var currentNode: LinkedListNode<T>?
fileprivate init(node: LinkedListNode<T>?) {
currentNode = node
}
public mutating func next() -> T? {
guard let node = currentNode else {
return nil
}
currentNode = node.next
return node.value
}
}
}
//MARK: - Collection Conformance
extension LinkedList: Collection {
public typealias Index = LinkedListIndex<Element>
public var startIndex: LinkedList<Element>.Index {
return Index(node: headNode, offset: 0)
}
public var endIndex: LinkedList<Element>.Index {
return Index(node: nil, offset: count)
}
public func index(after i: LinkedList<Element>.Index) -> LinkedList<Element>.LinkedListIndex<Element> {
precondition(i.offset != endIndex.offset, "LinkedList index is out of bounds")
return Index(node: i.node?.next, offset: i.offset + 1)
}
public struct LinkedListIndex<T>: Comparable {
fileprivate weak var node: LinkedList.Node<T>?
fileprivate var offset: Int
fileprivate init(node: LinkedList.Node<T>?, offset: Int) {
self.node = node
self.offset = offset
}
public static func ==<T>(lhs: LinkedListIndex<T>, rhs: LinkedListIndex<T>) -> Bool {
return lhs.offset == rhs.offset
}
public static func < <T>(lhs: LinkedListIndex<T>, rhs: LinkedListIndex<T>) -> Bool {
return lhs.offset < rhs.offset
}
}
}
//MARK: - MutableCollection Conformance
extension LinkedList: MutableCollection {
public subscript(position: LinkedList<Element>.Index) -> Element {
get {
precondition(position.offset != endIndex.offset, "Index out of range")
guard let node = position.node else {
fatalError("LinkedList index is invalid")
}
return node.value
}
set {
precondition(position.offset != endIndex.offset, "Index out of range")
// Copy-on-write semantics for nodes
if !isKnownUniquelyReferenced(&headNode) {
copyNodes()
}
position.node?.value = newValue
}
}
}
//MARK: LinkedList Specific Operations
public extension LinkedList {
mutating func prepend(_ newElement: Element) {
replaceSubrange(startIndex..<startIndex, with: [newElement])
}
mutating func prepend<S>(contentsOf newElements: S) where S: Sequence, S.Element == Element {
replaceSubrange(startIndex..<startIndex, with: newElements)
}
mutating func popFirst() -> Element? {
guard !isEmpty else {
return nil
}
return removeFirst()
}
mutating func popLast() -> Element? {
guard !isEmpty else {
return nil
}
return removeLast()
}
}
//MARK: - BidirectionalCollection Conformance
extension LinkedList: BidirectionalCollection {
public func index(before i: LinkedList<Element>.LinkedListIndex<Element>) -> LinkedList<Element>.LinkedListIndex<Element> {
precondition(i.offset != startIndex.offset, "LinkedList index is out of bounds")
if i.offset == count {
return Index(node: tailNode, offset: i.offset - 1)
}
return Index(node: i.node?.previous, offset: i.offset - 1)
}
}
//MARK: - RangeReplaceableCollection Conformance
extension LinkedList: RangeReplaceableCollection {
public mutating func replaceSubrange<S, R>(_ subrange: R, with newElements: __owned S) where S : Sequence, R : RangeExpression, LinkedList<Element>.Element == S.Element, LinkedList<Element>.Index == R.Bound {
let range = subrange.relative(to: indices)
precondition(range.lowerBound >= startIndex && range.upperBound <= endIndex, "Subrange bounds are out of range")
// If range covers all elements and the new elements are a LinkedList then set references to it
if range.lowerBound == startIndex, range.upperBound == endIndex, let linkedList = newElements as? LinkedList {
self = linkedList
return
}
var newElementsCount = 0
// Update count after replacement
defer {
count = count - (range.upperBound.offset - range.lowerBound.offset) + newElementsCount
}
// There are no new elements, so range indicates deletion
guard let nodeChain = NodeChain(of: newElements) else {
// If there is nothing in the removal range
// This also covers the case that the linked list is empty because this is the only possible range
guard range.lowerBound != range.upperBound else {
return
}
// Deletion range spans all elements
guard !(range.lowerBound == startIndex && range.upperBound == endIndex) else {
headNode = nil
tailNode = nil
return
}
// Copy-on-write semantics for nodes before mutation
if !isKnownUniquelyReferenced(&headNode) {
copyNodes()
}
// Move head up if deletion starts at start index
if range.lowerBound == startIndex {
// Can force unwrap node since the upperBound is not the end index
headNode = range.upperBound.node!
headNode!.previous = nil
// Move tail back if deletion ends at end index
} else if range.upperBound == endIndex {
// Can force unwrap since lowerBound index must have an associated element
tailNode = range.lowerBound.node!.previous
tailNode!.next = nil
// Deletion range is in the middle of the linked list
} else {
// Can force unwrap all bound nodes since they both must have elements
range.upperBound.node!.previous = range.lowerBound.node!.previous
range.lowerBound.node!.previous!.next = range.upperBound.node!
}
return
}
// Obtain the count of the new elements from the node chain composed from them
newElementsCount = nodeChain.count
// Replace entire content of list with new elements
guard !(range.lowerBound == startIndex && range.upperBound == endIndex) else {
headNode = nodeChain.head
tailNode = nodeChain.tail
return
}
// Copy-on-write semantics for nodes before mutation
if !isKnownUniquelyReferenced(&headNode) {
copyNodes()
}
// Prepending new elements
guard range.upperBound != startIndex else {
headNode?.previous = nodeChain.tail
nodeChain.tail.next = headNode
headNode = nodeChain.head
return
}
// Appending new elements
guard range.lowerBound != endIndex else {
tailNode?.next = nodeChain.head
nodeChain.head.previous = tailNode
tailNode = nodeChain.tail
return
}
if range.lowerBound == startIndex {
headNode = nodeChain.head
}
if range.upperBound == endIndex {
tailNode = nodeChain.tail
}
range.lowerBound.node!.previous!.next = nodeChain.head
range.upperBound.node!.previous = nodeChain.tail
}
}
//MARK: - ExpressibleByArrayLiteral Conformance
extension LinkedList: ExpressibleByArrayLiteral {
public typealias ArrayLiteralElement = Element
public init(arrayLiteral elements: LinkedList<Element>.ArrayLiteralElement...) {
self.init(elements)
}
}
//MARK: - CustomStringConvertible Conformance
extension LinkedList: CustomStringConvertible {
public var description: String {
return "[" + lazy.map { "\($0)" }.joined(separator: ", ") + "]"
}
}
Note: My up-to-date LinkedList implementation can be found here: https://github.com/Wildchild9/LinkedList-Swift.
