线性表(python实现line list)

实现 list 对象的 list.append, list.insert, list.pop 方法

# coding:utf-8
from typing import Iterable


class ListNode(object):
    def __init__(self, data=None, pre=None, post=None, index=None):
        """
        线性表节点
        :param data:
        :param pre:
        :param post:
        """
        self.data = data  # 存储的数据
        self.pre = pre  # 前一个节点
        self.post = post  # 下一个节点
        self.index = index  # 数据索引


class LineList(object):
    def __init__(self, arr: Iterable = None):
        """python版本链式表"""
        self.node = None
        self._len = 0
        self._pre_node = None
        self._init(arr if arr is not None else [])

    def _init(self, arr: Iterable):
        for b in arr:
            self.append(b)

    def append(self, value):
        """
        list.append(value)
        """
        cur_node = ListNode(data=value, index=self._len)
        if self.node is None:
            self.node = cur_node
        else:
            cur_node.pre = self._pre_node
            self._pre_node.post = cur_node
        self._pre_node = cur_node
        self._len += 1

    def insert(self, index, value):
        """
        list.insert(index, value)
        """
        if index > (self._len + 1):
            raise IndexError("index:{i} max then length:{l}".format(i=index, l=self._len))
        pre_nd = self.node
        while 1:
            cur_node = ListNode(data=value, index=index)
            if pre_nd.index == index:
                cur_node.post = pre_nd
                pre_nd.pre.post = cur_node
                self._add_index(cur_node.post)
                break
            pre_nd = pre_nd.post
        self._len += 1

    def pop(self):
        if self._len == 0:
            raise IndexError("pop empty object")
        cur_nd = self.node
        while 1:
            if cur_nd.index == (self._len - 1):
                del cur_nd.pre.post
                cur_nd.pre.post = None
                break
            cur_nd = cur_nd.post
        self._len -= 1

    @staticmethod
    def _sub_index(root: ListNode):
        while 1:
            root.index -= 1
            root = getattr(root, "post", None)
            if root is None:
                break

    @staticmethod
    def _add_index(root: ListNode):
        while 1:
            root.index += 1
            root = getattr(root, "post", None)
            if root is None:
                break

    def __len__(self):
        return self._len

    @property
    def values(self):
        return self._get_values(show_index=False)

    @property
    def index_values(self):
        return self._get_values(show_index=True)

    def _get_values(self, show_index=False):
        res, nd = [], self.node
        while 1:
            v = getattr(nd, 'data', None)
            if v is not None:
                res.append((nd.index, v) if show_index else v)
            else:
                break
            nd = nd.post
        return res


if __name__ == '__main__':
    ll = LineList(['a', 'b', 'c'])
    ll.append(1)
    ll.insert(1, 10)
    print(ll.values)
    print(len(ll))
    print()

    ll.pop()
    print(ll.values)
    print(len(ll))