线性表

零个或多个数据元素的有限序列。

线性表的结构

• 顺序存储
• 链式存储

顺序存储结构

用一段地址连续的存储单元依次存储线性表的元素，因为地址是连续的，顺序存储结构元素读取很快，但是这个结构的线表进行插入以及删除等操作涉及到的元素的地址都要进行变换，都很不方便，于是衍生出下面那个链式的结构。
一个图：

34567的存储位置都要变更。

链式存储结构（链表）

链表的两种结构

• 单向链表：每一个节点的只有下一个节点的引用

• 双向链表：每一个节点有前一个和后一个节点的引用

每一个链表都有头节点以及尾节点：

实现一个双向链表

推荐研读Swift Algorithm Club: Swift Linked List Data Structure

构造一个节点类

public class Node{
    var value : String
    init(value:String){
        self.value = value
    }
}

value 可以是任意的数据类型，根据链表的用途来定。在最后一个章节用泛型来改造这个数据结构。

加入对下一个节点的引用

public class Node{
    var next : Node?
    var value : String
    init(value:String){
        self.value = value
    }
}

加入对上一个节点的引用

public class Node{
    var next : Node?
    weak var previous : Node?
    var value : String
    init(value:String){
        self.value = value
    }
}

建立一个链表类

public class List {
    fileprivate var head : Node?
    private var tail : Node?
    
    public var isEmpty : Bool{
        return head == nil
    }
    
    public var head : Node?{
        return head
    }
    
    public var tail : Node?{
        return tail
    }
}

让链表类可以添加节点元素

public class List {
    fileprivate var head : Node?
    private var tail : Node?
    
    public var isEmpty : Bool{
        return head == nil
    }
    
    public var head : Node?{
        return head
    }
    
    public var tail : Node?{
        return tail
    }
    
    public func append(value:String){
        let newNode = Node(value:value)
        
        if let tailNode = tail{
            newNode.previous = tailNode
            tailNode.next = newNode
        }else{
            head = newNode
        }
        
        tail = newNode
    }
}

List 类的实践

首先添加一个 List 的 extension 协助打印输出

extension List{
    public var description : String{
        var text = "["
        var node = head
        
        while node != nil{
            text += "\(node!.value)"
            node = node!.next
            if node != nil {
                text += " , "
            }
        }
        return text + "]"   
    }
}

let listt = List()
listt.append(value:"熊大")
listt.append(value:"熊二")
listt.append(value:"周末")
listt.append(value:"蛋蛋")

print(listt.description)

打印结果:

[熊大 , 熊二 , 周末 , 蛋蛋]

根据下标读取链表节点

由于链表的性质，从头结点开始读取，直到读到对应的下标停止并返回相应的节点。
给 List 类添加一个读取下标对应节点函数：

public func nodeAt(index:Int) -> Node? {
        if index >= 0 {
            var node = head
            var i = index
            
            while node != nil {
                if i == 0 {
                    return node
                }
                i -= 1
                node = node!.next
            }
        }
        return nil
    }

清空链表

只要将首节点与尾节点置为 nil 整个链表就会被置空。
给 List 添加函数：

public func removeAll() {
        head = nil
        tail = nil
    }

移除其中某个节点

移除节点的三种情况：

• 移除首节点：如图变更 Head 指针以及 Node1 的 previous 指针

• 移除尾节点：如图变更 Tail 指针以及 Node2 的 next 指针指为 nil。

• 移除非首尾节点：如图只需要变更被移除的 Node1 节点的上一个节点 Node0 的 next 指针指向 Node2，Node2 的 previous 指针指向 Node0，那么 Node1 节点就已经脱离了链表。

Screen Shot 2017-02-07 at 10.41.06 AM.png

给 List 添加移除节点函数：

public func remove(node: Node){
        let prev = node.previous
        let next = node.next
        
        if let prev = prev {
            prev.next = next
        }else {
            head = next
        }
        
        next?.previous = prev
        
        if next == nil {
            tail = prev
        }
        
        node.previous = nil
        node.next = nil
    }

在进行一次实践

代码：

let list = List()
list.append(value:"熊大")
list.append(value:"熊二")
list.append(value:"周末")
list.append(value:"蛋蛋")
print(list.description)

let node = list.nodeAt(index:1)
list.remove(node:node!)
print(list.description)

list.removeAll()
print(list.description)

输出：

[熊大 , 熊二 , 周末 , 蛋蛋]
[熊大 , 周末 , 蛋蛋]
[]

使用泛型来改造这个链表类

改造节点 Node 类

public class Node<T>{
    var next : Node<T>?
    weak var previous : Node<T>?
    var value : T
    init(value:T){
        self.value = value
    }
}

改造链表 List 类

public class List<T> {
    fileprivate var head : Node<T>?
    private var tail : Node<T>?
    
    public var isEmpty : Bool{
        return head == nil
    }
    
    public var first : Node<T>?{
        return head
    }
    
    public var last : Node<T>?{
        return tail
    }
    
    public func append(value:T){
        let newNode = Node(value:value)
        
        if let tailNode = tail{
            newNode.previous = tailNode
            tailNode.next = newNode
        }else{
            head = newNode
        }
        
        tail = newNode
    }
    
    public func nodeAt(index:Int) -> Node<T>? {
        if index >= 0 {
            var node = head
            var i = index
            
            while node != nil {
                if i == 0 {
                    return node
                }
                i -= 1
                node = node!.next
            }
        }
        return nil
    }
    
    public func removeAll() {
        head = nil
        tail = nil
    }
    
    public func remove(node: Node<T>){
        let prev = node.previous
        let next = node.next
        
        if let prev = prev {
            prev.next = next
        }else {
            head = next
        }
        
        next?.previous = prev
        
        if next == nil {
            tail = prev
        }
        
        node.previous = nil
        node.next = nil
    }
}

实践

利用泛型特性改造之后，这个链表类则可以储存任意类型的值，比较灵活。

输入：

let list = List<String>()
list.append(value:"熊大")
list.append(value:"熊二")
list.append(value:"周末")
list.append(value:"蛋蛋")

输出：

[熊大 , 熊二 , 周末 , 蛋蛋]

end