定义

双向循环链表是在双向链表的基础上发展的，双向链表的最后一个节点指向起始节点，起始节点的上一个节点指向最后一个节点，就得到双向循环链表。

优势

向循环链表比双向链表具有更多的优势，节点的增加和删除有很多优化的地方，从起点开始不必循环完整个链表就可以增加或删除节点。

python实现双向循环链表

头部插入节点

代码实现

def add(self, value):
        """
        头插法
        """
        node = Node(value)
        if self.is_empty():
            node.next = node
            node.prev = node
            self._head = node
        else:
            # 新节点的next指向head
            node.next = self._head
            # 新节点的prev指向head的prev
            node.prev = self._head.prev
            # head节点的prev的next的节点指向node
            self._head.prev.next = node
            # 头部节点的prev指向node
            self._head.prev = node
            # 头部指针指向node
            self._head = node

尾部插入节点

代码实现

def append(self, value):
        """
        尾插法
        """
        if self.is_empty():
            self.add(value)
        else:
            node = Node(value)
            # node的next指向head
            node.next = self._head
            # node的prev指向head的prev
            node.prev = self._head.prev
            # head的prev节点的next指向node
            self._head.prev.next = node
            # head的prev指向node
            self._head.prev = node

指定位置插入节点

代码实现

def insert(self, value, index):
        """
        指定位置插入节点  
        """
        if index <= 0:
            self.add(value)
        elif index > (self.length() - 1):
            self.append(value)
        else:
            node = Node(value)
            cur = self._head
            count = 0
            # 移动到指定位置的前一个节点
            while count < (index - 1):
                count += 1
                cur = cur.next
            # 新节点pre指向上一个节点
            node.prev = cur
            # 新节点的next指向下一个节点
            node.next = cur.next
            # 下一个节点的prev指向node
            cur.next.prev = node
            # 上一个节点next指向新节点
            cur.next = node

删除节点

代码实现

def remove(self, value):
        """
        删除节点
        """
        if self.is_empty():
            return
        else:
            cur = self._head
            # 如果第一个节点就是要删除的节点
            if cur.item == value:
                # 如果只有一个元素
                if self.length() == 1:
                    self._head = None
                else:
                    # 将头结点的下一个节点的prev指向头结点的prev
                    cur.next.prev = cur.prev
                    # 头结点的prev的next指向头结点的下一个节点
                    cur.prev.next = cur.next
                    # 头指针指向头结点的下一个节点
                    self._head = cur.next
            else:
                # 后移一个节点
                cur = cur.next
                # 循环cur 找到删除的元素 找不到break
                while cur is not self._head:
                    if cur.item == value:
                        # cur的next的prev指向cur的prev
                        cur.next.prev = cur.prev
                        # cur的prev的next指向cur的next
                        cur.prev.next = cur.next
                    cur = cur.next

完整代码

class Node(object):
    """
    双向循环链表节点实现
    """
    def __init__(self, item):
        self.prev = None
        self.item = item
        self.next = None


class DoubleCircleLinkList(object):
    """
    双向循环链表实现
    """
    def __init__(self):
        self._head = None

    def is_empty(self):
        """
        判断双向循环链表是否为空
        """
        return self._head is None

    def length(self):
        """
        双向循环链表长度
        """
        if self.is_empty():
            return 0
        else:
            # cur用来移动遍历节点
            cur = self._head
            # count为计数
            count = 1
            while cur.next is not self._head:
                count += 1
                cur = cur.next
            return count

    def traverse(self):
        """
        遍历双向循环链表
        :return:
        """
        if self.is_empty():
            return
        else:
            cur = self._head.next
            # print(cur.next)
            # print(self._head)
            while cur != self._head:
                print(cur.item, end=" ")
                cur = cur.next
            print("")

    def add(self, value):
        """
        头插法
        """
        node = Node(value)
        if self.is_empty():
            node.next = node
            node.prev = node
            self._head = node
        else:
            # 新节点的next指向head
            node.next = self._head
            # 新节点的prev指向head的prev
            node.prev = self._head.prev
            # head节点的prev的next的节点指向node
            self._head.prev.next = node
            # 头部节点的prev指向node
            self._head.prev = node
            # 头部指针指向node
            self._head = node

    def append(self, value):
        """
        尾插法
        """
        if self.is_empty():
            self.add(value)
        else:
            node = Node(value)
            # node的next指向head
            node.next = self._head
            # node的prev指向head的prev
            node.prev = self._head.prev
            # head的prev节点的next指向node
            self._head.prev.next = node
            # head的prev指向node
            self._head.prev = node

    def insert(self, value, index):
        """
        指定位置插入节点  
        """
        if index <= 0:
            self.add(value)
        elif index > (self.length() - 1):
            self.append(value)
        else:
            node = Node(value)
            cur = self._head
            count = 0
            # 移动到指定位置的前一个节点
            while count < (index - 1):
                count += 1
                cur = cur.next
            # 新节点pre指向上一个节点
            node.prev = cur
            # 新节点的next指向下一个节点
            node.next = cur.next
            # 下一个节点的prev指向node
            cur.next.prev = node
            # 上一个节点next指向新节点
            cur.next = node

    def remove(self, value):
        """
        删除节点
        """
        if self.is_empty():
            return
        else:
            cur = self._head
            # 如果第一个节点就是要删除的节点
            if cur.item == value:
                # 如果只有一个元素
                if self.length() == 1:
                    self._head = None
                else:
                    # 将头结点的下一个节点的prev指向头结点的prev
                    cur.next.prev = cur.prev
                    # 头结点的prev的next指向头结点的下一个节点
                    cur.prev.next = cur.next
                    # 头指针指向头结点的下一个节点
                    self._head = cur.next
            else:
                # 后移一个节点
                cur = cur.next
                # 循环cur 找到删除的元素 找不到break
                while cur is not self._head:
                    if cur.item == value:
                        # cur的next的prev指向cur的prev
                        cur.next.prev = cur.prev
                        # cur的prev的next指向cur的next
                        cur.prev.next = cur.next
                    cur = cur.next

    def search(self, item):
        """
        查找元素是否存在
        """
        if self.is_empty():
            return False
        else:
            cur = self._head
            while cur.next is not self._head:
                if cur.item == item:
                    return True
                cur = cur.next
            if cur.item == item:
                return True
            return False


if __name__ == '__main__':
    double_circle_link_list = DoubleCircleLinkList()
    print("当前链表是否为空：", double_circle_link_list.is_empty())
    print("当前链表长度为：", double_circle_link_list.length())

    double_circle_link_list.append(99)
    print("当前链表是否为空：", double_circle_link_list.is_empty())
    print("当前链表长度为：", double_circle_link_list.length())

    double_circle_link_list.append(23)
    double_circle_link_list.append(89)
    double_circle_link_list.append("python")
    double_circle_link_list.append(12.66)
    double_circle_link_list.add(27)
    double_circle_link_list.insert(4, 0)
    double_circle_link_list.remove(27)
    double_circle_link_list.traverse()
    print(double_circle_link_list.search(23))

结果

当前链表是否为空： True
当前链表长度为： 0
当前链表是否为空： False
当前链表长度为： 1
99 23 89 python 12.66 
True