python 实现线性表（line list）

1968609663

参照《数据结构与算法》第八集
代码写的比较粗糙，实现：list.insert, list.append, list.pop 三个方法，实现的比较复杂，且存在bug

1. from typing import Iterable
   
2. 
   
3. 
   
4. class ListNode(object):
   
5.     def __init__(self, data=None, pre=None, post=None, index=None):
   
6.         """
   
7.         线性表节点
   
8.         :param data:
   
9.         :param pre:
   
10.         :param post:
    
11.         """
    
12.         self.data = data  # 存储的数据
    
13.         self.pre = pre  # 前一个节点
    
14.         self.post = post  # 下一个节点
    
15.         self.index = index  # 数据索引
    
16. 
    
17. 
    
18. class LineList(object):
    
19.     def __init__(self, arr: Iterable = None):
    
20.         """python版本链式表"""
    
21.         self.node = None
    
22.         self._len = 0
    
23.         self._pre_node = None
    
24.         self._init(arr if arr is not None else [])
    
25. 
    
26.     def _init(self, arr: Iterable):
    
27.         for b in arr:
    
28.             self.append(b)
    
29. 
    
30.     def append(self, value):
    
31.         """
    
32.         list.append(value)
    
33.         """
    
34.         cur_node = ListNode(data=value, index=self._len)
    
35.         if self.node is None:
    
36.             self.node = cur_node
    
37.         else:
    
38.             cur_node.pre = self._pre_node
    
39.             self._pre_node.post = cur_node
    
40.         self._pre_node = cur_node
    
41.         self._len += 1
    
42. 
    
43.     def insert(self, index, value):
    
44.         """
    
45.         list.insert(index, value)
    
46.         """
    
47.         if index > (self._len + 1):
    
48.             raise IndexError("index:{i} max then length:{l}".format(i=index, l=self._len))
    
49.         pre_nd = self.node
    
50.         while 1:
    
51.             cur_node = ListNode(data=value, index=index)
    
52.             if pre_nd.index == index:
    
53.                 cur_node.post = pre_nd
    
54.                 pre_nd.pre.post = cur_node
    
55.                 self._add_index(cur_node.post)
    
56.                 break
    
57.             pre_nd = pre_nd.post
    
58.         self._len += 1
    
59. 
    
60.     def pop(self):
    
61.         if self._len == 0:
    
62.             raise IndexError("pop empty object")
    
63.         cur_nd = self.node
    
64.         while 1:
    
65.             if cur_nd.index == (self._len - 1):
    
66.                 cur_nd.pre.post = None
    
67.                 break
    
68.             cur_nd = cur_nd.post
    
69.         self._len -= 1
    
70. 
    
71. 
    
72.     @staticmethod
    
73.     def _sub_index(root: ListNode):
    
74.         while 1:
    
75.             root.index -= 1
    
76.             root = getattr(root, "post", None)
    
77.             if root is None:
    
78.                 break
    
79. 
    
80.     @staticmethod
    
81.     def _add_index(root: ListNode):
    
82.         while 1:
    
83.             root.index += 1
    
84.             root = getattr(root, "post", None)
    
85.             if root is None:
    
86.                 break
    
87. 
    
88.     def __len__(self):
    
89.         return self._len
    
90. 
    
91.     @property
    
92.     def values(self):
    
93.         return self._get_values(show_index=False)
    
94. 
    
95.     @property
    
96.     def index_values(self):
    
97.         return self._get_values(show_index=True)
    
98. 
    
99.     def _get_values(self, show_index=False):
    
100.         res, nd = [], self.node
     
101.         while 1:
     
102.             v = getattr(nd, 'data', None)
     
103.             if v is not None:
     
104.                 res.append((nd.index, v) if show_index else v)
     
105.             else:
     
106.                 break
     
107.             nd = nd.post
     
108.         return res
     
109. 
     
110. 
     
111. if __name__ == '__main__':
     
112.     ll = LineList(['a', 'b', 'c'])
     
113.     ll.append(1)
     
114.     ll.insert(1, 10)
     
115.     print(ll.values)
     
116.     print(len(ll))
     
117.     print()
     
118. 
     
119.     ll.pop()
     
120.     print(ll.values)
     
121.     print(len(ll))
     

复制代码