by
51 6
0
4
420
2
Top 5% !
Popular
Specified
OpenSource
No tags for this snippet yet.
Languageswift
LicenseMIT_X11

LinkedList (Collection)

Copy Embed Code
<iframe id="embedFrame" style="width:600px; height:300px;"
src="https://www.snip2code.com/Embed/3813274/LinkedList-(Collection)?startLine=0"></iframe>
Click on the embed code to copy it into your clipboard Width Height
Leave empty to retrieve all the content Start End
class Node<Value> { var value: Value var next: Node? init(value: Value, next: Node? = nil) { self.value = value self.next = next } } //MARK: - CustomStringConvertible extension Node: CustomStringConvertible { var description: String { guard let next = next else { return "\(value)" } return "\(value) -> " + String(describing: next) + " " } } struct LinkedList<Value> { var head: Node<Value>? var tail: Node<Value>? init() {} var isEmpty: Bool { return head == nil } mutating func copyNodes() { guard !isKnownUniquelyReferenced(&head) else { return } guard var oldNode = head else { return } head = Node(value: oldNode.value) var newNode = head while let nextOldNode = oldNode.next { newNode!.next = Node(value: nextOldNode.value) newNode = newNode!.next oldNode = nextOldNode } tail = newNode } mutating func push(_ value: Value) { copyNodes() head = Node(value: value, next: head) if tail == nil { tail = head } } mutating func append(_ value: Value) { copyNodes() guard !isEmpty else { push(value); return } tail!.next = Node(value: value) tail = tail!.next } func node(at index: Int) -> Node<Value>? { var currentNode = head for _ in 0..<index { currentNode = currentNode?.next } return currentNode } @discardableResult mutating func insert(value: Value, after node: Node<Value>) -> Node<Value> { copyNodes() guard tail !== node else { append(value); return tail! } let newNode = Node(value: value, next: node.next) node.next = newNode return newNode } @discardableResult mutating func pop() -> Value? { copyNodes() defer { head = head?.next if isEmpty { tail = nil } } return head?.value } @discardableResult mutating func removeLast() -> Value? { copyNodes() 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 } @discardableResult mutating func remove(after node: Node<Value>) -> Value? { copyNodes() defer { if node.next === tail { tail = node } let nodeToRemove = node.next node.next = nodeToRemove?.next } return node.next?.value } } extension LinkedList: CustomStringConvertible { var description: String { guard let head = head else { return "Empty list" } return String(describing: head) } } extension LinkedList: Collection { struct Index: Comparable { var node: Node<Value>? static func ==(lhs: Index, rhs: Index) -> Bool { switch (lhs.node, rhs.node) { case let (left?, right?): return left.next === right.next case (nil, nil): return true default: return false } } static func <(lhs: Index, rhs: Index) -> Bool { guard lhs != rhs else { return false } let nodes = sequence(first: lhs.node) { $0?.next } return nodes.contains { $0 === rhs.node } } } var startIndex: Index { return Index(node: head) } var endIndex: Index { return Index(node: tail?.next) } func index(after i: Index) -> Index { return Index(node: i.node?.next) } subscript(position: Index) -> Value { return position.node!.value } }
If you want to be updated about similar snippets, Sign in and follow our Channels

blog comments powered by Disqus