算法--Swift--链表

算法不分语言,重要的是思想,这里我用swift来记录算法的实现,供大家一起学习.
首先我们看下链表的结构

1.单链表 屏幕快照 2017-12-04 上午11.53.23.png
2,双链表 屏幕快照 2017-12-04 上午11.55.11.png

我们主要讲解双链表

在这里我们创建一个链表类和节点类(下方代码)

/// 声明链表类
public final class LinkedList<T>{
    /// 声明节点类
    public class LinkedListNode<T>{
        var value: T
        var next: LinkedListNode<T>?
        weak var previous: LinkedListNode<T>? //这里使用week避免循环引用
        
        public init(value: T) {
            self.value = value
        }
    }

    /// 重命名节点类,方便使用
    public typealias Node = LinkedListNode<T>
    
    /// 链表头节点
    fileprivate var head: Node?
    
    /// 链表初始化
    public init() {}

}

下面为该链表添加基本的属性和方法

/// 判断链表是否空
    public var isEmpty: Bool {
        return head == nil
    }
    
    /// 获取链表第一个节点
    public var first: Node? {
        return head
    }
    
    /// 获取最后一个节点
    public var last: Node?{
        guard var node = head else {
            return nil
        }
        
        while let next = node.next {
            node = next
        }
        return node
    }
    
    /// 计算节点的个数
    public var count: Int {
        
        guard var node = head else {
            return 0
        }
        
        var count: Int = 1
        while let next = node.next {
            node = next
            count += 1
        }
        return count
    }
    
    /// 获得某个位置的节点
    ///
    /// - Parameter index: 链表中第几个节点(从0开始)
    /// - Returns: Optional LinkedListNode
    public func node(at index: Int) -> Node! {
        assert(head != nil ,"链表为空")
        assert(index >= 0, "index 必须大于等于0")
        
        if index == 0 {
            return head!
        }else {
            var node = head!.next
            for _ in 1..<index {
                node = node?.next
                if node == nil {
                    break
                }
            }
            assert(node != nil, "index 超出接线")
            return node!
        }
    }
    
    /// 获得指定下标节点的内容
    ///
    /// - Parameter index: 链表中第几个节点(从0开始)
    public func value(index: Int) -> T {
        let node = self.node(at: index)
        return node!.value
    }
    
    /// 添加一个节点到链表的尾部
    public func append(_ node: Node!){
        if head == nil {
            head = node
            return
        }
        
        last!.next = node
        node.previous = last
    }
    
    /// 添加一个value值到链表的尾部
    public func append(_ value: T) {
        let newNode = Node(value: value)
        self.append(newNode)
    }
    
    /// 插入一个节点到链表中
    public func insert(_ newNode: Node!, at index: Int) {
        if index == 0 {
            newNode.next = head
            head?.previous = newNode
            head = newNode
        }else {
            let nextNode = node(at: index)
            let previousNode = node(at: index - 1)
            
            newNode.next = nextNode
            nextNode?.previous = newNode
            
            newNode.previous = previousNode
            previousNode?.next = newNode
        }
    }
    
    /// 插入一个value到链表中
    public func insert(value: T, at index: Int){
        let newNode = Node(value: value)
        self.insert(newNode, at: index)
    }
    
    /// 移除所有的 node/value
    public func removeAll() {
        head = nil
    }
    
    /// 移除某个节点
    public func remove(node: Node!) {
        assert(head != nil, "该链表没有节点")
        
        let previousNode: Node? = node.previous
        let nextNode: Node? = node.next
        
        if previousNode == nil {
            head = nextNode
        }else{
            previousNode!.next = nextNode
            nextNode?.previous = previousNode
        }

        node.previous = nil
        node.next = nil
    }
    
    /// 移除指定位置的节点
    public func remove(at index: Int) {
        let node = self.node(at: index)
        self.remove(node: node)
    }

写完方法,让我们做下简单的测试吧,验证链表的正确性

let list = LinkedList<String>()
list.isEmpty                //true
list.first                  //nil
list.last                   //nil

list.append("小码儿")        //[小码儿]
list.isEmpty                //false
list.first!.value           //"小码儿"
list.last!.value            //"小码儿"
list.count                  //1

list.append("666")          //[小码儿,666]
list.first!.value           //"小码儿"
list.last!.value            //"666"
list.count                  //2

list.first!.previous        //nil
list.first!.next!.value     //"666"
list.last!.previous!.value  //"666"
list.last!.next             //nil

list.node(at: 0).value      //"小码儿"
list.node(at: 1).value      //"666"
list.insert(value: "mySwift", at: 1)  //[小码儿,mySwift,666]
list.remove(at: 1)          //[小码儿,666]

上方链表的基本操作都已经完成,为了更好的理解,现在让我们一起做下扩展吧:
1.扩展打印链表的方法,方便我们查看

/// 打印链表 当我们调用print 格式 ["value1","value2"]
extension LinkedList: CustomStringConvertible {
    public var description: String {
        var node = head
        var text: String = "["
        while node != nil {
            text += "\(node!.value)"
            node = node!.next
            if node != nil {
                text += ","
            }
        }
        return text + "]"
    }
}

2.将列表反转

//反转链表(通过迭代的方式反转,这里需要重点理解下)
extension LinkedList {
    public func reverse() {
        var node = head
        while let currentNode = node {
            node = currentNode.next
            swap(&currentNode.next, &currentNode.previous)
            head = currentNode
        }
    }
}

同时附上单链表的反转

/// 实现单链表的反转(迭代)
    public func reverseLinkList(){
        var node1: Node? = head
        var node2: Node? = nil
        var node3: Node? = nil
        
        while node1 != nil{
            node2 = node1
            node1 = node1!.next
            
            node2!.next = node3
            
            node3 = node2
            head = node2
        }
    }

今天先到这里,以后关于链表的问题会不断的补充进来