python双向循环链表实例详解

# Functions  函数声明
class Node():
    """实例化节点类"""
    def __init__(self, item):
        self.item = item
        self.prev = None
        self.next = None

class Linklist():
    """
    存放节点类
    """
    def __init__(self):
        self.head = None

    # 1. 链表是否为空
    def is_empty(self):
        return self.head == None

    # 2. 链表的长度
    def length(self):
        """
        返回链表中所有数据的个数
        实例化游标，遍历链表，使用计数器自增一
        空链表

        """
        # 实例化游标
        cur = self.head
        # 判断是否为空
        if self.is_empty():
            return 0
        else:
            # 不为空
            # 定义计数
            count = 1
            while cur.next != self.head:
                count+=1
                cur = cur.next
            return count
            pass

    # 3. 遍历链表
    def travel(self):
        """
        遍历链表
        实例化游标，遍历链表，每次输出节点的数据
        空链表
        只有头节点
        """
        # 实例化游标
        cur = self.head
        # 判断是否为空
        if self.is_empty():
            return None
        else:
            # 不为空的情况
            while cur.next != self.head:
                print(cur.item, end=' ')
                cur = cur.next
            print(cur.item)
            pass

    # 4. 链表头部添加元素
    def add(self, item):
        """
        头节点添加
        实例化节点，
        """
        # 实例化节点
        node = Node(item)
        # 实例化游标
        cur = self.head
        # 判断是否为空
        if self.is_empty():
            node.next = node
            node.prev = node
            self.head = node
        else:
            # 链表不为空的情况
            # 只有一个节点的情况
            # node.next = self.head
            node.next = cur
            node.prev = cur
            if cur.next == self.head:
                # print(cur.item)
                cur.prev = node
                cur.next = node
                self.head = node
            elif cur.next != self.head:
                pro = self.head
                while cur.next != self.head:
                    cur = cur.next
                pro.prev = node
                cur.next = node
                self.head = node
                pass

    # 5. 链表尾部添加元素
    def append(self, item):
        """
        链表尾部添加数据
        实例化节点，实例化游标，指向尾部节点，修改指向
        链表为空
        """
        # 实例化节点
        node = Node(item)
        # 实例化游标
        cur = self.head
        if self.is_empty():
            self.add(item)
        else:
            # 不为空的情况
            # 指针指向最后一个节点
            self.head.prev = node
            node.next = self.head
            while cur.next != self.head:
                cur = cur.next
            node.prev = cur
            cur.next = node
            pass

    # 6. 链表指定位置添加元素
    def insert(self, index, item):
        """
        指定位置添加数据
        实例化节点， 实例化游标
        移动游标到索引位置，更改指向
        输入索引大小判断
        链表是否为空
        """
        # 实例化节点
        node = Node(item)
        # 实例化游标
        cur = self.head
        if index <= 0:
            self.add(item)
        elif index > (self.length()-1):
            self.append(item)
        else:
            # 中间添加数据
            # 声明计数
            count = 0
            print(index)
            while count < index-1:
                count+=1
                cur = cur.next
            # print(cur.item)
            node.next = cur.next
            node.prev = cur
            cur.next.prev = node
            cur.next = node
            pass

    # 7. 链表删除节点
    def remove(self, item):
        """
        删除数据
        实例化游标，遍历链表，查找有没有改数据
        有，对改数据两侧的节点进行指向修改
        """
        # 实例化游标
        cur = self.head
        # 判断是否为空
        if self.is_empty():
            return None
        else:
            # 不为空的情况下
            # 如果删除的是头节点
            if cur.item == item:
                # 如果只有一个头节点
                if cur.next == self.head:
                   self.head = None
                else:
                    # self.head = cur.next
                    pro = cur.next
                    while cur.next != self.head:
                        cur = cur.next
                    cur.next = pro
                    pro.prev = cur
                    self.head = pro
                    pass
            else:
                while cur.next != self.head:
                    if cur.item == item:
                        # print(cur.item)
                        pro = cur.prev
                        nex = cur.next
                        pro.next = cur.next
                        nex.prev = pro
                        return True
                    else:
                        cur = cur.next
                # 如果是最后一个节点
                if cur.item == item:
                    cur.prev.next = self.head
                    self.head.prev = cur.prev

    # 8. 查找节点是否存在
    def search(self, item):
        """
        查询指定的数据是否存在
        实例化游标
        遍历所有的节点。每个节点中判断数据是否相等，相等，返回True
        """
        # 实例化游标
        cur = self.head
        # 判断是否为空
        if self.is_empty():
            return None
        else:
            # 不为空的情况
            # 遍历所有的节点
            while cur.next != self.head:
                if cur.item == item:
                    return True
                else:
                    cur = cur.next
            if cur.item == item:
                return True
            pass

# 程序的入口
if __name__ == "__main__":
    a = Linklist()
    a .add(400)
    a .add(300)
    a .add(200)
    a .add(100)
    a.append(10)
    a.append(11)
    a.add(1)
    a.insert(30, 12) # 1 100 200 300 400 10 11 12
    a.remove(1)    # 100 200 300 400 10 11 12
    a.remove(12)   # 100 200 300 400 10 11
    a.remove(400)  # # 100 200 300  10 11
    a.remove(4000)
    print(a.search(100))  # True
    print(a.search(11))   # True
    print(a.search(111))  # None
    print(a.is_empty())   # False
    a.travel()            # 100 200 300 10 11
    print(a.length())     # 5
    pass