无序列表抽象数据类型

无序列表是元素的集合，其中每一个元素都有一个相对于其他元素的位置。以下是无序列表支持的操作：

• List() 创建一个空列表。它不需要参数，且会返回一个空列表。
• add(item) 假设元素 item 之前不在列表中，并向其中添加 item。它接受一个元素作为参数，无返回值。
• remove(item) 假设元素 item 已经在列表中，并从其中移除 item。它接受一个元素作为参数，并且修改列表。
• search(item) 在列表中搜索元素 item。它接受一个元素作为参数，并且返回布尔值。
• isEmpty() 检查列表是否为空。它不需要参数，并且返回布尔值。
• length() 返回列表中元素的个数。它不需要参数，并且返回一个整数。
• append(item) 假设元素 item 之前不在列表中，并在列表的最后位置添加 item。它接受一个元素作为参数，无返回值。
• index(item) 假设元素 item 已经在列表中，并返回该元素在列表中的位置。它接受一个元素作为参数，并且返回该元素的下标。
• insert(pos, item) 假设元素 item 之前不在列表中，同时假设 pos 是合理的值，并在位置 pos 处添加元素 item。它接受两个参数，无返回值。
• pop() 假设列表不为空，并移除列表中的最后一个元素。它不需要参数，且会返回一个元素。
• pop(pos) 假设在指定位置 pos 存在元素，并移除该位置上的元素。它接受位置参数，且会返回一个元素。

用 Python 实现无序列表：链表

Node 类

节点（node）是构建链表的基本数据结构。每一个节点对象都必须持有至少两份信息：

1. 节点必须包含列表元素，我们称之为节点的数据变量。
2. 节点必须保存指向下一个节点的引用。

class Node:
    def __init__(self, initdata):
        self.data = initdata
        self.next = None

    def getData(self):
        return self.data

    def getNext(self):
        return self.next

    def setData(self, newdata):
        self.data = newdata

    def setNext(self, newnext):
        self.next = newnext

UnorderedList 类

无序列表（unordered list）是基于节点集合来构建的，每一个节点都通过显式的引用指向下一个节点。只要知道第一个节点的位置（第一个节点包含第一个元素），其后的每一个元素都能通过下一个引用找到。因此，UnorderedList 类必须包含指向第一个节点的引用。

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

注意：列表类本身并不包含任何节点对象，而只有指向整个链表结构中第一个节点的引用。

isEmpty 方法检查列表的头部是否为指向 None 的引用。

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

在 Python 中，None 可以和任何引用进行比较。如果两个引用都指向同一个对象，那么它们就是相等的。

add 方法将元素添加到列表中。由于链表只提供一个入口（头部），因此其他所有节点都只能通过第一个节点以及 next 链接来访问。于是添加新节点最简便的位置就是链表的起点。

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

length、 search 以及 remove 都需要遍历链表。

def length(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
        else:
            previous = current
            current = current.getNext()

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

注意：如果被移除的元素正好是链表的第一个元素，那么 current 会指向链表中的第一个节点，previous 的值则是 None。这时，需要修改链表的头节点，而不是 previous 指向的节点。

---

有序列表抽象数据类型

在有序列表中，元素的相对位置取决于它们的基本特征。它们通常以升序或者降序排列，并且我们假设元素之间能进行有意义的比较。有序列表的众多操作与无序列表的相同。

• OrderedList() 创建一个空有序列表。它不需要参数，且会返回一个空列表。
• add(item) 假设 item 之前不在列表中，并向其中添加 item，同时保持整个列表的顺序。它接受一个元素作为参数，无返回值。
• remove(item) 假设 item 已经在列表中，并从其中移除 item。它接受一个元素作为参数，并且修改列表。
• search(item) 在列表中搜索 item。它接受一个元素作为参数，并且返回布尔值。
• isEmpty() 检查列表是否为空。它不需要参数，并且返回布尔值。
• length() 返回列表中元素的个数。它不需要参数，并且返回一个整数。
• index(item) 假设 item 已经在列表中，并返回该元素在列表中的位置。它接受一个元素作为参数，并且返回该元素的下标。
• pop() 假设列表不为空，并移除列表中的最后一个元素。它不需要参数，且会返回一个元素。
• pop(pos) 假设在指定位置 pos 存在元素，并移除该位置上的元素。它接受位置参数，且会返回一个元素。

用 Python 实现有序列表

OrderedList 类

OrderedList 类的构造方法与 UnorderedList 类的相同。head 引用指向 None，代表这是一个空列表。

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

因为 isEmpty 和 length 仅与列表中的节点数目有关，而与实际的元素值无关，所以这两个方法在有序列表中的实现与在无序列表中一样。同理，由于仍然需要找到目标元素并且通过更改链接来移除节点，因此 remove 方法的实现也一样。而search 和 add，则需要做一些修改。

在无序列表中搜索时，需要逐个遍历节点，直到找到目标节点或者没有节点可以访问。这个方法同样适用于有序列表，但前提是列表包含目标元素。如果目标元素不在列表中，可以利用元素有序排列这一特性尽早终止搜索。

def search(self, item):
    current = self.head
    found = False
    stop = False
    while current != None and not found and not stop:
        if current.getData() == item:
            found = True
        else:
            if current.getData() > item:
                stop = True
            else:
                current = current.getNext()

    return found

对于无序列表， add 方法可以简单地将一个节点放在列表的头部。而对于有序列表，我们需要在已有链表中为新节点找到正确的插入位置。

def add(self, item):
    current = self.head
    previous = None
    stop = False
    while current != None and not stop:
        if current.getData() > item:
            stop = True
        else:
            previous = current
            current = current.getNext()

    temp = Node(item)
    if previous == None:
        temp.setNext(self.head)
        self.head = temp
    else:
        temp.setNext(current)
        previous.setNext(temp)