003 - 链表的实现

1.链表

• 链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的
• 链表可以用到多少申请多少，不浪费内存空间
• 链表中通常包含元素和下一个节点的地址
• 链表的尾结点中的下一个节点的地址为空

2.链表接口设计

• isEmpty:是否为空
• push:从head处添加
• append:从tail处添加
• insert(after:)指定位置添加
• pop:从表头删除
• removeLast:从结尾删除
• remove(after:)任意位置删除
• removeAll:清除所有元素
• getNode(index:)根据下标获取到节点
• reverseNode()翻转链表

2.链表swift实现

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处添加
    // 思路：创建新的head，并把之前的head设置为新head的next 
    public func push(_ value: Value) {
        head = Node(value: value, next: head)
        if tail == nil {
            tail = head
        }
        size += 1
    }

    /// 从tail处添加
    // 思路：创建新的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.创建新Node，并且新node的next指向index所在的node 3.index-1所在的node的next指向新创建的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
        }
    }
    
    /// 从结尾删除
    // 思路：倒数第二个node的next置空
    // 如何获取倒数第二个node 方式1 getNode取  方式2：两个node,一个是pre 一个是cur,从头循环遍历，直到cur.next == nil为止，此时的pre就是倒数第二个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,从头循环遍历，直到cur.next == nil为止，此时的pre就是倒数第二个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
    }
    
    /// 根据下标获取到节点
    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)
    }
}