1.鏈表

• 鏈表是一種鏈式存儲的線性表，所有元素的內存地址不一定是連續(xù)的
• 鏈表可以用到多少申請多少，不浪費內存空間
• 鏈表中通常包含元素和下一個節(jié)點的地址
• 鏈表的尾結點中的下一個節(jié)點的地址為空

2.鏈表接口設計

• isEmpty:是否為空
• push:從head處添加
• append:從tail處添加
• insert(after:)指定位置添加
• pop:從表頭刪除
• removeLast:從結尾刪除
• remove(after:)任意位置刪除
• removeAll:清除所有元素
• getNode(index:)根據(jù)下標獲取到節(jié)點
• reverseNode()翻轉鏈表

2.鏈表swift實現(xiàn)

import Foundation

public class Node<Value>: CustomStringConvertible{
   
    public var value: Value?
    public var next: Node?
    public var size: Int = 0
    public init(value: Value, next: Node? = nil) {
        self.value = value
        self.next = next
    }
    
    // 重寫description方法，方便打印
    public var description: String{
        guard let next = next else {
            return "\(value!)"
        }
        return "\(value!) -> " + "\(next)"
    }
    
}


public class NodeList<Value> {
    public var node: Node<Value>?
    public var size: Int = 0
    public var head: Node<Value>?
    public var tail: Node<Value>?
    public var next: NodeList?
    public var value: Value?
    public init() {}

}

extension NodeList: CustomStringConvertible {
    /// 是否為空
    public func isEmpty() -> Bool {
        return head == nil
    }
   
    /// 從head處添加
    // 思路：創(chuàng)建新的head，并把之前的head設置為新head的next 
    public func push(_ value: Value) {
        head = Node(value: value, next: head)
        if tail == nil {
            tail = head
        }
        size += 1
    }

    /// 從tail處添加
    // 思路：創(chuàng)建新的tail，并把原來tial的next指向新的tial，新的tial的next為空  最后把新的tail覆蓋掉原來的tail
    public func append(_ value: Value){
        // 判斷鏈表為空
        guard !isEmpty() else {
            push(value)
            size += 1
            return
        }
        tail?.next = Node(value: value)
        tail = tail?.next
        size += 1
    }
    /// 指定位置添加
    // 思路：1.獲取到index-1的Node 2.創(chuàng)建新Node，并且新node的next指向index所在的node 3.index-1所在的node的next指向新創(chuàng)建的node
    public func insert(_ index: Int, value: Value){
        if index < 1 {
            push(value)
            size += 1
        }else {
            if index > size - 1 {
                append(value)
                size += 1
            }else {
                let preNode = getNode(index - 1)
                preNode?.next = Node(value: value, next: preNode?.next)
                size += 1
            }
        }
    }
    
    /// 從表頭刪除
    // 思路：head指向第二個node
    public func pop() {
        if isEmpty() {
            print("Empty list")
        }else {
            
            head = head?.next
            size -= 1
        }
    }
    
    /// 從結尾刪除
    // 思路：倒數(shù)第二個node的next置空
    // 如何獲取倒數(shù)第二個node 方式1 getNode取  方式2：兩個node,一個是pre 一個是cur,從頭循環(huán)遍歷，直到cur.next == nil為止，此時的pre就是倒數(shù)第二個node
        // 方式一
//    public func removeLast() {
//        if size == 0 {
//            return
//        }
//        if size == 1{
//            pop()
//        }else{
//
//            let node = getNode(size-2)
//            node?.next = nil
//            tail = node
//            size -= 1
//        }
//    }
    
    // 方式二：兩個node,一個是pre 一個是cur,從頭循環(huán)遍歷，直到cur.next == nil為止，此時的pre就是倒數(shù)第二個node
    public func removeLast() {
        guard head?.next != nil else {
            pop()
            return
        }
        var pre = head
        var cur = head?.next
        
        while cur?.next != nil {
            cur = cur?.next
            pre = pre?.next
        }
        pre?.next = nil
        tail = pre
        size -= 1
    }
    
    
    /// 任意位置刪除
    // 思路：把index-1的next指向index+1的node
    public func remove(_ index: Int) {
        if index < 0 || index > size - 1{
            print("下標輸入錯誤")
           return
        }
        if size == 1 || index == 0 {
            pop()
            return
        }
        if size == 2 {
            if index == 1 {
                head?.next = nil
                size -= 1
                return
            }
        } else {
            let preNode = getNode(index - 1)
            preNode?.next = preNode?.next?.next
            size -= 1
        }
        
    }
    
    /// 清除所有元素
    // 思路： heda置空 size歸零
    public func removeAll() {
        head = nil
        size = 0
    }
    
    /// 根據(jù)下標獲取到節(jié)點
    public func getNode(_ index: Int) -> Node<Value>?{
   
        var currentNode = head
        var currentIndex: Int = 0
        while currentNode != nil && currentIndex < index {
            currentNode = currentNode?.next
            currentIndex += 1
        }
    
        return currentNode
    }
    
    // 重寫description方法，方便打印
    public var description: String{
        guard let head = head else {
            return "Empty list"
        }
        return String(describing: head)
    }
}