跳转至

3.23. 实现有序列表

3.23. Implementing an Ordered List

为了实现有序列表，我们必须记住项的相对位置是基于某些基本特征。有序的整数列表（如 17, 26, 31, 54, 77 和 93）可以通过链接结构来表示，如 图 15 所示。同样，节点和链接结构非常适合表示项的相对位置。

图像标题
图 15：有序链表

要实现 OrderedList 类，我们将使用与之前无序列表相同的技术。再次，空列表将由指向 None 的 head 引用表示（参见 Listing 8）。

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

考虑到有序列表的操作，我们应该注意到 is_empty 和 size 方法可以与无序列表一样实现，因为它们只处理列表中节点的数量，而不关心实际项的值。同样，remove 方法也能正常工作，因为我们仍然需要找到项，然后绕过节点进行删除。剩下的两个方法，search 和 add, 将需要一些修改。

无序链表的搜索要求我们逐个遍历节点，直到找到所寻找的项或用尽节点（None）。实际上，对于有序列表，同样的方法也适用，如果项在列表中，没有必要做任何更改。然而，如果项不在列表中，我们可以利用排序来尽可能早地停止搜索。

例如，图 16 显示了有序链表的搜索过程，正在寻找值 45。当我们从列表的头部开始遍历时，首先与 17 进行比较。由于 17 不是我们要找的项，我们移动到下一个节点，这里是 26。同样，这也不是我们想要的，所以我们继续移动到 31，然后到 54。此时，情况有所不同。由于 54 不是我们要找的项，我们的旧策略是继续向前移动。然而，由于这是一个有序列表，情况并非如此。一旦节点中的值大于我们要搜索的项，搜索可以停止并返回 False。因为项不可能在链表的后面存在。

图像标题
图 16：搜索有序链表

Listing 9 显示了完整的 search 方法。通过添加另一个检查（第 6 行），很容易将上述新条件纳入其中。我们可以继续向前查看列表（第 3 行）。如果发现任何节点包含的数据大于我们要寻找的项，我们将立即返回 False。其余的行与无序列表的搜索相同。

Listing 9
def search(self, item):
    current = self.head
    while current is not None:
        if current.data == item:
            return True
        if current.data > item:
            return False
        current = current.next

    return False

最重要的方法修改将在 add 中进行。回想一下，对于无序列表，add 方法可以简单地将新节点放在列表的头部。这是最容易访问的点。不幸的是，这在有序列表中不再有效。现在有必要找到新项在现有有序列表中的确切位置。

假设我们有一个有序列表，包含 17, 26, 54, 77 和 93，并且我们想要添加值 31。add 方法必须决定新项应该放在 26 和 54 之间。图 17 显示了我们需要的设置。如前所述，我们需要遍历链表，寻找新节点应该插入的位置。当我们用尽节点（current 变为 None）或当前节点的值大于我们想要添加的项时，我们知道已经找到了位置。在我们的例子中，看到值 54 就会使我们停止。

图像标题
图 17：向有序链表中添加项

正如我们在无序列表中看到的，我们需要一个额外的引用，这里称为 previous, 因为 current 不会提供访问必须修改的节点的能力。Listing 10 显示了完整的 add 方法。第 3 行和第 4 行设置了两个外部引用，第 8 行和第 9 行使 previous 每次迭代时都跟在 current 后面。一旦发现当前节点的值大于要添加的项（第 1 行的条件），迭代将继续。无论如何，当迭代结束时，我们已经找到了新节点的位置。

方法的其余部分完成了 图 17 中显示的两步过程。一旦为该项创建了新节点，唯一剩下的问题是新节点是会被添加到链表的开头，还是添加到中间某个位置。同样，previous is None（第 11 行）可以用来提供答案。

Listing 10
def add(self, item):
    """添加一个新节点"""
    current = self.head
    previous = None
    temp = Node(item)

    while current is not None and current.data < item:
        previous = current
        current = current.next

    if previous is None:
        temp.next = self.head
        self.head = temp
    else:
        temp.next = current
        previous.next = temp

到目前为止讨论的 OrderedList 类可以在 ActiveCode 1 中找到。我们将剩余的方法留作练习。你应该仔细考虑无序列表的实现是否适用于有序列表。

Activity: 3.23.1 OrderedList 类
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
class Node:
    """链表的节点"""

    def __init__(self, node_data):
        self._data = node_data
        self._next = None

    def get_data(self):
        """获取节点数据"""
        return self._data

    def set_data(self, node_data):
        """设置节点数据"""
        self._data = node_data

    data = property(get_data, set_data)

    def get_next(self):
        """获取下一个节点"""
        return self._next

    def set_next(self, node_next):
        """设置下一个节点"""
        self._next = node_next

    next = property(get_next, set_next)

    def __str__(self):
        """字符串表示"""
        return str(self._data)


class OrderedList:
    """有序链表的实现"""
    def __init__(self):
        self.head = None

    def search(self, item):
        """搜索具有特定值的节点"""
        current = self.head
        while current is not None:
            if current.data == item:
                return True
            if current.data > item:
                return False
            current = current.next

        return False

    def add(self, item):
        """添加一个新节点"""
        current = self.head
        previous = None
        temp = Node(item)

        while current is not None and current.data < item:
            previous = current
            current = current.next

        if previous is None:
            temp.next = self.head
            self.head = temp
        else:
            temp.next = current
            previous.next = temp

    def is_empty(self):
        """列表是否为空"""
        return self.head == None

    def size(self):
        """列表的大小"""
        current = self.head
        count = 0
        while current is not None:
            count = count + 1
            current = current.next

        return count


my_list = OrderedList()
my_list.add(31)
my_list.add(77)
my_list.add(17)
my_list.add(93)
my_list.add(26)
my_list.add(54)

print(my_list.size())
print(my_list.search(93))
print(my_list.search(100))

In order to implement the ordered list, we must remember that the relative positions of the items are based on some underlying characteristic. The ordered list of integers given above (17, 26, 31, 54, 77, and 93) can be represented by a linked structure as shown in Figure 15. Again, the node and link structure is ideal for representing the relative positioning of the items.

Image title
Figure 15: An Ordered Linked List

To implement the OrderedList class, we will use the same technique as seen previously with unordered lists. Once again, an empty list will be denoted by a head reference to None (see Listing 8).

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

As we consider the operations for the ordered list, we should note that the is_empty and size methods can be implemented the same as with unordered lists since they deal only with the number of nodes in the list without regard to the actual item values. Likewise, the remove method will work just fine since we still need to find the item and then link around the node to remove it. The two remaining methods, search and add, will require some modification.

The search of an unordered linked list required that we traverse the nodes one at a time until we either find the item we are looking for or run out of nodes (None). It turns out that the same approach would work with the ordered list and no changes are necessary if the item is in the list. However, in the case where the item is not in the list, we can take advantage of the ordering to stop the search as soon as possible.

For example, Figure 16 shows the ordered linked list as a search is looking for the value 45. As we traverse, starting at the head of the list, we first compare against 17. Since 17 is not the item we are looking for, we move to the next node, in this case 26. Again, this is not what we want, so we move on to 31 and then on to 54. Now, at this point, something is different. Since 54 is not the item we are looking for, our former strategy would be to move forward. However, due to the fact that this is an ordered list, that will not be necessary. Once the value in the node becomes greater than the item we are searching for, the search can stop and return False. There is no way the item could exist further out in the linked list.

Image title
Figure 16: Searching an Ordered Linked List

Listing 9 shows the complete search method. It is easy to incorporate the new condition discussed above by adding another check (line 6). We can continue to look forward in the list (line 3). If any node is ever discovered that contains data greater than the item we are looking for, we will immediately return False. The remaining lines are identical to the unordered list search.

Listing 9
def search(self,item):
    current = self.head
    while current is not None:
        if current.data == item:
            return True
        if current.data > item:
            return False
        current = current.next

    return False

The most significant method modification will take place in add. Recall that for unordered lists, the add method could simply place a new node at the head of the list. It was the easiest point of access. Unfortunately, this will no longer work with ordered lists. It is now necessary that we discover the specific place where a new item belongs in the existing ordered list.

Assume we have the ordered list consisting of 17, 26, 54, 77, and 93 and we want to add the value 31. The add method must decide that the new item belongs between 26 and 54. Figure 17 shows the setup that we need. As we explained earlier, we need to traverse the linked list looking for the place where the new node will be added. We know we have found that place when either we run out of nodes (current becomes None) or the value of the current node becomes greater than the item we wish to add. In our example, seeing the value 54 causes us to stop.

Image title
Figure 17: Adding an Item to an Ordered Linked List

As we saw with unordered lists, it is necessary to have an additional reference, again called previous, since current will not provide access to the node that must be modified. Listing 10 shows the complete add method. Lines 3–4 set up the two external references and lines 8–9 again allow previous to follow one node behind current every time through the iteration. The condition (line 1) allows the iteration to continue as long as there are more nodes and the value in the current node is not larger than the item. In either case, when the iteration fails, we have found the location for the new node.

The remainder of the method completes the two-step process shown in Figure 17. Once a new node has been created for the item, the only remaining question is whether the new node will be added at the beginning of the linked list or some place in the middle. Again, previous is None (line 11) can be used to provide the answer.

Listing 10
def add(self, item):
    """Add a new node"""
    current = self.head
    previous = None
    temp = Node(item)

    while current is not None and current.data < item:
        previous = current
        current = current.next

    if previous is None:
        temp.next = self.head
        self.head = temp
    else:
        temp.next = current
        previous.next = temp

The OrderedList class with methods discussed thus far can be found in ActiveCode 1. We leave the remaining methods as exercises. You should carefully consider whether the unordered implementations will work given that the list is now ordered.

Activity: 3.23.1 OrderedList Class Thus Far
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
class Node:
    """A node of a linked list"""

    def __init__(self, node_data):
        self._data = node_data
        self._next = None

    def get_data(self):
        """Get node data"""
        return self._data

    def set_data(self, node_data):
        """Set node data"""
        self._data = node_data

    data = property(get_data, set_data)

    def get_next(self):
        """Get next node"""
        return self._next

    def set_next(self, node_next):
        """Set next node"""
        self._next = node_next

    next = property(get_next, set_next)

    def __str__(self):
        """String"""
        return str(self._data)


class OrderedList:
    """Ordered linked list implementation"""
    def __init__(self):
        self.head = None

    def search(self, item):
        """Search for a node with a specific value"""
        current = self.head
        while current is not None:
            if current.data == item:
                return True
            if current.data > item:
                return False
            current = current.next

        return False

    def add(self, item):
        """Add a new node"""
        current = self.head
        previous = None
        temp = Node(item)

        while current is not None and current.data < item:
            previous = current
            current = current.next

        if previous is None:
            temp.next = self.head
            self.head = temp
        else:
            temp.next = current
            previous.next = temp

    def is_empty(self):
        """Is the list empty"""
        return self.head == None

    def size(self):
        """Size of the list"""
        current = self.head
        count = 0
        while current is not None:
            count = count + 1
            current = current.next

        return count


my_list = OrderedList()
my_list.add(31)
my_list.add(77)
my_list.add(17)
my_list.add(93)
my_list.add(26)
my_list.add(54)

print(my_list.size())
print(my_list.search(93))
print(my_list.search(100))

3.23.1. 链表分析

3.23.1. Analysis of Linked Lists

为了分析链表操作的复杂性，我们需要考虑这些操作是否需要遍历。考虑一个有 \(n\) 个节点的链表。is_empty 方法的复杂度是 \(O(1)\)，因为只需要一步检查头引用是否为 None。另一方面，size 方法总是需要 \(n\) 步，因为没有办法知道链表中有多少个节点而不从头到尾遍历。因此，size 的复杂度是 \(O(n)\)。向无序链表添加一个项目的复杂度始终是 \(O(1)\)，因为我们只需将新节点放置在链表的头部。然而，search 和 remove 以及有序链表中的 add 都需要遍历过程。尽管平均情况下它们可能只需遍历链表的一半节点，这些方法的复杂度都是 \(O(n)\)，因为在最坏的情况下，每个方法都可能处理链表中的每个节点。

你可能还注意到，这种实现的性能与之前提到的 Python 列表的实际性能不同。这表明链表并不是 Python 列表的实现方式。Python 列表的实际实现基于数组的概念。我们将在最后一章中详细讨论这一点。

To analyze the complexity of the linked list operations, we need to consider whether they require traversal. Consider a linked list that has \(n\) nodes. The is_empty method is \(O(1)\) since it requires one step to check the head reference for None. size, on the other hand, will always require \(n\) steps since there is no way to know how many nodes are in the linked list without traversing from head to end. Therefore, size is \(O(n)\). Adding an item to an unordered list will always be \(O(1)\) since we simply place the new node at the head of the linked list. However, search and remove, as well as add for an ordered list, all require the traversal process. Although on average they may need to traverse only half of the nodes, these methods are all \(O(n)\) since in the worst case each will process every node in the list.

You may also have noticed that the performance of this implementation differs from the actual performance given earlier for Python lists. This suggests that linked lists are not the way Python lists are implemented. The actual implementation of a Python list is based on the notion of an array. We discuss this in more detail in the last chapter.

最后更新: 2024年9月12日
创建日期: 2024年9月9日