python-单向链表

一个简单的单向链表类

#!/usr/bin/env python
# -*- coding: utf-8 -*-


class BaseNode:
    pass


class Node(BaseNode):
    def __init__(self, value, next=None):
        self._value = value
        self._next = next

    def __repr__(self):
        return str(self._value)

    @property
    def value(self):
        return self._value

    @value.setter
    def value(self, value):
        self._value = value

    @property
    def next(self):
        return self._next

    @next.setter
    def next(self, node):
        self._next = node


class FirstNode(BaseNode):
    def __init__(self, next=None):
        self._next = next

    @property
    def next(self):
        return self._next

    @next.setter
    def next(self, node):
        self._next = node


class LinkedList:
    def __init__(self, i_list=[]):
        if type(i_list) is not list:
            raise TypeError
        self._first_node = FirstNode()
        now_node = self._first_node
        for n in i_list:
            now_node.next = Node(n)
            now_node = now_node.next
        self._end_node = now_node
        self._len = len(i_list)

    def __len__(self):
        return self._len

    def __iter__(self):
        now_node = self._first_node.next
        while now_node is not None:
            yield now_node
            now_node = now_node.next
        raise StopIteration

    def __getitem__(self, item):
        n = self._first_node.next
        for i in range(item):
            n = n.next
            if n is None:
                raise IndexError
        return n

    # 链表是否为空
    def is_empty(self):
        return self._len == 0

    # 获取最后一个结点
    def end_node(self):
        n = self._first_node
        while n.next is not None:
            n = n.next
        return n

    # 在末尾添加
    def app_end(self, i):
        return self.insert(self._len, i)

    # 在索引位置插入结点
    def insert(self, item, i):
        if type(i) is not Node:
            i = Node(i)
        n = self[item - 1]
        i.next = n.next
        n.next = i
        self._len += 1
        return True

    # 删除索引位置的结点
    def delete(self, item):
        n = self[item - 1]
        if n.next is None:
            raise IndexError
        n.next = n.next.next
        self._len -= 1
        return True

    # 更新索引位置的值
    def update(self, item, i):
        if i is Node:
            self.delete(item)
            self.insert(item)
        else:
            self[item].value = i

    # 通过值查找索引
    def find(self, i):
        for item, node in enumerate(self):
            if node.value == i:
                return item
        return False

    # 通过Node查找索引
    def find_node(self, n):
        for item, node in enumerate(self):
            if node == n:
                return item
        return False

    # 清空
    def clear(self):
        self._first_node.next = None
        self._len = 0

    # 添加list到末尾
    def add_list(self, i_list):
        if type(i_list) is not list:
            raise TypeError
        now_node = self.end_node()
        for n in i_list:
            now_node.next = Node(n)
            now_node = now_node.next
        self._end_node = now_node
        self._len += len(i_list)

    # 从list建立
    def from_list(self, i_list):
        if type(i_list) is not list:
            raise TypeError
        now_node = self._first_node
        for n in i_list:
            now_node.next = Node(n)
            now_node = now_node.next
        self._end_node = now_node
        self._len = len(i_list)

    # 转换成list
    def to_list(self):
        l = list()
        for n in self:
            l.append(n)
        return l

    # 翻转链表
    def flip(self):
        if self._len <= 2:
            return True
        last = self._first_node.next
        now = last.next
        last.next = None
        while now is not None:
            next = now.next
            now.next = last
            last = now
            now = next
        self._first_node.next = last
        return True

 

相关日志

  1. 2018.06.07

    python爬虫:提取页面时间

    def date_check(date_st…

  2. 2018.08.21

    [微信公众号文章抓取.二]构建Anyproxy来获取数据

    上回书说到,啊啊呸。上一篇文章已经确定了抓取…

  3. 2018.03.22

    关于python中yield和协程的一点理解

    yield一般应用于生成循环中的那个变量,一…

  4. 2018.08.08

    [微信公众号文章抓取.一]探索各种办法的可行性

    最近在公司做了一个这方面的项目,总结一下。顺…

  5. 2018.09.14

    再用dict.keys()就是狗

    最近刷题用python比较多,毕竟list比…

  6. 2018.03.20

    使用正则表达式解析url

    #!/usr/bin/env python …

评论

还没有评论。

在此评论中不能使用 HTML 标签。