数据结构与算法-链表-一一网

这是我参与更文挑战的第11天，活动详情查看：更文挑战

数组是软件开发过程中非常重要的一种数据结构，但是数组至少有两个局限：

编译期需要确定元素大小
数组在内存中是连续的，插入或者删除需要移动数组中其他数据

数组适合处理确定长度的，对于插入或者删除不敏感的数据。如果数据是频繁变化的，就需要选择其他数据结构了。链表是一种逻辑简单的、实用的数据结构，

单链表、
1. 每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址
2. 头结点(链表的基地址)
3. 尾结点
循环链表
1. 循环链表的尾结点指针是指向链表的头结点
双向链表
1. 双向链表需要额外的两个空间来存储后继结点和前驱结点的地址；比较费内存
2. 插入、删除比较高效

用空间换时间的设计思想

当内存空间充足的时候，如果我们更加追求代码的执行速度，我们就可以选择空间复杂度相对较高、但时间复杂度相对很低的算法或者数据结构。相反，如果内存比较紧缺，比如代码跑在手机或者单片机上，这个时候，就要反过来用时间换空间的设计思路

数据和链表对比

数组需要连续的内存空间，可以借助CPU的缓存机制，预读数组中的数据，所以访问效率更高
大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配给它，导致“内存不足（out of memory）”。申明过下，下次再次操作需要先拷贝过去，非常费时；链表动态扩容
链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。（数组中插入、删除数据项时，需要移动其它数据项，非常繁琐）链表必须根据next指针找到下一个元素
链表从堆中分配空间, 自由度大但是申请管理比较麻烦
从上面的比较可以看出，如果需要快速访问数据，很少或不插入和删除元素，就应该用数组；相反，如果需要经常插入和删除元素就需要用链表数据结构了。

使用swift实现数据链表

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

let node1 = Node(value: "A")
let node2 = Node(value: "B")
let node3 = Node(value: "C")
node1.next = node2
node2.next = node3
//  print(node1.description)

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

/// 扩张push方法
extension LinkedList {
    public mutating func push(_ value: Value) {
        head = Node(value: value, next: head)
        if tail == nil {
            tail = head
        }
    }
}

/// 扩张append方法
extension LinkedList {
    public  mutating func append(_ value: Value) {
        guard !isEmpty else
        {
            push(value)
            return
        }
        tail?.next = Node(value: value)
        tail = tail?.next
    }
}

/// 扩张insert方法，指定插入
extension LinkedList {
    
    public mutating func insert(_ value:Value, after node:Node<Value>)->Node<Value> {
        guard tail !== node else {
            append(value)
            return tail!
        }
        node.next = Node(value: value, next: node.next)
        return node.next!
    }
}

// Test
var linked = LinkedList<String>()
linked.head = node1
linked.tail = node2
print(linked.description)

//  linked.push(value: <#T##String#>)
linked.push("E")
linked.push("D")
linked.push("F")
//  linked.tail = node1
print(linked.description)
linked.insert("AA", after: node1)
print(linked.description)


///结果
A -> B -> C
F -> D -> E -> A -> B -> C
F -> D -> E -> A -> AA -> B -> C

复制代码