用Python链表实现有序表与无序表

dlnb526

用Python链表实现有序表与无序表

《数据结构与算法》MOOC（北大地空）课堂笔记
2020.4
by dlnb526

啥是链表
链表,顾名思义，顾名思义，链表像锁链一样，由一节节节点连在一起，组成一条数据链。
为什么要使用链表？
在之前用了python中的列表（list）来实现各种数据结构，然而有的语言可能并没有提供像python的列表一样强大的功能，我们必须要自己实现列表。

无序列表
概述
列表可以看作是一个无序的列表。
无序，也就是说它里面的元素没有一定的顺序，比如这样一个列表：

a = [1,2,'ads',54,32]

这里面的每个元素没有按照一定的规则排序，所以就叫无序。

                               
登录/注册后可看大图

无序列表应该有以下的方法

• list() 创建一个新的空列表。它不需要参数，而返回一个空列表。
• add(item) 将新项添加到列表，没有返回值。假设元素不在列表中。
• remove(item) 从列表中删除元素。需要一个参数，并会修改列表。此处假设元素在列表中。
• search(item) 搜索列表中的元素。需要一个参数，并返回一个布尔值。
• isEmpty() 判断列表是否为空。不需要参数，并返回一个布尔值。
• size() 返回列表的元素数。不需要参数，并返回一个整数。
• append(item) 在列表末端添加一个新的元素。它需要一个参数，没有返回值。假设该项目不在列表中。
• index(item) 返回元素在列表中的位置。它需要一个参数，并返回位置索引值。
• 此处假设该元素原本在列表中。
• insert(pos,item) 在指定的位置添加一个新元素。它需要两个参数，没有返回值。假设该元素在列表中并不存在，并且列表有足够的长度满足参数提供的索引需要。
• pop() 从列表末端移除一个元素并返回它。它不需要参数，返回一个元素。假设列表至少有一个元素。
• pop(pos) 从指定的位置移除列表元素并返回它。它需要一个位置参数，并返回一个元素。假设该元素在列表中。
  

节点
为了实现无序列表，我们采用链表的方式。
链表最基本的元素是节点。

每个节点对象必须持有至少两条信息。

首先，节点必须包含列表元素本身。我们将这称为该节点的“数据区”（data field）。
此外，每个节点必须保持到下个节点的引用。
如果没有下一个节点，那我们就记录为None

1. class Node:#节点这个类~
   
2.     def __init__(self,initdata):
   
3.         self.data = initdata
   
4.         self.next = None#初始化的时候头节点后面没有节点了
   
5. 
   
6.     def getData(self):
   
7.         return self.data #节点可以获取自身数据
   
8. 
   
9.     def getNext(self):
   
10.         return self.next #节点可以获取指向的下一个节点
    
11. 
    
12.     def setData(self,newdata):
    
13.         self.data = newdata
    
14. 
    
15.     def setNext(self,newnext):#节点可以对下一个节点进行更新
    
16.         self.next = newnext

复制代码

上面我们就把一个节点建立起来了，那如何把节点连接起来呢。

无序表的链表实现
操作举例
1. 添加数据项add
通过之前的方式建立了一个节点，如果初始化它我们知道他是一个在开头的节点，后面是None.由于无序表是从表头开始逐个向后查找，新数据所以插入到表头是我们的最佳选择。

1. def add(self,item):
   
2.         temp = Node(item) #新的要插入的数据初始化为一个节点
   
3.         temp.setNext(self.head)#但当前节点的下一个指向为之前链表的头部
   
4.         self.head = temp#把插入的节点设为新链表的头部

复制代码

2. size()的实现 和 search()的实现
  

1. def size(self):
   
2.         current = self.head
   
3.         count = 0
   
4.         while current != None:
   
5.             count = count + 1
   
6.             current = current.getNext()
   
7. 
   
8.         return count
   
9.     def search(self,item):
   
10.         current = self.head
    
11.         found = False
    
12.         while current != None and not found:
    
13.             if current.getData() == item:
    
14.                 found = True
    
15.             else:
    
16.                 current = current.getNext()
    
17.         return found

复制代码

没什么可说的，设置一个计数器，然后遍历元素。

3. remove(item)实现
我们需要先用类似search的方法找到元素，然后它指向的后一个元素和前一个元素怎么连在一起呢？
这时就需要维护前一个节点的引用。

1. def remove(self,item):
   
2.         current = self.head
   
3.         previous = None
   
4.         found = False
   
5.         while not found:
   
6.             if current.getData() == item:
   
7.                 found = True
   
8.             else:
   
9.                 previous = current#不断地往后找，然后把当前的节点记作前一个结点，这样在找到后就可以对前一个结点进行操作。
   
10.                 current = current.getNext()
    
11.    
    
12.         if previous == None:
    
13.             self.head = current.getNext()
    
14.         else:
    
15.             previous.setNext(current.getNext())

复制代码

好了那下面我们来看无序表的完整实现

游客，如果您要查看本帖隐藏内容请回复

有序链表
概述
之前无序链表时我们就能推测出有序的意思，也就是排列过大小的呗~
有序表依据数据项的可比性质（如整数大小，字母表前后）来决定数据项在列表中的位置。
比如下面我们要实现越小的越靠近列表头的操作。

                               
登录/注册后可看大图

有序表中的操作：

• OrderedList()：创建一个新的空有序列表。它返回一个空有序列表并且不需要传递任何参数。
• add(item):在保持原有顺序的情况下向列表中添加一个新的元素，新的元素作为参数传递进函数而函数无返回值。假设列表中原先并不存在这个元素。
• remove(item):从列表中删除某个元素。欲删除的元素作为参数，并且会修改原列表。假设原列表
• 中存在欲删除的元素。
• search(item)：在列表中搜索某个元素，被搜索元素作为参数，返回一个布尔值。
• isEmpty()：测试列表是否为空，不需要输入参数并且其返回一个布尔值。
• size()：返回列表中元素的数量。不需要参数，返回一个整数。
• index(item)：返回元素在列表中的位置。需要被搜索的元素作为参数输入，返回此元素的索引值。假设这个元素在列表中。
• pop()：删除并返回列表中的最后一项。不需要参数，返回删除的元素。假设列表中至少有一个元素。
• pop(pos)：删除并返回索引 pos 指定项。需要被删除元素的索引值作为参数，并且返回这个元素。假设该元素在列表中。
  

                               
登录/注册后可看大图

有序链表的实现
其实大部分操作都和无序表相同

search()方法
在无序表中如果不存在，搜索的时候会遍历整个表。
但是在有序表中，因为有顺序，一旦当前节点大于要查找的数据，就直接宣判死刑可以返回False了。

1. def search(self,item):
   
2.         current = self.head
   
3.         found = False
   
4.         stop = False# 加入了一个stop可以直接停住
   
5.         while current != None and not found and not stop:#这里有三个条件
   
6.             if current.getData() == item:
   
7.                 found = True
   
8.             else:
   
9.                 if current.getData() > item:
   
10.                     stop = True
    
11.                 else:
    
12.                     current = current.getNext()
    
13. 
    
14.         return found

复制代码

add()方法
和无序表相比，改动最大的方法是 add。回想一下在无序列表中的 add 方法，只需要在原列表头加一个新的节点。然而在有序表里我们要找到大小合适的位置才行。

所以我们还是要定位一个previous（前一个元素）。

1. def add(self,item):
   
2.         current = self.head
   
3.         previous = None
   
4.         stop = False
   
5.         while current != None and not stop:
   
6.             if current.getData() > item:
   
7.                 stop = True
   
8.             else:
   
9.                 previous = current
   
10.                 current = current.getNext()
    
11. 
    
12.         temp = Node(item)
    
13.         if previous == None:
    
14.             temp.setNext(self.head)
    
15.             self.head = temp
    
16.         else:
    
17.             temp.setNext(current)
    
18.             previous.setNext(temp)      

复制代码

有序表的完整实现如下：

游客，如果您要查看本帖隐藏内容请回复

总结分析
当分析链表方法的复杂度时，我们应该考虑它们是否需要遍历链表。考虑一个有 n 个节点的链表，isEmpty 方法复杂度是 O（1），因为它只需要检查链表的头指针是否为 None。对于方法 size，则总需要 n 个步骤，因为除了遍历整个链表以外，没有办法知道链表的节点数。因此，size 方法的复杂度是 O（n）。无序列表的 add 方法的复杂度是 O（1），因为我们永远只需要在链表的头部简单地添加一个新的节点。但是，search、remove 和在有序列表中的 add 方法，需要遍历。尽管在平均情况下，它们可能只需要遍历一半的节点，但这些方法的复杂度都是 O(n)，因为在最糟糕的情况下需要遍历整个链表。

1. 参考资料：MOOC配套教材及代码
   
2. 《Python数据结构与算法分析》 第2版

复制代码

伍陆柒5678

感谢楼主分享

Deteriorat

666