无序链表

链表是项的集合，其中每个项保持相对于其他项的相对位置。
例如：
整数 54,26,93,17,77 和 31 的集合可以表示考试分数的简单无序链表。请注意，我们将它们用逗号分隔，这是链表结构的常用方式。当然，Python 会显示这个链表为 [54,26,93,17,77,31]。

无序链表的抽象数据类型

下面给出了一些可能的无序链表操作：

操作	描述	返回值
List()	创建一个新的空链表，不需要参数	返回一个空链表
add(item)	向链表中添加一个新项，需要 item 作为参数	不返回任何内容
remove(item)	从链表中删除该项，需要 item 作为参数并修改链表
search(item)	搜索链表中的项目，需要 item 作为参数	返回一个布尔值
isEmpty()	检查链表是否为空，不需要参数	返回布尔值
size（）	返回链表中的项数，不需要参数	返回一个整数
append(item)	将一个新项添加到链表的末尾，使其成为集合中的最后一项，需要 item 作为参数	不返回任何内容
index(item)	返回项在链表中的位置，需要 item 作为参数	返回索引
insert(pos，item)	在位置 pos 处向链表中添加一个新项，需要 item 作为参数	不返回任何内容
pop()	删除链表中的最后一个项	返回删除项
pop(pos)	删除位置 pos 处的项，需要 pos 作为参数	返回删除项

python实现无序链表

创建节点

Unordered List 类

序列表将从一组节点构建，每个节点通过显式引用链接到下一个节点。只要我们知道在哪里找到第一个节点（包含第一个项），之后的每个项可以通过连续跟随下一个链接找到。

创建一个链表

class UnorderedList:
    def __init__(self):
        self.head = None

#创建一个空链表
mylist = UnorderedList()

创建一个空链表

判断是否为空

判断链表是否为空：

def isEmpty(self):
    return  self.head == None

isEmpty 方法只是检查链表头是否是 None 的引用。 布尔表达式 self.head == None 的结果只有在链表中没有节点时才为真。

添加项

由于该链表是无序的，所以新项相对于已经在列表中的其他项的特定位置并不重要。 新项可以在任何位置。考虑到这一点，将新项放在最简单的位置是有意义的。链表结构只为我们提供了一个入口点，即链表的头部。所有其他节点只能通过访问第一个节点，然后跟随下一个链接到达。这意味着添加新节点的最简单的地方就在链表的头部。 换句话说，我们将新项作为链表的第一项，现有项将需要链接到这个新项后。

def add (self,item):
    temp = Node(item)
    temp.setNext(self.head)
    self.head = temp

无序链表添加项

链表中的元素项数

要实现 size 方法，我们需要遍历链表并对节点数计数:

def size(self):
    current = self.head
    count = 0
    while current != None:
        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

例如查找包含17的结点：

节点查找

删除节点

remove 方法需要两个逻辑步骤：

• 首先，我们需要遍历列表寻找我们要删除的项。
• 一旦我们找到该项（我们假设它存在），删除它。
  为了简单起见，我们假设被删除的节点一定存在，如果要删除的项目恰好是链表中的第一个项，则 current 将引用链接列表中的第一个节点。这也意味着 previous 是 None。

def remove(self,item):
    current = self.head
    previous = None
    found = False
    while not found:
        if current.getData == item:
            found = True
        else:
            previous = current
            current = current.getNext()

    if previous == None:
        self.head = current.getNext()
    else:
        previous.setNext(current.getNext())

删除一个中间节点：

删除中间节点

删除一个头节点：

删除头节点