链表

节点

链表是由一串节点组成的，节点有两个职责

• 1. value值
• 2. 持有指向下一个node的引用，如果该引用为nil，则该node是链表的结尾。

1574614470521.jpg

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
  }
}

extension Node: CustomStringConvertible {

  public var description: String {
    guard let next = next else {
      return "\(value)"
    }
    return "\(value) -> " + String(describing: next) + " "
  }
}

接下来我们创建创建3个node，并连接它们

   func testNode(){
        let node1 = Node(value: 1)
        let node2 = Node(value: 2)
        let node3 = Node(value: 3)
        
        node1.next = node2
        node2.next = node3
        
        print(node1)
    }

输出如下
1 -> 2 -> 3

链表

public struct LinkedList<Value> {

  public var head: Node<Value>?
  public var tail: Node<Value>?
  
  public init() {}

  public var isEmpty: Bool {
    return head == nil
  }
}

extension LinkedList: CustomStringConvertible {

  public var description: String {
    guard let head = head else {
      return "Empty list"
    }
    return String(describing: head)
  }
}

链表都有一个head和tail，分别代表着链表的第一个元素和最后一个元素 1574615495292.jpg

push

在链表的头部插入一个节点（head-first insertion）

public mutating func push(_ value: Value) {
  head = Node(value: value, next: head)
  if tail == nil {
    tail = head
  }
}

接下来我们使用push添加节点

 func testLinkPush() {
        var list = LinkedList<Int>()
        list.push(3)
        list.push(2)
        list.push(1)
        print(list)
 }

输出如下
1 -> 2 -> 3

append

在链表的尾部添加节点

public mutating func append(_ value: Value) {

  guard !isEmpty else {
    // 如果为空链表
    push(value)
    return
  }
  
  //链表当前的尾部的next指向新节点
  tail!.next = Node(value: value)
  
  // 设置链表的新的尾部
  tail = tail!.next
}

使用append方法添加新节点

func testLinkAppend() {
        var list = LinkedList<Int>()
        list.append(1)
        list.append(2)
        list.append(3)
        print(list)
}

输出如下
1 -> 2 -> 3

insert(after:)

在链表中插入新节点需要两步：
1. 在链表中找到该node
2. 插入新的node
根据给的index通过遍历链表元素得到该位置的node值

   public func node(at index: Int) -> Node<Value>? {
        var currentNode = head
        var currentIndex = 0 // 索引
        
        while  currentIndex < index && currentNode != nil  {
            currentNode = currentNode?.next // 查找下一个
            currentIndex += 1
        }
        return currentNode
    }

在给定node后面插入新的节点

    @discardableResult // 忽略函数返回值
    public mutating func insert(_ value: Value, after node: Node<Value>) -> Node<Value> {
        // 如果node为函数的尾部，直接在尾部添加元素
        guard tail !== node else {
            append(value)
            return tail!
        }
        
        let insertNode = Node(value: value)
        insertNode.next = node.next
        node.next = insertNode
//        node.next = Node(value:  value, next: node.next)
        return node.next!
    }

性能分析

	push	append	insert(after:)	node(at:)
Behaviour	insert at head	insert at tail	insert after a node	return a node at given index
Time complexity	O(1)	O(1)	O(1)	O(i),where I is the given index

从链表中移除值

• 1.pop: 从列表的头部移除元素
• 2.removeLast: 从链表的的最后面移除元素
• 3.remove(at:): 从列表中移除任意值

pop operations

    @discardableResult
    public mutating func pop() -> Value?{
        // 延迟执行
        defer {
            head = head?.next
            if isEmpty {
                tail = nil
            }
        }
        return head?.value
    }

removeLast operations

移除最后一个元素：通过while循环找到倒数第二个元素，将该元素的next置为nil，并设置为链表的tail

    @discardableResult
    public mutating func removeLast() -> Value?{
        guard let head = head else {
            //空链表
            return nil
        }
        
        guard head.next != nil else {
            // 只有一个元素
            return pop()
        }
        
        var preNode = head
        var currentNode = head
        // 找到倒数第二个元素
        while let next = currentNode.next {
            preNode = currentNode
            currentNode = next
        }
        // 将next置空，设置为tail
        preNode.next = nil
        tail = preNode
        return currentNode.value
    }

remove(after:)

删除链表中的某一元素

1574696403011.jpg

@discardableResult
public mutating func remove(after node: Node<Value>) -> Value? {  
     defer {
          if node.next === tail {
              tail = node
          }
            node.next = node.next?.next
     }
        return node.next?.value
 }