链表(下)

Tuesday, April 16, 2019

swift实现链表

创建结点对象

<code class="language-swift">public class Node<Value> {
    public var value: Value
    public var next: Node?

    public init(value: Value, next: Node? = nil) {
        self.value = value
        self.next = next
    }
}</code>

创建链表

<code class="language-swift">public struct LinkedList<Value> {
    public var head: Node<Value>?
    public var tail: Node<Value>?

    public init() {}

}</code>

判断是否为空链表

<code>public var isEmpty: Bool {
    return head == nil
}</code>

头部推入

<code class="language-swift">public mutating func push(_ value: Value) {
    head = Node(value: value, next: head)
    if tail == nil {
        tail = head
    }
}</code>

尾部添加

<code class="language-swift">public mutating func append(_ value: Value) {
    guard !isEmpty else {
        push(value)
        return
    }
    tail!.next = Node(value: value)
    tail = tail!.next
}</code>

插入

<code class="language-swift">public func node(at index: Int) -> Node<Value>? {
    var currentNode = head
    var currentIndex = 0

    while currentNode != nil && currentIndex < index {
        currentNode = currentNode!.next
        currentIndex += 1
    }
    return currentNode
}

@discardableResult
public mutating func insert(_ value: Value, after node: Node<Value>) -> Node<Value> {
    guard tail !== node else {
        append(value)
        return tail
    }
    node.next = Node(value: value, next: node.next)
    return node.next!
}
</code>

弹出头部

<code class="language-swift">@discardableResult
public mutating func pop() -> Value? {
    defer {
        head = head?.next
        if isEmpty {
            tail = nil
        }
    }
    return head?.value
}</code>

移除尾部

<code class="language-swift">@discardableResult
public mutating func removeLast() -> Value? {
    guard head = head else {
        return nil
    }

    guard head.next != nil else {
        return pop()
    }

    var prev = head
    var current -head

    while next = current.next {
        prev = current
        current = next
    }

    prev.next = nil
    tail = prev
    return current.value
}</code>

删除结点

<code class="language-swift">@discardableResult
public mutating func remove(after node: Node<Value>) -> Value? {
    defer {
        if node.next === tail {
            tail = node
        }
        node.next = node.next
    }
    return node.next?.value
}</code>
数据结构-算法

链表(上)