python 实现线性表（line list）
本帖最后由 1968609663 于 2019-1-29 01:13 编辑参照《数据结构与算法》第八集
代码写的比较粗糙，实现：list.insert, list.append, list.pop 三个方法，实现的比较复杂，且存在bug
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):
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))
页:
[1]