python单链表的实现

• 2020 年 1 月 8 日
• 筆記

'''  当加入第一个node节点的时候,会有几个值,(这里的self.tail.next 其实就是node.next)  head = item = tail = Node(object element1 memory)  item = head = tail = Node(object element1  memory)  next = None  tail = item = head = Node(object element1  memory)    当加入第二个元素node节点的时候,next1值会改变,tail会向后漂移,head将会保留  新加入第二个元素后第一个节点变成了  head = item1 = Node(object element1  memory)  item1= head = Node(object element1  memory)  next = Node(object element2  memory)    第二个节点为:  item = tail =  Node(object element2  memory)  next =  Node(object element2  memory)  tail = item =  Node(object element2  memory)    当加入第三个元素的时候,tail.next继续为None item为新元素tail结束元素为新元素,  item = tail =  Node(object element3  memory)  next = None  tail = item =  Node(object element3  memory)  '''    class Node:      def __init__(self,item,next=None):          self.item = item #记录元素          self.next = next #记录下一跳节点        #为了输出 我们可以看到的结果:      def __repr__(self):          return '{} ==> {}'.format(self.item,self.next)    class LinkedList:      def __init__(self):          self.head= None          self.tail = None        def append(self,value):          #添加链表前需要,实例化一个节点,来进行赋值          node = Node(value) #实例化节点          #添加链表,首先判断链表是否为空,          # 空列表时 head= tail = None          #添加元素后head = value = tail = Node(value) = node          if self.head == None:              self.head = node              # self.tail = node          #当链表不为空时向后添加,既是向后添加,添加后的值为          # self.tail.next = Node(last(value)).next = node          #要知道self.tail值的改变是不应为append的改变而改变了,只是再重新赋值之后才会改变的          # self.tail = node #现在的结尾部分被重新赋值          else:              self.tail.next = node #如果添加的是最后一位,next就是默认值既是None              # self.tail = node          # if和slse有公共部分self.tail = node可以直接提出来,          self.tail = node        def iternode(self):          #这里的迭代可以使用我们定义好的方法来做,因为每个node节点都有next可以调用下一个节点,因此我们可以利用这一特性来做迭代          #因为我们不知道需要迭代的个数有多少个,因此只能使用yield配合while循环来做,然后使用节点的下一个来重赋值,知道current为None,while循环结束          current = self.head          while current:              yield current              current = current.next  ll = LinkedList()  ll.append(1)  ll.append(2)  ll.append(3)  for i in ll.iternode():      print(i)

输出结果为:

1 ==> 2 ==> 3 ==> None  2 ==> 3 ==> None  3 ==> None