链表python

无序链表、有序链表

有序列表排序通常是升序或降序，并且我们假设列表项具有已经定义的有意义的比较运算。

许多有序列表操作与无序列表的操作相同。

必须明确链表的第一项位置，一旦知道第一项。

链表实现的基本构造快是节点。

每个节点对象必须至少保存两个信息。

首先，节点必须包含列表项本身。我们将这个称为节点的数据字段。

此外，每个节点必须保存对下一个节点的引用。

Node 类还包括访问，修改数据和访问下一个引用的常用方法。

 1 class Node():
 2     def __init__(self,initialdata):
 3         self.data = initialdata
 4         self.next = None
 5     def getdata(self):
 6         return self.data
 7     def getnext(self):
 8         return self.next
 9     def setdata(self,newdata):
10         self.data = newdata
11     def setnext(self,newnext):
12         self.next = newnext
13 temp = Node(93)
14 print(temp.getdata())

已经有了节点了，开始构造链表
无序列表将从一组节点构建，每个节点通过显式引用链接到下一个节点。
只要我们知道在哪里找到第一个节点（包含第一个项），之后的每个项可以通过连续跟随下一个链接找到。
考虑到这一点， UnorderedList 类必须保持对第一个节点的引用。
！注意，每个链表对象将维护对链表头部的单个引用！

  1 #定义节点
  2 class Node():
  3     def __init__(self,initialdata):
  4         self.data = initialdata
  5         self.next = None
  6         
  7 #构造链表
  8 class List():
  9     //初始空链表
 10     //链表类本身不包含任何节点对象,只是对节点头的引用
 11     def __inti__(self):
 12         self.head = None
 13     #添加
 14     #在链表头添加
 15     def add(self,item):
 16         newnode = Node(item)
 17         newnode.next = self.head
 18         self.head = newnode #新节点头
 19     #有序链表添加
 20     #先找合适的位置，再放进去
 21     def orderlist_add(self,item):
 22         current_node = self.head
 23         previous = None
 24         found = False
 25         while current_node != None and not found:
 26             if current_node >= item:
 27                 founnd = True
 28             else:
 29                 previous = current_node
 30                 current_node = current_node.next
 31         #要么没找到current_node=None，放到链表末尾；要么找到了found=True，插入
 32         newnode = Node(item)
 33         if current_node == None:
 34             current_node = newnode
 35         else:
 36             previous.next = newnode
 37             newnode.next = current_node
 38 
 39     #链表长度
 40     def length(self):
 41         node = self.head
 42         count = 0
 43         while node != None:
 44             count += 1
 45             node = node.next
 46         return count
 47     #链表搜索
 48     def search(self,item):
 49         current_node = self.head
 50         while current_node != None:
 51             if current_node.data == item;
 52                 return True
 53             else:
 54                 current_node = current_node.next
 55         return False
 56     #删除
 57     #先找再删,记录前一个节点信息
 58     def remove(self,item):
 59         current_node = self.head
 60         found = False
 61         previous = None
 62         #先找，只要节点为None或找到了就停止循环
 63         while current_node != None and not found:
 64             if current_node.data == item:
 65                 found = True
 66             else:
 67                 previous = current_node
 68                 current_node = current_node.next
 69         #这个时候只有两种情况，要么找到了found=True;要么没找到，此时current_node=None
 70         if current_node == None:
 71             print("We coundn't find")
 72         else:
 73             previous.next = current_node.next