数据结构是计算机存储、组织数据的方式
本文演示代码为Swift语言

数据结构

数据结构分为：

在实际开发中，根据使用场景来选择最合适的数据结构

动态数组

线性表是具有n个相同类型元素的有限序列(n>=0)。举个明显的例子：数组
数组是一种顺序存储的线性表，所有元素的内存地址是连续的
比如我们创建一个局部变量的array数组:let array = [1, 2, 3, 4, 5]，在内存当中的表现形式为：在一些编程语言当中，数组都有个致命的缺点：无法动态修改容量; 在实际开发当中，我们更希望数组的容量是可以动态改变的, 一般的做法是自己来实现动态数组

动态数组接口设计

动态数组的接口设计应尽可能的满足调用，下面是定义的接口

为了使自定义的动态数组可以添加任意类型，此处使用了泛型

// 是否为空
func isEmpty() -> Bool {
    return true
}

// 是否包含某个元素
func contains<T>(element: T) -> Bool {
    return true
}

// 添加元素到最后面
func add<T>(element: T) -> Void {
    
}

// 返回index位置对应的元素
func get<T>(index: Int) -> T {
    return nil
}

// 往index位置添加元素
func set<T>(index: Int, element: T) -> Void {
    
}

// 往index位置添加元素
func add<T>(index: Int, element: T) -> Void {
    
}

// 删除index位置对应的元素
func remove<T>(index: Int) -> T {
    return nil
}

// 查看元素的位置
func indexOf<T>(element: T) -> Int {
    return 0
}

// 清除所有元素
func clear() {
    
}

而自定义的动态数组，属性应该有：

// 动态数组的长度
var size: Int {
    get {
       return 0
    }
}
// 动态数组存储的元素
var elements: [T] = Array<T>()

完整的代码为：

class ArrayList<T: Comparable> {
    // 动态数组的长度
    var size: Int {
        get {
            return elements.count
        }
    }
    
    // 动态数组存储的元素
    var elements: [T] = Array<T>()
    
    // 常量，动态数组的默认容量
    private final let DEFAULT_CAPATICY: Int = 10;
    
    // 有参构造器
    init(capaticy: Int) {
        if capaticy >= 1 {
            self.elements.reserveCapacity(capaticy)
        }
        else {
            self.elements.reserveCapacity(DEFAULT_CAPATICY)
        }
    }
    
    // 无参构造器(默认容量是10)
    init() {
        elements.reserveCapacity(DEFAULT_CAPATICY)
    }
    
    // 是否为空
    func isEmpty() -> Bool {
        return self.elements.isEmpty;
    }
    
    // 是否包含某个元素
    func contains(element: T) -> Bool {
        return self.elements.contains(element)
    }
    
    // 添加元素到最后面
    func add(element: T) -> Void {
        self.elements.append(element)
    }
    
    // 往index位置插入元素
    func add(index: Int, element: T) throws -> Void {
        if index < 0 || index >= self.elements.capacity {
            throw VendingMathineError.indexOutOfBounds(index: index, size: self.size)
        }
        
        let length = self.elements.count - 1
        for i in length..<self.elements.count {
            elements[i+1] = elements[i]
        }
        elements[index] = element
    }
    
    // 返回index位置对应的元素
    func get(index: Int) throws -> T {
        if index < 0 || index >= self.size {
            throw VendingMathineError.indexOutOfBounds(index: index, size: self.size)
        }
        return self.elements[index]
    }
    
    /// 往index位置设置元素
    ///
    /// - Parameters:
    ///   - index: index
    ///   - element: element
    /// - Returns: 原来的元素
    func set(index: Int, element: T) throws -> T {
        if index < 0 || index >= self.size {
            throw VendingMathineError.indexOutOfBounds(index: index, size: self.size)
        }
        
        let old = self.elements[index]
        self.elements[index] = element;
        return old
    }
    
    // 删除index位置对应的元素
    func remove(index: Int) -> T {
        return self.elements.remove(at: index)
    }
    
    // 查看元素的位置
    func indexOf(element: T) -> Int {
        for i in 0..<self.elements.count {
            if self.elements[i] == element {
                return i
            }
        }
        return -1
    }
    
    // 清除所有元素
    func clear() {
        self.elements.removeAll()
    }
    
    func toString() {
        for i in 0..<self.elements.count {
            print("数组中存放元素有：\(self.elements[i])")
        }
    }
    
    enum VendingMathineError: Error {
        case invalidSelection
        case insufficientFunds(coinsNeed: Int)
        case indexOutOfBounds(index: Int, size: Int)
    }
}

var arr = ArrayList<Int>(capaticy: 5);
//let item = try? arr.get(index: 5)
print(arr.isEmpty())
print(arr.size)

arr.add(element: 10)
try? arr.add(index: 0, element: 20)
print(arr.toString())

动态数组扩容

当数组的容量已经到达临界值时，这时候就需要对数组扩容了，否则再向数组中添加元素是无法添加的
扩容的原理：在堆空间再次申请容量更大的数组(容量可以自己来设置，一般是初始容量*系数，OC当中大约是1.6，java当中大约是1.5)，然后将ArrayList的elements指向新申请的数组，这样旧数组由于没有任何指针指向就会自动销毁，同时将旧数组元素移动到新数组当中。这里就不做示例了

动态数组缩容

如果内存使用比较紧张，而动态数组又有比较多的剩余空间时，可以考虑对动态数组进行缩容操作
比如向动态数组中添加东西，添加到一定程度就会扩容，随后可能会对动态数组进行remove操作，这时必然就会有一部分剩余空间存在
缩容可以考虑一定的规则:

比如剩余空间占总容量的一半时，就进行缩容(总容量需要达到一定值，比如总容量达到100，而剩余空间达到了60个)
可以考虑一定的时机：
比如在做删除操作时进行

如果扩容倍数、缩容时机设计的不恰当，有可能会导致复杂度震荡
因为扩容和缩容时都需要创建新的数组，将旧数组元素移动过来

大部分程序语言当中都有动态数组，比如OC的NSMutableArray，java的java.util.ArrayList等等，swift当中系统也会对数组进行动态扩容，本文仅仅是演示数据结构的原理

本文首次发布于孙忠良 Blog, 作者 [@sunzhongliang] , 转载请保留原文链接.

数据结构-动态数组

数据结构

动态数组

动态数组接口设计

动态数组扩容

动态数组缩容

CATALOG

FEATURED TAGS

FRIENDS