之前的学习中都是用C语言编写的链表实现，今天小编将带大家一起来学习用python编写单向循环链表。

链表

链表（Linked list）是一种常见的基础数据结构，是⼀种线性表，但是不像顺序表一样连续存储数据，是在每个节点（数据存储单元）存放下一个节点的位置信息（即地址）。

Python

单向循环链表

单链表的一个变形是单向循环链表，链表中最后一个节点的next域不再为None，而是指向链表的头节点。

语法实现：

class Node(object):    """结点类"""    def __init__(self, item):        self.item = item        self.next = Noneclass CyclesSingleLinkList():    """单向循环链表"""    def __init__(self, node=None):        self.__head = node    def is_empty(self):        """链表是否为空        :return 如果链表为空 返回真        """        return self.__head is None    def length(self):        """链表长度"""        # 如果是空链表        if self.is_empty():            return 0        cur = self.__head        count = 1        while cur.next != self.__head:            count += 1            cur = cur.next        return count    def travel(self):        """遍历整个链表"""        if self.is_empty():            print("")            return        cur = self.__head        while cur.next != self.__head:            print(cur.item, end=" ")            cur = cur.next        # 从循环退出，cur指向的是尾结点        print(cur.item)    def add(self, item):        """链表头部添加元素        :param item: 要保存的具体数据        """        node = Node(<b style="color:transparent">来&源gao@dai!ma.com搞$代^码%网</b>item)        if self.is_empty():            self.__head = node            node.next = node        # 寻找尾结点        cur = self.__head        while cur.next != self.__head:            cur = cur.next        # 从循环中退出，cur指向尾结点        node.next = self.__head        self.__head = node        cur.next = self.__head    def append(self, item):        """链表尾部添加元素"""        node = Node(item)        #如果列表为空，直接添加结点        if self.is_empty():            self.__head = node            node.next = node        else:            cur = self.__head            while cur.next != self.__head:                cur = cur.next            #退出循环的时候，cur指向尾结点            cur.next = node            node.next = self.__head    def insert(self, pos, item):        """指定位置添加元素"""        # 在头部添加元素        if pos <= 0:            self.add(item)        # 在尾部添加元素        elif pos >= self.length():            self.append(item)        else:            cur = self.__head            count = 0            while count < (pos - 1):                count += 1                cur = cur.next            # 退出循环的时候，cur指向pos前一个位置            # node插入到pos位置前            node = Node(item)            node.next = cur.next            cur.next = node    def remove(self,item):        """删除结点"""        if self.is_empty():            return        # 当前游标        cur = self.__head        # 当前游标的上一个游标        pre = None        while cur.next != self.__head:            # 找到了要删除的元素            if cur.item == item:                # 在头部找到了元素                if cur == self.__head:                    # 先找到尾结点                    rear = self.__head                    while rear.next != self.__head:                        rear = rear.next                    # 退出循环后，rear指向尾结点                    self.__head = cur.next                    rear.next = self.__head                else:                    # 在中间位置找到了元素                    pre.next = cur.next                return            # 不是要找的元素，移动游标            pre = cur            cur = cur.next        # 退出循环后，cur指向尾结点        if cur.item == item:            # 链表只有一个节点            if cur == self.__head:                self.__head = None            else:                pre.next = self.__head    def search(self,item):        """查找结点是否存在"""        if self.is_empty():            return False        cur = self.__head        while cur.next != self.__head:            if cur.item == item:                return True            cur = cur.next        # 退出循环后，cur指向为尾结点        if cur.item == item:            return True        return Falseif __name__ == '__main__':    ll = CyclesSingleLinkList()    print(ll.length())    ll.travel()    ll.append(1)    print(ll.length()) #1    ll.travel() #1    ll.add(2)    print(ll.length()) #2    ll.travel()#2 1    ll.insert(1,3)    ll.travel() #2 3 1    ll.remove(1)    ll.travel() #2 3

喜欢 (0)赏

[搞代码]

分享 (0)