A playground and implementation of a SingleLinkedList in Swift

SingleyLinkedList.swift

//: [Previous](@previous)

import Foundation

class SingleyLinkedList: CustomStringConvertible, Sequence {
  
  struct Iterator: Swift.IteratorProtocol {
    typealias Element = Int
    internal var nextValue: SLLNode?
    mutating func next() -> Int? {
      defer {
        nextValue = nextValue?.next
      }
      return nextValue?.value
    }
  }
  
  func makeIterator() -> Iterator {
    return Iterator(nextValue: self.head)
  }
  
  internal class SLLNode: CustomStringConvertible {
    var value: Int
    var next: SLLNode?
    
    init(value: Int) {
      self.value = value
    }
    
    var description: String { get { return self.value.description + " " + (((next?.description) != nil) ? next!.description : "END") } }
    
    func append(value: Int) {
      if let next = self.next {
        next.append(value: value)
      } else {
        self.next = SLLNode(value: value)
      }
    }
  }

  internal var head: SLLNode?
  
  init(value: Int) {
    self.head = SLLNode(value: value)
  }
  
  init() {
    
  }
  
  //O(n) where n is the length of the list
  var description: String { get { return self.head?.description ?? "END" } }
  
  var underestimatedCount: Int = 0
  
  //O(n) where n is the length of the list
  func append(value: Int) {
    if let head = self.head {
      head.append(value: value)
    } else {
      head = SLLNode(value: value)
    }
    underestimatedCount += 1
  }
  
  // O(m + n) where m is the length of the list and n is the length of the sequence
  func append<S: Sequence>(sequence: S) where S.Element == Int {
    underestimatedCount += sequence.underestimatedCount
    var itr = self.head
    while itr?.next != nil {
      itr = itr?.next!
    }
    sequence.forEach { value in
      itr?.append(value: value)
      itr = itr?.next
    }
  }
  
  //O(1)
  func prepend(value: Int) {
    let newHead = SLLNode(value: value)
    newHead.next = self.head
    self.head = newHead
    underestimatedCount += 1
  }
  
  //O(m) where m is the length of the Sequence
  func prepend<S: Sequence>(sequence: S) where S.Element == Int {
    underestimatedCount += sequence.underestimatedCount
    var newHead: SLLNode?
    var previous: SLLNode?
    for (i, val) in sequence.enumerated() {
      let new = SLLNode(value: val)
      previous?.next = new
      previous = new
      if i == 0 {
        newHead = new
      }
    }
    previous?.next = self.head
    self.head = newHead
  }
  
  //O(n) where n is the length of the list
  func insert(value: Int, at index: UInt) {
    var itr = index
    var node = self.head
    while itr > 0 {
      itr -= 1
      node = node?.next!
    }
    let add = SLLNode(value: value)
    add.next = node!.next
    node!.next = add
    underestimatedCount += 1
  }
  
  // O(m + n) where m is the index and n is the length of the sequence
  func insert<S: Sequence>(sequence: S, at index: UInt) where S.Element == Int {
    if self.head == nil || index == 0 {
      self.prepend(sequence: sequence)
      return
    }
    var itr = index
    var atIndex = self.head
    while itr > 0 {
      itr -= 1
      atIndex = atIndex?.next!
    }
    var insertHead: SLLNode?
    var previous: SLLNode?
    for (i, val) in sequence.enumerated() {
      let new = SLLNode(value: val)
      previous?.next = new
      previous = new
      if i == 0 {
        insertHead = new
      }
    }
    previous?.next = atIndex?.next
    atIndex?.next = insertHead
    underestimatedCount += sequence.underestimatedCount
  }
  
  //O(n) where n is the length of the list
  var length: Int {
    get {
      if let head = self.head {
        var count = 1
        var itr = head
        while itr.next != nil {
          itr = itr.next!
          count += 1
        }
        return count
      } else {
        return 0
      }
    }
  }
  
  //O(n) where n is the length of the list
  subscript(index: UInt) -> Int? {
    guard let head = self.head else { return nil }
    var dec = index
    var itr = head
    while dec > 0 {
      if let next = itr.next {
        itr = next
        dec -= 1
      } else {
        return nil
      }
    }
    return itr.value
  }
  
}

let list = SingleyLinkedList(value: 1)
list.append(value: 2)
list.prepend(value: 0)
list.append(value: 4)
list.insert(value: 3, at: 3-1)
list.append(value: 5)
let length = list.length
let fifth = list[5]

let listTwo = SingleyLinkedList()
listTwo.append(value: 1)
listTwo.append(sequence: [4,5])
listTwo.prepend(sequence: [-1,0])
listTwo.insert(sequence: [2,3], at: 2)

for (i, val) in list.enumerated() {
  print(i, val)
}
for (i, val) in listTwo.enumerated() {
  print(i, val)
}

list.map { (i) -> Void in
  print(i)
}
listTwo.map { (i) -> Void in
  print(i)
}


//: [Next](@next)