环形链表

一、说明

二、代码

三、应用

class Node(object):
    def __init__(self, item, next):
        self.item = item
        self.next = next


class LoopLink(object):
    def __init__(self, init_list: list):
        """
        初始化
        """
        self._link = None
        self._reverse_link = None
        self._init_link(init_list)

    def _init_link(self, init_list: list):
        init_list.reverse()
        first = None
        for item in init_list:
            self._link = Node(item, self._link)
            if first is None:
                first = self._link
        first.next = self._link

    # def _init_link_2(self):
    #     try:
    #         self._link = Node(next(self._init_list), self._link)
    #         self._init_link()
    #     except:
    #         return

    @property
    def list(self):
        """
        将链表转换成list
        :return:
        """
        res = []
        link = self._link
        item = link.item
        while link:
            res.append(link.item)
            link = link.next
            if link.item == item:
                break
        return res

    def clear(self):
        """
        清空链表
        :return:
        """
        self._link = None

    def pop(self):
        """
        删除最后一个元素
        :return:
        """
        # 获取倒数第二个元素
        node = self.get_node(self.length - 1 - 1)
        node.next = self._link

    def shift(self, length=None):
        """
        删除第一个元素
        :return:
        """
        link = self._link
        if length is None:
            length = self.length
        index = 0
        second_node = link.next
        while link:
            if index >= length - 1:
                link.next = second_node
                self._link = second_node
                break
            link = link.next
            index += 1

    def delete(self, item):
        """
        删除某个元素，删除头元素调用shift()方法
        :param item:
        :return:
        """
        length = self.length
        link = self._link
        index = 0
        prev = None
        while link:
            if link.item == item:
                if index == 0:
                    self.shift(length)
                elif index == length - 1:
                    prev.next = self._link
                else:
                    prev.next = link.next
                break
            if index >= length - 1:
                break
            prev = link
            link = link.next
            index += 1

    def get_index(self, item):
        """
        根据元素获取位置
        :param item:
        :return:
        """
        index = 0
        link = self._link
        while link:
            if link.item == item:
                break
            link = link.next
            index += 1
        return index

    def get_node(self, index):
        """
        根据位置获取元素
        :param index:
        :return:
        """
        _index = 0
        link = self._link
        while link:
            if _index == index:
                break
            link = link.next
            _index += 1
        return link

    def append(self, item):
        """
        在最后的位置添加
        :param item:
        :return:
        """
        first = self._link
        last = self.get_node(self.length-1)
        last.next = Node(item, first)

    def unshift(self, item):
        """
        在第一个位置添加
        :param item:
        :return:
        """
        last = self.get_node(self.length-1)
        self._link = Node(item, self._link)
        last.next = self._link

    def insert(self, item, index):
        """
        向链表的index位置插入元素item
        index从0计数
        :param item:
        :param index:
        :return:
        """
        length = self.length
        if index >= length:
            index = index % length
        if index == 0:
            self.unshift(item)
        elif index == length - 1:
            self.append(item)
        else:
            _index = 0
            link = self._link
            prev = None
            while link:
                if _index == index:
                    prev.next = Node(item, link)
                    break
                prev = link
                link = link.next
                _index += 1

    @property
    def length(self):
        """
        获取链表的长度
        :return:
        """
        return len(self.list)

    def empty(self):
        """
        链表是否为空
        :return:
        """
        if self._link is None:
            return True
        else:
            return False

    def in_link(self, item):
        """
        判断元素是否在链表中
        :param item:
        :return:
        """
        index = 0
        length = self.length
        link = self._link
        while link:
            if item == link.item:
                return True
            if index >= length - 1:
                return False
            link = link.next
            index += 1
        return False


if __name__ == '__main__':
    link = LoopLink(['zhangbo', 'liudong', 'zhuxiang', 'suirun'])
    print(link.list)
    # link.insert('wuxiaokang', 3)
    # print(link.list)
    # print(link.get_index('wuxiaokang'))
    # print(link.get_node(3).item)
    # link.append('hufang')
    # print(link.list)
    # link.unshift('shenming')
    # print(link.list)
    # link.insert('xiaoqiao', 7)
    # print(link.list)
    link.delete('liudong')
    print(link.list)
    # link.delete('suirun')
    # print(link.list)
    # link.reverse()
    # print(link.list)