双向链表

双向链表的node分为三个部分，前驱结点，数据，后继结点

image.png

设计一个带有头结点的双向链表，优点在于当需要插入新结点的时候，不需要考虑index为第一个的情况。只需特殊判断插入为最后一个结点时，后续为空。

image.png

设计结点

class Node {
    
    var priod:Node?
    var data:Int?
    var next:Node?
    
}

双向链表插入，删除Swift实现

class LinkList {
    //创建双向链表
    func createLinkList() -> Node {
        
        let l = Node()
        l.priod = nil
        l.next = nil
        l.data = -1
        
        var p = l
        //新增10个结点
        for index in 0...9 {
            let temp = Node()
            temp.priod = nil
            temp.next = nil
            temp.data = index
            
            p.next = temp
            temp.priod = p
            p = temp
        }
        
        return l
    }

    //插入
    func insert(linkList:Node, index i:Int, value:Int) {
        
        let temp = Node()
        temp.data = value
        temp.priod = nil
        temp.next = nil
        
        //找到插入位置的前一个位置p
        var j = 1
        var p:Node? = linkList
        while j < i && p != nil {
            p = p?.next
            j += 1
        }
        
        if p == nil {
            return
        }
        
        //结点插入链表,先处理后继，再处理前驱
        if p!.next == nil {
            //当插入的结点为最后一个结点，temp的后继置空
            p!.next = temp
            temp.priod = p!
            temp.next = nil
        }else {
            p!.next?.priod = temp
            temp.next = p!.next
            p!.next = temp
            temp.priod = p!
        }
    }

    //删除
    func delete(linkList l:Node, index i:Int) {
        
        var j:Int = 1
        var p:Node? = l
        
        //指针找到待删除的结点的前一个位置
        while j < i && p != nil {
            p = p?.next
            j += 1
        }
        
        if j>i || p == nil {
            return
        }
        
        let toDel = p!.next
        p!.next = toDel!.next
        
        //判断是否是最后一个结点
        if toDel?.next != nil {
            toDel?.next?.priod = p!
        }
    }

    //打印链表
    func show(linkList l:Node) {
        
        var temp = l.next
        if temp == nil {
            print("双向链表为空")
            return
        }
        
        while temp != nil {
            print("data :: \(temp?.data ?? -1)")
            temp = temp?.next
        }
    }
}

let link = LinkList()
let l = link.createLinkList()
link.show(linkList: l)
link.insert(linkList: l, index: 1, value: 99)
link.insert(linkList: l, index: 8, value: 99)
print("did Insert")
link.show(linkList: l)
link.delete(linkList: l, index: 4)
link.show(linkList: l)

运行结果

98E38995-938D-4299-9C85-AC0DCB336FB7.png

双向循环列表

相对于双向链表，双向循环列表的尾结点指向首结点

image.png

双向循环链表插入，删除Swift实现

//双向循环链表
class CycleLinkList {

    func createLinkList() -> Node {
        let l = Node()
        l.next = l
        l.priod = l
        l.data = -1
        
        var p = l
        for index in 0...9 {
            let temp = Node()
            temp.data = index
            
            p.next = temp
            temp.priod = p
            temp.next = l
            p.priod = temp
            p = p.next!
        }
        
        return l
    }
    
    //插入
    func insert(linkList l:Node, index:Int, value:Int) {
        
        var p:Node? = l
        
        var i = 1
        while i < index {
            p = p?.next
            i += 1
        }
        
        if i > index {
            return
        }
        
        //创建
        let temp = Node()
        temp.data = value
        temp.priod = p
        temp.next = p?.next
        
        p?.next = temp
        if l !== temp.next {
            temp.next?.priod = temp
        }else {
            l.priod = temp
        }
    }
    
    //遍历
    func show(linkList l:Node) {
        
        var p = l.next
        while p !== l {
            print("data ==== \(p!.data ?? -1)")
            p = p?.next
        }
    }
    
    //删除
    func delete(linkList l:Node, index:Int) {
        var i = 1
        var temp = l.next
        //删除到只剩下首元结点了
        if temp?.next === l {
            return
        }
        
        //找到要删除的结点
        while i < index {
            temp = temp?.next
            i += 1
        }
        
        //修改被删除结点的前驱的后继指针
        temp?.priod?.next = temp?.next
        //修改被删除结点的后继结点的前驱指针
        temp?.next?.priod = temp?.priod
    }
    
}

let cLink = CycleLinkList()
let cL = cLink.createLinkList()
cLink.show(linkList: cL)

cLink.insert(linkList: cL, index: 2, value: 99)
cLink.insert(linkList: cL, index: 5, value: 88)
print("did Insert")
cLink.show(linkList: cL)

cLink.delete(linkList: cL, index: 3)
print("did Delete")
cLink.show(linkList: cL)

运行结果

image.png