单向循环链表的特点：最后一个数据元素的指针域，指向首元结点
image.png

  • 设计一个循环链表时，也可以增加头结点降低逻辑复杂度

1. 创建

循环链表在创建元素时分为两种情况：

  • 当循环链表为空表时，第一次创建元素

  • 当循环链表非空表时，创建更多元素

【情况一】当循环链表为空表时，只存在一个指针。创建第一个元素时，创建新结点并赋值，将指针域指向自身
image.png

【情况二】当循环链表非空表时，假设采用后插法，需要先找到链表的结尾位置，然后创建新结点并赋值，将尾结点的指针域指向新结点，将新结点的指针域指向首元结点
image.png

1.1 通过循环找到尾结点

  1. import Foundation
  3. public struct CircularLinkedList<Element>{
  5.     fileprivate class Node<T>: Equatable {
  7.         static func == (lhs: CircularLinkedList<Element>.Node<T>, rhs: CircularLinkedList<Element>.Node<T>) -> Bool {
  8.             let obj1 = Unmanaged<AnyObject>.passUnretained(lhs).toOpaque();
  9.             let obj2 = Unmanaged<AnyObject>.passUnretained(rhs).toOpaque();
  11.             return obj1 == obj2;
  12.         }
  14.         var next : Node<T>?;
  15.         var data : T?;
  17.         init(data : T){
  18.             self.data = data;
  19.             self.next = nil;
  20.         }
  22.         deinit {
  23.             print("值为\(data!)的Node释放");
  24.         }
  25.     }
  27.     fileprivate var _head : Node<Element>? = nil;
  28.     private var _length : Int = 0;
  30.     func length() -> Int {
  31.         return _length;
  32.     }
  34.     mutating func pushTail(element : Element) -> Int{
  36.         let node = Node<Element>(data: element);
  38.         if(_head == nil){
  39.             _head = node;
  40.         }
  41.         else{
  42.             var lastNode = _head;
  44.             while(lastNode?.next != _head){
  45.                 lastNode = lastNode?.next;
  46.             }
  48.             lastNode?.next = node;
  49.         }
  51.         node.next = _head;
  52.         _length += 1;
  54.         return OK;
  55.     }
  56. }

1.2 使用指针记录尾结点

import Foundation

public struct CircularLinkedList<Element>{

    fileprivate class Node<T>: Equatable {

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

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

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

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

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

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

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

        if(_head == nil){
            _head = node;
        }
        else{
            _r?.next = node;
        }

        node.next = _head;
        _r = node;

        _length += 1;

        return OK;
    }
}

2. 插入

循环链表在插入元素时分为两种情况：

  • 插入的位置是首元结点

  • 插入到其他位置

【情况一】插入的位置是首元结点
image.png

  • 判断插入位置是否在首元结点上

  • 创建新结点，并赋值新结点

  • 新结点指针域指向之前的首元结点，L指针指向新结点，尾结点的指针域指向新结点

【情况二】插入到其他位置
image.png

  • 创建新结点，并赋值新结点

  • 找到指定位置的前一个结点target

  • 新结点指针域指向target的next，target的指针域指向新结点

代码实现：

import Foundation

public struct CircularLinkedList<Element>{

    fileprivate class Node<T>: Equatable {

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

            return obj1 == obj2;
        }

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

        init(data : T){
            self.data = data;
            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 lastNode = _head;

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

            return lastNode;
        }
    };

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

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

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

        let node = getNode(index: index);

        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 {

        let index = locate - 1;

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

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

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

        if(index == 0){

            node.next = _head;
            _r?.next = node;
            _head = node;
        }
        else{

            let ptr = getNode(index: index - 1);
            node.next = ptr?.next;
            ptr?.next = node;
        }

        _length += 1;

        return OK;
    }

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

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

        if(_head == nil){
            _head = node;
        }
        else{
            _r?.next = node;
        }

        node.next = _head;
        _length += 1;

        return OK;
    }
}

  • 访问尾结点，_r会通过遍历方式获取

  • 不建议使用_r指针记录尾结点，因为在对尾结点插入或删除时，逻辑会变得复杂

3. 删除

循环链表在删除元素时分为两种情况：

  • 删除首元节点

  • 删除其他节点

【情况一】删除首元节点

  • 判断删除位置是否在首元结点上

  • 找到尾结点，将尾结点的指针域指向首元结点的next

  • 将L指针指向首元结点的next

【情况二】删除其他节点

  • 找到删除位置前一个节点

  • 将前一个节点的指针域指向该节点的next→next

代码实现：

import Foundation

public struct CircularLinkedList<Element>{

    fileprivate class Node<T>: Equatable {

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

            return obj1 == obj2;
        }

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

        init(data : T){
            self.data = data;
            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 lastNode = _head;

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

            return lastNode;
        }
    };

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

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

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

        let node = getNode(index: index);

        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 {

        let index = locate - 1;

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

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

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

        if(index == 0){

            node.next = _head;
            _r?.next = node;
            _head = node;
        }
        else{

            let ptr = getNode(index: index - 1);
            node.next = ptr?.next;
            ptr?.next = node;
        }

        _length += 1;

        return OK;
    }

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

        let index = locate - 1;

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

        var data : Element? = nil;

        if(index == 0){

            data = _head?.data;

            _r?.next = _head?.next;
            _head = _head?.next;
        }
        else{

            let node = getNode(index: index);
            data = node?.data;

            let preNode = getNode(index: index - 1);
            preNode?.next = node?.next;
        }

        _length -= 1;

        return data;
    }

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

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

        if(_head == nil){
            _head = node;
        }
        else{
            _r?.next = node;
        }

        node.next = _head;
        _length += 1;

        return OK;
    }
}

4. 查找元素位置

在循环链表中查找元素，遍历寻找一次即可。找到元素返回位置，否则返回0

import Foundation

public struct CircularLinkedList<Element: Equatable>{

    fileprivate class Node<T>: Equatable {

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

            return obj1 == obj2;
        }

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

        init(data : T){
            self.data = data;
            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 lastNode = _head;

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

            return lastNode;
        }
    };

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

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

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

        let node = getNode(index: index);

        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 {

        let index = locate - 1;

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

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

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

        if(index == 0){

            node.next = _head;
            _r?.next = node;
            _head = node;
        }
        else{

            let ptr = getNode(index: index - 1);
            node.next = ptr?.next;
            ptr?.next = node;
        }

        _length += 1;

        return OK;
    }

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

        let index = locate - 1;

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

        var data : Element? = nil;

        if(index == 0){

            data = _head?.data;

            _r?.next = _head?.next;
            _head = _head?.next;
        }
        else{

            let node = getNode(index: index);
            data = node?.data;

            let preNode = getNode(index: index - 1);
            preNode?.next = node?.next;
        }

        _length -= 1;

        return data;
    }

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

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

        if(_head == nil){
            _head = node;
        }
        else{
            _r?.next = node;
        }

        node.next = _head;
        _length += 1;

        return OK;
    }

    func getLocate(element : Element) -> Int {

        if(length() < 1){
            return 0;
        }

        var locate = 0;
        var node = _head;

        repeat{

            locate += 1;

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

            node = node?.next;

        }while(node != _head)

        return 0;
    }
}

总结

循环链表在创建元素时分为两种情况：

  • 当循环链表为空表时，第一次创建元素

    • 当循环链表为空表时，只存在一个指针。创建第一个元素时，创建新结点并赋值，将指针域指向自身

  • 当循环链表非空表时，创建更多元素

    • 当循环链表非空表时，假设采用后插法，需要先找到链表的结尾位置，然后创建新结点并赋值，将尾结点的指针域指向新结点，将新结点的指针域指向首元结点

循环链表在插入元素时分为两种情况：

  • 插入的位置是首元结点

    • 判断插入位置是否在首元结点上

    • 创建新结点，并赋值新结点

    • 新结点指针域指向之前的首元结点，L指针指向新结点，尾结点的指针域指向新结点

  • 插入到其他位置

    • 创建新结点，并赋值新结点

    • 找到指定位置的前一个结点target

    • 新结点指针域指向target的next，target的指针域指向新结点

循环链表在删除元素时分为两种情况：

  • 删除首元节点

    • 判断删除位置是否在首元结点上

    • 找到尾结点，将尾结点的指针域指向首元结点的next

    • 将L指针指向首元结点的next

  • 删除其他节点

    • 找到删除位置前一个节点

    • 将前一个节点的指针域指向该节点的next→next

循环链表中查找元素：

  • 遍历寻找一次即可。找到元素返回位置，否则返回0