数据结构和算法- 简单链表代码（swift）

日常平常的开发，会用到大量集合类型，平常我们常说： 数据结构就是指一组数据的存储方式，算法就是操作数据的一组方法，数据结构是为算法服务的，算法要作用在特定的数据结之上，算法和数据结构相辅相成。 代码执行起来性能好的好坏是一个非常重要的一个标准，平常写的业务逻辑基本不考虑性能，先开发完再说，但是越到后面可能就是写写业务。反正早点意识到越早弄对自己未开发展是越好，掌握了数据结构和算法，看待问题的深度和解决角度完全不一样。

线性和非线性

线性表：就是把数据排列成一条线一样的数据结构，每个线性表上的数据最多只有前后两个方法平常我们用的数组、链表、队列、栈等也是线性表结构。

非线性表：在数据之中非先后关系，如二叉树，堆，图等。 无论是那种链表，

最基本的保证操作要实现增删查改的功能。

数组

既然它这么好，好奇驱使的我打开大门一探究竟。说道集合，第一想到就是数组，数组就是一个线性表的结构.它是一组连续的内存空间，来存储一组具有相同类型的数据.

我们知道，计算机会给每个内存分配一个地址，计算机通过地址来访问内存中的数据，当计算机需要随机访问的时候，它会通过下面的寻址公式，计算出该元素存储的内存地址

a[i]_address = base_address + i * data_type_size

对于大多数的编程语言，数组要从0开始编号，而不是1呢。从数组存储内存模型来看，“下标”最确切的定义应该是偏移（offset）.前面讲到，如果用a来表示数组的首地址，a[0]就是表示数组的首地址，偏移为0的位置，所以a[k]就表示偏移K个type_size的位置，

a[k]_address = base_address + k * type_size

而如果数组从1开始计算，那我们计算数组的元素 a[k]的内存地址就会变为

a[k]_addrss = base_address + (k - 1) * type_size 

我们发现从1开始编号，每次随机访问数组元素多了一次减法运算，对于CPU来说，就多了一层减法

链表

我第一次看到链表的时候，丈二和尚摸不着头脑这用编程怎么实现了，走了很多弯路，入手链表之前，就必须懂指针的概念，指针，就是存储所指对象内存地址。具体来说将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来，指针存储了这个变量的内存地址，指向这个变量，通过指针就可以找到这个变量

在链表中我们经常发些有这样的代码： p -> next = q 可以这样说p结点中的next指针存储q结点的内存地址。还有一个更复杂的：p -> next = p -> next -> next。这行代码表示P结点的next地址存储了p结点下下一个结点的内存地址，这也是删除最后结点赋值代码。

首先是结点的声明：

final class LinkedListNode<T> {
    var value: T
    var next: LinkedListNode?
    init(value: T, next: LinkedListNode? = nil) {
        self.value = value
        self.next = next
    }
}
extension LinkedListNode: CustomStringConvertible {

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

结点使用：

        let node1 = LinkedListNode(value: 1)
        let node2 = LinkedListNode(value: 2)
        let node3 = LinkedListNode(value: 3)
        node1.next = node2
        node2.next = node3
        print(node1)
        // 结果
        1 -> 2 -> 3

我们创建一个链表LinkedList定义为Struct类型，同时也是泛型

struct LinkedList<T> {

    var head: LinkedListNode<T>?

    var tail: LinkedListNode<T>?

    init() {}
}

extension LinkedList: CustomStringConvertible {

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

extension LinkedList {

    var isEmpty: Bool {

        return head == nil
    }
}

head是第一个结点，tail最后一个结点，另外还添加了isEmpty属性，方便以后使用

链表添加元素

extension LinkedList {

    //链表大多数都是处理的边界问题

    mutating func append(_ value: T) {

        guard !isEmpty else {

            let node = LinkedListNode(value: value)
            
            head = node
            
            tail = node

            return

        }

        let next = LinkedListNode(value: value)

        tail?.next = next

        tail = next

    }

    mutating func insert(_ value: T, after node: LinkedListNode<T>) {

        guard tail !== node else { append(value) ; return }   //不仅内容要相同，地址也要相同

        node.next = LinkedListNode(value: value , next: node.next)

        //node.next  指的是下一个指针
    }
  }

append操作中如果链表为空，把头结点和尾结点都赋值为Node，然后把就原来尾结点next指向新的结点，尾结点等于新的结点

链表删除操作

    //链表大多数都是处理的边界问题
    mutating func removeLast() -> T? {

        guard let head = head else {
            return nil
        }

        guard head.next != nil else {

            let headValue = head.value

            self.head = nil

            tail = nil

            return headValue

        }

        var prev = head

        var current = head

        while let next = current.next {

            prev = current

            current = next
        }

        prev.next = nil

        tail = prev

        return current.value

    }
    
    mutating func remove(after node: LinkedListNode<T>) -> T? {

        defer {

            if node.next === tail {

                tail = node
            }

            node.next = node.next?.next
        }
        return node.next?.value
    }
}

在链表删除操作中，注意可能出现的边界问题：链表为空，链表只有一个元素，实例prev变量和current变量，prev属性做为中转存储，当遍历current到next为nil时候为止，prev就是为倒数第二个变量。

链表查找元素

extension LinkedList {

    func node(at index: Int) -> LinkedListNode<T>? {

        var currentNode = head

        var currentIndex = 0

        while currentNode != nil && currentIndex < index {

            currentNode = currentNode?.next

            currentIndex += 1
        }
        return currentNode
    }
}

链表查找操作： 从头结点开始一步一步遍历操作

性能分析

方法名	方法概述	时间复杂度
append()	在最后面添加元素	O(1)
insert(after:)	在某个节点后面添加元素	O(1)
removeLast()	移除最后一个元素	O(n)，n是元素个数，因为要从头开始找才能找到最后一个元素，所以为O(n)
remove(after:)	移除某一节点后面的元素	O(1)
node(at:)	查找某个index对应的元素	O(i)，i是指index，因为要从头开始找，所以为O(i)

实现链表的collection协议

为什么要实现一系列Collection协议？试想，首先链表能存储一系列的结点，实现Sequence协议很合理，并且链表结点是有限的，这也非常符合Collection协议的要求。实现Collection协议之后，我们能使用for-in循环，从苹果的文档中我们能看到实现Collection协议需要提供：

startIndex()
endIndex()
index(after:)
subscript(index: Index) -> T 

很重要的一点，通过index去访问元素的事件复杂度为O(i)，这也是和数组等线性集合不同的地方数组可以通过寻址公式很快找到指定的位置，而链表在内存中的存储可以不是连续的，通过结点中的next存储下一个元素的地址。所以没有办法满足Collection协议的要求，所以我们自定义了一个Index类型来存储对应的Node。Collection为什么这么做，某些集合操作的性能取决于集合提供的索引类型，性能需要

从代码实现可以看到，因为自定义的 Index 本身包含了 node，startIndex 可以直接获取到 head，endIndex 可以直接获取到 tail?.next，subscript 也是能直接获取到index 对应节点的值，所以很明显 时间复杂度都为 O(1)。

extension LinkedList: Collection {

    struct Index: Comparable {

        var node: LinkedListNode<T>?

        static func  == (lhs: Index, rhs: Index) -> Bool {

            switch (lhs.node, rhs.node) {

            case let (left?, right?):

                return left.next === right.next

            case (nil, nil):

                return true

            default:
                return false
            }
        }

        static func < (lhs: LinkedList<T>.Index, rhs: LinkedList<T>.Index) -> Bool {

            guard lhs != rhs else {
                return false
            }
            
            let nodes = sequence(first: lhs.node) { $0?.next }

            return nodes.contains { $0 === rhs.node }
        }
    }
    
    var startIndex: Index {

        return Index(node: head)
    }

    var endIndex: Index {
    
       return Index(node: tail?.next)
    }

    subscript(index: Index) -> T {
    
        return index.node!.value
    }
    
    func index(after i: Index) -> Index {

        return Index(node: i.node?.next)
    }
}

上面代码定义了Index类型，然后实现Collection协议要求的属性和方法，但是还要解释两点

sequence(first:)API解释是：返回由下一个的第一个和重复的惰性应用程序形成的序列。序列中的第一个元素总是第一个，每个后续元素都是调用前一个元素的next的结果。当next返回nil时，序列结束。如果next从不返回nil，则序列是无限的。 此函数可用于替换以前使用C样式for循环处理的许多情况。例如list存的值是1、2、3，如果你传入first参数是2的节点，那么nodes的值就是2，3 nodes.contains { $0 === rhs.node }如果接下来的数组序列有rhs，则返回true

最后我想扩展一下， Comparable这个协议对我们的自定义类型的意义在哪里：

struct Person: Comparable, CostomStringConvertible {
   static func <(lhs:Person, rhs:Person) -> Bool {
     if lhs.age == rhs.age {
       return lhs.name < rhs.name
     }
     return lhs.age < rhs.age
   }
   
   let age: Int
   let name:String
   
   var description: String {
      "\(name:\(age))"
   }
}

let p1 = Person(age: 25, name: "wade")
let p2 = Person(age: 25, name: "Lebron")

let persons = [p1, p2]
print("persons:\(persons)")

let sorted = persons.sorted()
print("sorted:\(sorted)")

打印结果
persons:[wade:25,Lebron:25]
sorted:[Lebron:25,wade: 25]

如果Person不实现Comparable协议，也可以调用这个对其排序
let sorted = persons.sorted{ lhs,rhs in
   if lhs.age == rhs.age {
      return lhs.name < rhs.name
   }
   return lhs.age < rhs.age
}

使得链表具有内容拷贝功能

Swift标准库的很多都是值类型，比如数组字典元组, 具有内容拷贝功能，

var list1  = LinkedList<Int>()
list1.append(1)
list1.append(2)
list1.append(3)

let list2 = list1

print("list1: \(list1)")
print("list2: \(list2)")

list1.append(4)

print("list1: \(list1)")
print("list2: \(list2)")

// 结果
list1: 1 -> 2 -> 3
list2: 1 -> 2 -> 3

============分割线=======
list1: 1 -> 2 -> 3 -> 4
list2: 1 -> 2 -> 3 -> 4

结果： 改变其中一个list，会影响另外一个list，说明目前我们的LinkedList是引用类型，造成这种现象的原因是我们底层存储节点LinkedListNode是Class类型，是一个引用类型，为了修复这个问题，我们需要在改变链表元素的方法里面先要对节点的复制。这时就会有疑问为什么一开始不用struct做内容复制而用了Class，主要是因为struct存储了下一个结点的地址，如果用了struct 就不是下一个结点的地址。

mutating func copyNodes() {
    guard !isKnownUniquelyReference(&head) else {return}
    guard var oldNode = head else { return }  // 头结点必须有
    
    head = LinkedListNode(value: oldNode.value)保证头结点有值
    var newNode = head
    while let nextOldNode = oldNode.next {
       let nextNewNode = LinkedList(value: nextOldNode.value)
       newNode?.next = nextNewNode
       newNode = nextNewNode   //当前新链表节点
       oldNode = nextOldNode  // 当前旧链表节点
    }
}

把copyNodes()方法添加到所有改变链表元素的方法最上面，方法包括：append(),insert(after:)。

LRU缓存淘汰算法

缓冲是一种提高数据读取的计算，但是缓存的大小有限，当缓存被用满的时候，系统就要决定哪些数据应该被清理出去，就比如下载图片，或者文件的时候，当app发生内存警告了，清理资源那种算法最优，就需要淘汰策略来决定，常见策略有三种，先进先出FIFO，最少使用策略LFU，最近最少使用策略LRU

我们维护一个有序的单链表，越靠近链表尾部的节点是越早之前访问的，当有一个新的数据被访问的时候，我们从链表头开始顺序遍历链表

如果此数据之前被缓存在链表中了，我们遍历得到这个数据对应的节点，并将其从原来的位置删除，然后再插入到链表头部 如果此时缓冲未满，则将此结点直接插入链表的头部，如果此时缓冲满了，则链表尾部结点删除，将新的数据结点插入链表头部

双向链表

双向列表需要额外的两个空间来存储后继节点和前驱节点地址，所以，存储同样多的数据，双向链表要比单链表占用更多的内存存储的空间，从双向列表的结构上它可以支持O(1)时间复杂度的情况下找到前驱结点，正式这样的特点，也使得双向链表在某些情况下得插入、删除等操作比单链表简单，高效。

双向链表尽管比较费内存，但是还是比单链表应用更加广泛，比如java语言中LikedHashMap这个容器实现的原理就是用双链表这种结构

总结

数组在插入，删除操作的时候，为了保持内存数据的连续性，需要做大量的数据搬移 所以时间复杂度是O(n)，而在链表中插入或者删除一个数据，我们并不需要为了保持内存的连续性搬移节点，因为链表的存储空间本身就不是连续的，所以链表插入和删除一个数据非常快速的

但是因为链表中的数据并非连续存储的，所以无法像数组那样做那样，根据首地址和下标，通过寻址公式就能直接找到对应的内存地址。 空间换时间，或者时间换空间，当内存空间充足的时候，如果我们更加追求代码的执行速度，我们可以选择空间复杂度相对较高，但是时间复杂度相对较低的算法，相反，如果内存比较紧缺的时候，可以消耗更多的时间（时间换空间）来减低内存的消耗 找个时间把自己学习到的，零零碎碎东西总结一下，主要是在写的时候多多去思考，然后把优秀代码，自己的问题想办法解决成为自己的东西。在学习中谢谢Lebron大佬一直以来对我指导

转载，参考Lebron大佬代码，点击这里查看原文