python双向循环链表实例详解

使用python实现双向循环链表，供大家参考，具体内容如下

双向循环链表：将所有的数据存放到节点中，每一个节点相连接，首尾链接，
每一个节点中有一个数据存储区，和两个链接区，一个链接前一个节点，一个链接下一个节点

双向链表操作

1、链表是否为空
2、链表的长度
3、遍历链表
4、链表头部添加元素
5、链表尾部添加元素
6、链表指定位置添加元素
7、链表删除节点
8、查找节点是否存在

代码实现
`# 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

更多相关文章

随机推荐