数据结构算法--003：双向链表与双向循环链表 - 《数据结构算法》

1. 双向链表
2. 双向循环链表
总结

1. 双向链表

单向链表的指针只能往一个方向移动，如果要找到某一元素的前驱，必须从指针L开始向后移动查找。如果是单向循环链表，也可以从该元素开始，向后移动一轮从而找到前驱元素

所以单向链表和单向循环链表在查找前驱元素时，都需要进行遍历，时间复杂度为O(n)

双向链表在单向链表的基础上进行了一些调整，单向链表中只有一个后继的指针域，而双向链表中保存了前驱后后继两个指针域

1.1 头结点

设计双向链表时，可以选择是否加入头结点

带有头结点的非空双向链表

带有头结点后，首元结点也有了前驱元素，在插入时和其他结点逻辑一致
尾结点没有后继元素，所以它的next指针域一定为空

不带有头结点的非空双向链表

不带头结点，对首元结点的插入和删除，都需要加入额外判断处理L指针，逻辑会相对复杂

1.2 创建

创建带有头结点的双向链表，并对其添加元素：

头结点的next指向新结点
新结点的prior指向头结点

代码实现：

import Foundation
public struct DoublyLinkedList<Element>{
    fileprivate class Node<T> {
        var prior : Node<T>?;
        var next : Node<T>?;
        var data : T?;
        init(){
        }
        init(data : T){
            self.data = data;
            self.prior = nil;
            self.next = nil;
        }
        deinit {
            print("值为\(data!)的Node释放");
        }
    }
    fileprivate var _head : Node<Element>? = nil;
    private var _length : Int = 0;
    fileprivate var _r : Node<Element>? {
        get{
            var node = _head;
            while(node?.next != nil){
                node = node?.next;
            }
            return node;
        }
    };
    public init(){
        _head = Node<Element>();
    }
    func length() -> Int {
        return _length;
    }
    fileprivate func capacity() -> Int {
        return length() + 1;
    }
    mutating func pushTail(element : Element) -> Int{
        let node = Node<Element>(data: element);
        let lastNode = _r;
        lastNode?.next = node;
        node.prior = lastNode;
        _length += 1;
        return OK;
    }
}

双向链表带有头结点
添加元素采用后插法
只读属性r，访问时获取尾结点

1.3 插入

双向链表的插入，找到指定位置的前驱结点：

插入节点时，指针变换情况：

找到插入位置的前驱结点，指针p指向该结点
p.next结点的prior指向新结点，新结点的next指向p.next结点
前驱结点的next指向新结点，新结点的prior指向前驱结点

代码实现：

public struct DoublyLinkedList<Element>{

    func getElem(locate : Int) -> Element? {

        if(locate < 1 || locate > length()){
            return nil;
        }

        let node = getNode(index: locate);

        if(node == nil){
            return nil;
        }

        return node!.data;
    }

    fileprivate func getNode(index : Int) -> Node<Element>? {

        if(index < 0 || index > length()){
            return nil;
        }

        var i = 0;
        var node = _head;

        while(node != nil && i < index){
            node = node?.next;
            i += 1;
        }

        return node;
    }

    mutating func insetr(locate : Int, element : Element) -> Int {

        if(locate < 1 || locate > capacity()){
            return ERROR;
        }

        let node = Node<Element>(data: element);
        return insetrNode(locate: locate, node: node);
    }

    fileprivate mutating func insetrNode(locate : Int, node : Node<Element>) -> Int {

        let index = locate - 1;
        let ptr = getNode(index: index);

        ptr?.next?.prior = node;
        node.next = ptr?.next;

        node.prior = ptr;
        ptr?.next = node;

        _length += 1;

        return OK;
    }
}

1.4 删除

删除时的指针变换情况：

找到即将删除的元素
该元素的前驱的next指向该元素的后继
该元素的后继的prior指向该元素的前驱

1.4.1 删除指定位置结点

找到指定位置的结点，进行删除操作

代码实现：

public struct DoublyLinkedList<Element>{

    mutating func delete(locate : Int) -> Element? {

        if(locate < 1 || locate > length()){
            return nil;
        }

        let ptr = getNode(index: locate);

        if(ptr == nil){
            return nil;
        }

        let data = ptr?.data;

        ptr?.prior?.next = ptr?.next;
        ptr?.next?.prior = ptr?.prior;

        _length -= 1;

        return data;
    }
}

1.4.2 删除指定内容结点

遍历结点，数据相等则删除该结点，跳出循环

代码实现：

public struct DoublyLinkedList<Element: Equatable>{

    mutating func delete(element : Element) {

        var node = _head?.next;

        while(node != nil){

            if(node?.data == element){
                node?.prior?.next = node?.next;
                node?.next?.prior = node?.prior;
                _length -= 1;
                break;
            }

            node = node?.next;
        }
    }
}

1.5 查找元素在链表中的位置

遍历结点，每查找一次位置+1，数据相等直接返回位置，否则返回0

代码实现：

public struct DoublyLinkedList<Element: Equatable>{

    func getLocate(element : Element) -> Int {

        var locate = 1;

        var node = _head?.next;

        while(node != nil){

            if(node?.data == element){
                return locate;
            }

            node = node?.next;
            locate += 1;
        }

        return 0;
    }
}

1.6 替换指定位置的元素

找到指定位置的结点，记录原始数据，替换新数据，将原始数据返回

代码实现：

public struct DoublyLinkedList<Element: Equatable>{

    func replace(locate : Int, element : Element) -> Element? {

        if(locate < 1 || locate > length()){
            return nil;
        }

        let node = getNode(index: locate);

        if(node == nil){
            return nil;
        }

        let data = node?.data;
        node?.data = element;

        return data;
    }
}

2. 双向循环链表

双向循环链表在结点上和双向链表是一致的，区别在于首元结点的前驱指向尾结点，尾结点的后继指向首元结点

设计双向循环链表时，依然可以加入头结点。当头结点的前驱和后继都指向自己，证明当前为空链表

非空的双向循环链表：

头结点的前驱指向尾结点
尾结点的后继指向头结点
当一个结点的后继等于头结点时，该结点为尾结点

2.1 创建

代码实现：

import Foundation

public struct DoublyCircularLinkedList<Element: Equatable>{

    fileprivate class Node<T> : Equatable{

        static func == (lhs: DoublyCircularLinkedList<Element>.Node<T>, rhs: DoublyCircularLinkedList<Element>.Node<T>) -> Bool {
            let obj1 = Unmanaged<AnyObject>.passUnretained(lhs).toOpaque();
            let obj2 = Unmanaged<AnyObject>.passUnretained(rhs).toOpaque();

            return obj1 == obj2;
        }

        var prior : Node<T>?;
        var next : Node<T>?;
        var data : T?;

        init(){

        }

        init(data : T){
            self.data = data;
            self.prior = nil;
            self.next = nil;
        }

        deinit {
            print("值为\(data!)的Node释放");
        }
    }

    fileprivate var _head : Node<Element>? = nil;
    private var _length : Int = 0;

    fileprivate var _r : Node<Element>? {
        get{
            var node = _head;

            while(node?.next != _head){
                node = node?.next;
            }

            return node;
        }
    };

    public init(){
        _head = Node<Element>();
        _head?.prior = _head;
        _head?.next = _head;
    }

    func length() -> Int {
        return _length;
    }

    fileprivate func capacity() -> Int {
        return length() + 1;
    }

    mutating func pushTail(element : Element) -> Int{

        let node = Node<Element>(data: element);

        let lastNode = _r;

        lastNode?.next = node;
        node.prior = lastNode;

        node.next = _head;
        _head?.prior = node;

        _length += 1;

        return OK;
    }
}

创建头结点时，让它的前驱和后继都执行自身
使用r获取尾结点时，如果结点的后继等于头结点，将其返回
添加元素和双向链表的逻辑一致，增加新结点的后继和头结点的前驱处理逻辑

2.2 插入

代码实现：

public struct DoublyCircularLinkedList<Element: Equatable>{

    func getElem(locate : Int) -> Element? {

        if(locate < 1 || locate > length()){
            return nil;
        }

        let node = getNode(index: locate);

        if(node == nil){
            return nil;
        }

        return node!.data;
    }

    fileprivate func getNode(index : Int) -> Node<Element>? {

        if(index < 0 || index > length()){
            return nil;
        }

        var i = 0;
        var node = _head;

        while(node != nil && i < index){
            node = node?.next;
            i += 1;
        }

        return node;
    }

    mutating func insetr(locate : Int, element : Element) -> Int {

        if(locate < 1 || locate > capacity()){
            return ERROR;
        }

        let node = Node<Element>(data: element);
        return insetrNode(locate: locate, node: node);
    }

    fileprivate mutating func insetrNode(locate : Int, node : Node<Element>) -> Int {

        let index = locate - 1;
        let ptr = getNode(index: index);

        ptr?.next?.prior = node;
        node.next = ptr?.next;

        node.prior = ptr;
        ptr?.next = node;

        _length += 1;

        return OK;
    }
}

插入元素和双向链表的逻辑完全一致

2.3 删除

代码实现：

public struct DoublyCircularLinkedList<Element: Equatable>{

    mutating func delete(locate : Int) -> Element? {

        if(locate < 1 || locate > length()){
            return nil;
        }

        let ptr = getNode(index: locate);

        if(ptr == nil){
            return nil;
        }

        let data = ptr?.data;

        ptr?.prior?.next = ptr?.next;
        ptr?.next?.prior = ptr?.prior;

        _length -= 1;

        return data;
    }
}

删除元素和双向链表的逻辑完全一致

总结

双向链表：

双向链表中保存了前驱后后继两个指针域

带有头结点的非空双向链表：

带有头结点后，首元结点也有了前驱元素，在插入时和其他结点逻辑一致
尾结点没有后继元素，所以它的next指针域一定为空

不带有头结点的非空双向链表：

不带头结点，对首元结点的插入和删除，都需要加入额外判断处理L指针，逻辑会相对复杂

创建带有头结点的双向链表，并对其添加元素：

头结点的next指向新结点
新结点的prior指向头结点

双向链表的插入：

找到插入位置的前驱结点，指针p指向该结点
p.next结点的prior指向新结点，新结点的next指向p.next结点
前驱结点的next指向新结点，新结点的prior指向前驱结点

双向链表的删除：

找到即将删除的元素
该元素的前驱的next指向该元素的后继
该元素的后继的prior指向该元素的前驱

查找元素在链表中的位置：

遍历结点，每查找一次位置+1，数据相等直接返回位置，否则返回0

替换指定位置的元素：

找到指定位置的结点，记录原始数据，替换新数据，将原始数据返回

双向循环链表：

双向循环链表在结点上和双向链表是一致的，区别在于首元结点的前驱指向尾结点，尾结点的后继指向首元结点
设计双向循环链表时，依然可以加入头结点。当头结点的前驱和后继都指向自己，证明当前为空链表

非空的双向循环链表：

头结点的前驱指向尾结点
尾结点的后继指向头结点
当一个结点的后继等于头结点时，该结点为尾结点

双向循环链表的创建：

创建头结点时，让它的前驱和后继都执行自身
使用r获取尾结点时，如果结点的后继等于头结点，将其返回
添加元素和双向链表的逻辑一致，增加新结点的后继和头结点的前驱处理逻辑

双向循环链表的插入和删除：

插入和删除元素，和双向链表的逻辑完全一致