python 创建链表

  1 # -*- coding=utf-8 -*-
  2 # software: 算法学习
  3 # datetime:2020/4/8 11:13 上午
  4 
  5 class Node(object):
  6 
  7     def __init__(self, data=None, next=None):
  8         self._value = data
  9         self._next = next
 10 
 11     def get_value(self):
 12         return self._value
 13 
 14     def get_next(self):
 15         return self._next
 16 
 17     def set_value(self, new_data):
 18         self._value = new_data
 19 
 20     def set_next(self, new_next):
 21         self._next = new_next
 22 
 23 
 24 class LinkList(object):
 25 
 26     def __init__(self):
 27         self._head = Node()
 28         self._tail = self._head
 29         self._length = 0
 30 
 31     def head(self):
 32         """
 33         链表的第一个元素(除去头节点)
 34         :return:
 35         """
 36         if self._head.get_next():
 37             return self._head.get_next()
 38         else:
 39             return Node()
 40 
 41     def tail(self):
 42         """
 43         链表的最后一个元素
 44         :return:
 45         """
 46         return self._tail
 47 
 48     def is_empty(self):
 49         """
 50         判断链表是否为空
 51         :return:
 52         """
 53         return self._length == 0
 54 
 55     def size(self):
 56         """
 57         链表的大小
 58         :return:
 59         """
 60         return self._length
 61 
 62     def add(self, value):
 63         """
 64         从头部插入节点
 65         :param value:
 66         :return:
 67         """
 68         new_node = Node(value)
 69         new_node.set_next(self._head.get_next())
 70         self._head.set_next(new_node)
 71         self._length += 1
 72 
 73     def append(self, value):
 74         """
 75         从尾部追加节点
 76         :param value:
 77         :return:
 78         """
 79         new_node = Node(value)
 80         if self.is_empty():
 81             self._head.set_next(new_node)
 82         else:
 83             current = self._head
 84             while current.get_next():
 85                 current = current.get_next()
 86             current.set_next(new_node)
 87         self._tail = new_node
 88         self._length += 1
 89 
 90     def search(self, value):
 91         """
 92         查找数据，返回-1或者节点索引
 93         :param value:
 94         :return:
 95         """
 96         current = self._head.get_next()
 97         count = 0
 98         while current.get_next():
 99             if current.get_value() == value:
100                 return count
101             current = current.get_next()
102             count += 1
103         return -1
104 
105     def remove(self, value):
106         """
107         删除 返回该数据或者-1
108         :param value:
109         :return:
110         """
111         current = self._head
112         pre = None
113         while current.get_next():
114             if current.get_value() == value:
115                 if not pre:
116                     self._head = current.get_next()
117                 else:
118                     pre.set_next(current.get_next())
119                 self._length -= 1
120                 return current.get_value()
121             pre = current
122             current = current.get_next()
123         else:
124             return -1
125 
126 
127     def insert(self, index, value):
128         """
129         插入数据节点
130         :param index:
131         :param value:
132         :return:
133         """
134         if index <= 1:
135             self.add(value)
136         elif index > self.size():
137             self.append(value)
138         else:
139             new_node = Node(value)
140             count = 0
141             current = self._head
142             pre = None
143             while count < index:
144                 count += 1
145                 pre = current
146                 current = current.get_next()
147             pre.set_next(new_node)
148             new_node.set_next(current)
149             self._length += 1
150 
151 
152 if __name__ == ‘__main__‘:
153     arr = [1, 4, 2, 6, 8, 4, 9]
154     print("数组的长度: ", len(arr))
155     link_list = LinkList()
156     print("空链表size: ", link_list.size())
157     print("空链表是否为空：", link_list.is_empty())
158     print("空链表的第一个数据：", link_list.head().get_value())
159     print("空链表的最后一个数据：", link_list.tail().get_value())
160     for i in arr:
161         link_list.append(i)
162 
163     # 添加
164     link_list.append(10)
165     link_list.add(10)
166     link_list.insert(1, 11)
167     link_list.insert(3, 12)
168     link_list.insert(7, 13)
169     print("删除的元素：", link_list.remove(1))
170     link_list.append(1)
171     link_list.add(10)
172 
173     current = link_list.head()
174     l = ""
175     while current.get_next():
176         l += str(current.get_value()) + " "
177         current = current.get_next()
178     l += str(current.get_value())
179     print("遍历链表的值", l)
180     print("链表的尺寸：", link_list.size())
181     print("链表的查找：", link_list.search(8))
182     print("链表的第一个数据：", link_list.head().get_value())
183     print("链表的最后一个数据：", link_list.tail().get_value())