顺序存储

1585797224843.jpg

在iOS开发中，苹果已经帮我们封装好了Array.
为了探究其原理，我们自己来简单实现下Array中的插入和删除功能。

let maxSize:Int = 100
class CustomArray {

    var length:Int = 0
    var values:[Int] = Array.init(repeating: NSNotFound, count: maxSize)
    
    //顺序表的插入
    func insert(index:Int, value:Int) {
        if index>length || index<0 {
            return
        }
        
        //插入数据不在表尾，则先移动出空余位置
        if index < length {
            for (orgIndex, node) in values.enumerated() {
                if orgIndex >= index && orgIndex+1 < maxSize {
                    values[orgIndex+1] = node
                }
            }
        }
        
        values[index] = value
        
        length += 1
    }
    
    //顺序表的删除
    func delete(index:Int) {
        //表为空
        if length == 0 { return }
        //超出范围
        if index >= length { return }
        
        for (orgIndex, _) in self.values.reversed().enumerated() {
            //被删除元素之后的元素向前移动
            if orgIndex > index {
                values[orgIndex-1] = values[orgIndex]
            }
        }
        length -= 1
    }
}

线性表链式存储

//线性表链式存储
class LinkList: NSObject {
    
    var linkList:Node?
    
    //初始化
    func initList() {
        linkList = Node()
        linkList?.next = nil
    }
    
    //遍历
    func listTraverse() {
        var p = linkList?.next
        while p != nil {
            print("value::\(p!.data ?? -1)")
            p = p?.next
        }
        print("\n")
    }
    
    //插入
    func insert(index i:Int, value:Int) {
        var p:Node = linkList!
        var j:Int = 0
        //寻找第index-1个节点
        while (j<i) {
            p = p.next!
            j += 1
        }
        
        //生成新节点s
        let s:Node = Node()
        s.data = value
        s.next = p.next
        p.next = s
    }
    
    //删除
    func delete(index i:Int) {
        
        //查找第index-1个结点
        var p:Node = linkList!
        var j:Int = 0

        while j<i {
            p = p.next!
            j += 1
        }
        
        if p.next == nil || j>i {
            return
        }
        
        //q指向要删除的结点
        var q:Node = p.next!
        
        //将q的后继赋值给p的后继
        p.next = q.next
        
    }
}