在介绍链表之前，先了解一下什么是列表吧。
基本数据结构讨论使用Python列表实现表示的抽象数据类型。 列表是一种强大而简单的收集机制，为程序员提供各种操作。 但是，并不是所有的编程语言都包含列表集合。 在这些情况下，列表的概念必须由程序员实现。
列表是项目的集合，每个项目保持其相对于其他项目的位置。 更具体地说，这种类型的列表称为无序列表。 列表可以认为有第一项、第二项、第三项等。 也可以浏览列表的开头(第一个项目)或列表的末尾(最后一个项目)。 为了简单起见，我们假设列表中不能包含重复项。
例如，整数54、26、93、17、77和31的集合可以表示测试分数的简单无序列表。 这些请用逗号隔开。 这是列表结构的一般方法。 当然，Python将该列表显示为[54、26、93、17、77、31]。
1无序列表抽象数据类型
如上所述，无序列表的结构是项目的集合，每个项目保持其相对于其他项目的位置。 以下是可能的无序列表操作：
List ) )创建新的空列表。 不需要参数。 返回空列表。
add(item )向列表中添加新项目。 需要item作为参数，不返回任何内容。 假设此item不在列表中。
remove(item )从列表中删除项目。 需要使用item作为参数来修改列表。 假设项目存在于列表中。
搜索(item )搜索列表中的项目。 需要item作为参数，并返回布尔值。
isEmpty ) )检查列表是否为空。 不需要参数。 返回布尔值。
size ) )返回列表中的项数。 不需要参数。 返回整数。
append(item )将新项目添加到列表的末尾，使其成为集合中的最后一个项目。 需要项目
作为参数，不返回任何内容。 假设这个项目不在列表中。
index(item )返回项目在列表中的位置。 需要item作为参数，并返回索引。 假设这个项目在列表中。
insert(pos，item )在位置pos向列表中添加新条目。 需要item作为参数，不返回任何内容。 假设项目不在列表中，且现有项目足够有pos位置。
pop ) )将被删除并返回列表中的最后一项。 假设列表中至少有一个项目。
删除并恢复pop(pos )位置pos项目。 需要pos作为参数，并返回条目。 假设这个项目在列表中。
2 python实现无序列表
为了实现无序列表，构建一个众所周知的链表。 外部参照通常称为链表的开头。
2.1节点类
节点(Node )是链表实现的基本结构，由列表项目(item、数据字段)和对以下节点的引用组成： Node类包含访问、修改数据和访问以下引用等常用方法。 类的代码如下所示。
类节点：
def __init__(self，initdata ) :
self.data=initdata
self.next=None
获取数据(self ) :
return self.data
获取下一步(self ) :
return self.next
defsetdata(self，newdata ) :
self.data=newdata
defsetnext(self，newnext ) :
self.next=newnext
创建节点对象
temp=node(93 )
Python引用值None在Node类和链表本身中起着重要的作用。 引用None意味着没有以下节点： 请注意，对于构造函数，初始创建的节点next设置为None。 由于这有时称为接地节点，因此使用标准接地符号表示对None的引用，如下图所示。
2.2未排序列表类
如上所述，无序列表由一组节点构建，每个节点通过显式引用链接到下一个节点。 如果知道在哪里找到了第一个节点(包括第一个项目)，则可以通过按顺序浏览下一个链接来找到每个后续项目。 因此，UnorderedList类必须保留对第一个节点的引用，如下图所示。 实现代码应如下所示：
class UnorderedList:
def __init__(self ) :
self.head=None
efisempty(self ) :
return self.head==None
defadd(self，item ) :
temp=node (项目)
#更改新节点的下一个引用，以引用旧链表中的第一个节点
temp.setnext(self.head ) )。
#赋值语句设置列表的开头
手机
f.head = temp#访问和赋值的顺序不能颠倒，因为head是链表节点唯一的外部引用，颠倒将导致所有原始节点丢失并且不能再被访问
def size(self):
current = self.head
count = 0
while current != None:
count = count + 1
current = current.getNext()
return count
def search(self,item):
current = self.head
found = False
while current != None and not found:
if current.getData() == item:
found = True
else:
current = current.getNext()
return found
def remove(self,item):
current = self.head
previous = None
found = False
while not found:
if current.getData() == item:
found = True
#previous 必须先将一个节点移动到 current 的位置。此时，才可以移动current
else:
previous = current
current = current.getNext()
#如果要删除的项目恰好是链表中的第一个项，链表的 head 需要改变
if previous == None:
self.head = current.getNext()
else:
previous.setNext(current.getNext())
2.2.1 add function
链表结构只为我们提供了一个入口点，即链表的头部。所有其他节点只能通过访问第一个节点，然后跟随下一个链接到达。这意味着添加新节点的最简单的地方就在链表的头部。 换句话说，我们将新项作为链表的第一项，现有项将需要链接到这个新项后。
2.2.2 链表遍历技术——size，search，remove方法
size方法实现思路如下图：
remove方法实现思路如下图：
remove 方法需要两个逻辑步骤。
第一步搜索，第二部删除。
但是current实际指向的是目标节点的引用，直接删除会删除前一个节点，因此引入previous这个外部引用。
参考资料：《problem-solving-with-algorithms-and-data-structure-using-python》
http://www.pythonworks.org/pythonds