一、链表
链表中每一个元素都由为两部分构成：一是该链表节点的数据，二是指向下一个节点的引用。
1、定义节点类，链表中的节点包含数据以及指向下一个节点的引用，在构造方法中定义一个变量data用于存储数据，另定义一个变量next等于None，即指向None的引用，代表传入的节点后面没有元素（由于不确定传入的元素数目），使其指向一个空值；
# 节点类 class Node: def __init__(self, initdata): self.data = initdata self.next = None # 指向空值，初始化next
2、返回当前指向节点的数据
def getData(self): return self.data # 返回当前数据，无需参数
3、返回当前指向节点指向下一个节点的引用
def getNext(self): return self.next # 返回当前指向下一个节点的引用，无需参数
4、传入新的节点数据
def setData(self, newdata): self.data = newdata # 添加新的数据，包含参数newdata
5、传入指向下一个节点的引用
def setNext(self, newnext): self.next = newnext # 添加新的指向引用，包含参数newnext
通过向链表中添加节点数据以及指向和传入节点的引用来测试，完整代码如下：
# 节点类 class Node: def __init__(self, initdata): self.data = initdata self.next = None # 指向空值，初始化next def getData(self): return self.data # 返回当前数据，无需参数 def getNext(self): return self.next # 返回当前指向下一个节点的引用，无需参数 def setData(self, newdata): self.data = newdata # 添加新的数据，包含参数newdata def setNext(self, newnext): self.next = newnext # 添加新的指向引用，包含参数newnext c = Node(2) # 向链表中传入节点数据"2" print(c.getData()) # 获取当前指向节点的数据 print(c.getNext()) # 返回当前指向节点指向下一个节点的引用，由于初始化指向引用为None，所以为None c.setData(36) # 传入新的节点数据"36" print(c.getData()) # 获取当前指向节点的数据 c.setData("st") c.setNext("st") # 传入指向下一个节点的引用为st print(c.getNext()) print(c.getData())
运行结果如下：
二、无序链表 实现步骤分析
通过定义一个无序列表UnorderedList类，然后基于链表Node类的方法实现无序链表，无序列表本身不包含链表中的任何节点，只是其头部指向整个链表结构中第一个节点的引用，该节点包含指向下一个节点的引用。
1、定义无序列表类，head指向None，它表示无序列表的头部没有指向任何节点，即说明这是一个空列表。
# 无序列表类 class UnorderedList: def __init__(self): self.head = None # 表示无序列表的头部没有指向任何节点
2、检查列表是否为空，通过比较运算符“==”比较队列是否为空（None），若为空，则返回布尔值False，若不为空，则返回True；
def isEmpty(self): # 检查无序列表是否为空，不需要参数，返回一个布尔值 return self.head == None
3、向列表中添加元素，通过节点类Node()的构造方法添加新元素temp，然后利用节点类的setNext()方法传入新的指向引用，即指向链表的头部，此时再将新元素赋值给链表的头部；
def add(self, item): # 向列表中添加元素 temp = Node(item) # 添加新元素temp temp.setNext(self.head) # 传入新的指向引用，指向链表的头部 self.head = temp # 将新元素赋值给链表的头部
4、返回列表中元素数目，首先初始化变量current将列表的头节点赋值给它，然后对列表进行遍历；
def length(self): # 返回列表中元素数目 current = self.head # 定义中间变量current，列表的头节点赋值给该变量 count = 0 while current != None: # 列表遍历 count = count + 1 # 每当指向一个节点，变量count递加1 current = current.getNext() # 返回当前指向下一个节点的引用并赋值给变量current return count
5、搜索指定的列表元素，通过输入参数item搜索，遍历列表，found作为一个布尔值，初值为False，若定义的中间变量current的数据等于要搜索的元素时，则说明已搜索到该元素，并将布尔值True赋值给变量found，改变其值然后返回True值；
def search(self, item): # 在列表中搜索元素item，需参数item current = self.head # 定义中间变量current，列表的头节点赋值给该变量 found = False while current != None and not found: if current.geatData() == item: # 若定义的中间变量的数据等于要搜索的元素时，则将布尔值True赋值给变量found，改变其值 found = True else: # 若不是要搜索的元素，即对下一个节点进行搜索 current = current.getNext() # 返回当前指向下一个节点的引用并赋值给变量current return found
6、删除指定的列表元素，删除操作的第一步也是先搜索要要删除的元素；
def remove(self, item): # 从列表中删除元素item，需参数item current = self.head # 定义中间变量current，列表的头节点赋值给该变量，标记当前位置 previous = None # 定义变量previous为空 found = False while not found: # 若定义的found变量布尔值为True时，while循环一直执行下去 if current.getData() == item: found = True else: # 若found变量布尔值改变，执行以下操作 previous = current # 将列表的头节点赋值给该变量previous current = current.getNext() # 返回当前指向下一个节点的引用并赋值给变量current if previous == None: # 若要删除的元素是列表中的头节点时，需改变列表的头节点 self.head = current.getNext() # 返回当前指向下一个节点的引用并赋值给列表的头节点 else: previous.setNext(current.getNext()) # 使用previous的setNext方法来完成移除操作，添加新的指向引用，修改后的引用都指向当前指向下一个节点的引用
三、无序链表的Python实现代码
完整代码及测试如下：
# 节点类 class Node: def __init__(self, initdata): self.data = initdata self.next = None # 指向空值，初始化next def getData(self): return self.data # 返回当前数据，无需参数 def getNext(self): return self.next # 返回当前指向下一个节点的引用，无需参数 def setData(self, newdata): self.data = newdata # 添加新的数据，包含参数newdata def setNext(self, newnext): self.next = newnext # 添加新的指向引用，包含参数newnext # 无序列表类 class UnorderedList: def __init__(self): self.head = None # 表示无序列表的头部没有指向任何节点 def isEmpty(self): # 检查无序列表是否为空，不需要参数，返回一个布尔值 return self.head == None def add(self, item): # 向列表中添加元素 temp = Node(item) # 通过节点类Node()的构造方法添加新元素temp temp.setNext(self.head) # 通过节点类的setNext()方法传入新的指向引用，指向链表的头部 self.head = temp # 将新元素赋值给链表的头部 def length(self): # 返回列表中元素数目 current = self.head # 定义中间变量current，列表的头节点赋值给该变量，标记当前位置 count = 0 while current != None: # 列表遍历 count = count + 1 # 每当指向一个节点，变量count递加1 current = current.getNext() # 返回当前指向下一个节点的引用并赋值给变量current return count def search(self, item): # 在列表中搜索元素item，需参数item current = self.head # 定义中间变量current，列表的头节点赋值给该变量，标记当前位置 found = False while current != None and not found: if current.getData() == item: # 若定义的中间变量的数据等于要搜索的元素时，则将布尔值True赋值给变量found，改变其值 found = True else: # 若不是要搜索的元素，即对下一个节点进行搜索 current = current.getNext() # 返回当前指向下一个节点的引用并赋值给变量current return found def remove(self, item): # 从列表中删除元素item，需参数item current = self.head # 定义中间变量current，列表的头节点赋值给该变量，标记当前位置 previous = None # 定义变量previous为空 found = False while not found: # 若定义的found变量布尔值为True时，while循环一直执行下去 if current.getData() == item: found = True else: # 若found变量布尔值改变，执行以下操作 previous = current # 将列表的头节点赋值给该变量previous current = current.getNext() # 返回当前指向下一个节点的引用并赋值给变量current if previous == None: # 若要删除的元素是列表中的头节点时，需改变列表的头节点 self.head = current.getNext() # 返回当前指向下一个节点的引用并赋值给列表的头节点 else: previous.setNext(current.getNext()) # 使用previous的setNext方法来完成移除操作，添加新的指向引用，修改后的引用都指向当前指向下一个节点的引用 # 测试 mylist = UnorderedList() # 创建一个无序链表 print(mylist.isEmpty()) # 检查链表是否为空 mylist.add(39) mylist.add(154) mylist.add("trr") mylist.add(10) print(mylist.isEmpty()) print(mylist.length()) # 返回列表的元素数目 print(mylist.search(21)) print(mylist.search("trr")) mylist.remove(39) print(mylist.length()) print(mylist.search(39))
运行结果如下：
四、有序链表 实现步骤分析
通过定义一个有序列表OrderedList类，然后基于链表Node类的方法实现有序链表，有序列表为升序排列或降序排列，它的一些操作基本与无序列表相同，只是search搜索元素和add添加元素要需要根据其修改。
1、定义有序列表类，与有序列表一样，也是head引用指向None，代表它是一个空列表；
# 无序列表类 class OrderedList: def __init__(self): self.head = None # 表示无序列表的头部没有指向任何节点
2、检查列表是否为空，通过比较运算符“==”比较队列是否为空（None），若为空，则返回布尔值False，若不为空，则返回True；
def isEmpty(self): # 检查无序列表是否为空，不需要参数，返回一个布尔值 return self.head == None
3、向列表中添加元素，首先确定位置然后条件元素；
def add(self, item): # 向列表中添加元素 current = self.head # 定义中间变量current，列表的头节点赋值给该变量，标记当前位置 previous = None # 定义变量previous值为空 stop = False while current != None and not stop: # 变量previous值跟在变量current后面，只要还有节点且不大于要添加的元素while循环一直进行下去 if current.getData() > item: stop = True else: previous = current current = current.getNext() temp = Node(item) # 通过节点类Node()的构造方法添加新元素temp if previous == None: # 判断添加的元素添加到链表的开头还是中间某个位置 temp.setNext(self.head) # 通过节点类的setNext()方法传入新的指向引用，指向链表的头部 self.head = temp # 将新元素赋值给链表的头部 else: temp.setNext(current) previous.setNext(temp)
4、返回列表中元素数目，首先初始化变量current将列表的头节点赋值给它，然后对列表进行遍历；
def length(self): # 返回列表中元素数目 current = self.head # 定义中间变量current，列表的头节点赋值给该变量 count = 0 while current != None: # 列表遍历 count = count + 1 # 每当指向一个节点，变量count递加1 current = current.getNext() # 返回当前指向下一个节点的引用并赋值给变量current return count
5、搜索指定的列表元素，通过输入参数item搜索，遍历列表，found作为一个布尔值，初值为False，若定义的中间变量current的数据等于要搜索的元素时，则说明已搜索到该元素，并将布尔值True赋值给变量found，改变其值然后返回True值，若不是要搜索的元素，即对下一个节点进行搜索，遇到中间值大于目标元素的节点，则将stop值设为True，否则将中间变量的指向下一个节点的引用赋值给current，然后继续进行while循环；
def search(self, item): # 在列表中搜索元素item，需参数item current = self.head # 定义中间变量current，列表的头节点赋值给该变量，标记当前位置 found = False stop = False while current != None and not found and not stop: if current.getData() == item: # 若定义的中间变量的数据等于要搜索的元素时，则将布尔值True赋值给变量found，改变其值 found = True else: # 若不是要搜索的元素，即对下一个节点进行搜索 if current.getData() > item: # 若遇到中间值大于目标元素的节点，则将stop值设为True stop = True else: current = current.getNext() # 否则返回当前指向下一个节点的引用并赋值给变量current return found
6、删除指定的列表元素，删除操作的第一步也是先搜索要要删除的元素；
def remove(self, item): # 从列表中删除元素item，需参数item current = self.head # 定义中间变量current，列表的头节点赋值给该变量，标记当前位置 previous = None # 定义变量previous为空 found = False while not found: # 若定义的found变量布尔值为True时，while循环一直执行下去 if current.getData() == item: found = True else: # 若found变量布尔值改变，执行以下操作 previous = current # 将列表的头节点赋值给该变量previous current = current.getNext() # 返回当前指向下一个节点的引用并赋值给变量current if previous == None: # 若要删除的元素是列表中的头节点时，需改变列表的头节点 self.head = current.getNext() # 返回当前指向下一个节点的引用并赋值给列表的头节点 else: previous.setNext(current.getNext()) # 使用previous的setNext方法来完成移除操作，添加新的指向引用，修改后的引用都指向当前指向下一个节点的引用
五、有序链表的Python实现代码
完整代码及测试如下：
# 节点类 class Node: def __init__(self, initdata): self.data = initdata self.next = None # 指向空值，初始化next def getData(self): return self.data # 返回当前数据，无需参数 def getNext(self): return self.next # 返回当前指向下一个节点的引用，无需参数 def setData(self, newdata): self.data = newdata # 添加新的数据，包含参数newdata def setNext(self, newnext): self.next = newnext # 添加新的指向引用，包含参数newnext # 无序列表类 class OrderedList: def __init__(self): self.head = None # 表示无序列表的头部没有指向任何节点 def isEmpty(self): # 检查无序列表是否为空，不需要参数，返回一个布尔值 return self.head == None def add(self, item): # 向列表中添加元素 current = self.head # 定义中间变量current，列表的头节点赋值给该变量，标记当前位置 previous = None # 定义变量previous值为空 stop = False while current != None and not stop: # 变量previous值跟在变量current后面，只要还有节点且不大于要添加的元素while循环一直进行下去 if current.getData() > item: stop = True else: previous = current current = current.getNext() temp = Node(item) # 通过节点类Node()的构造方法添加新元素temp if previous == None: # 判断添加的元素添加到链表的开头还是中间某个位置 temp.setNext(self.head) # 通过节点类的setNext()方法传入新的指向引用，指向链表的头部 self.head = temp # 将新元素赋值给链表的头部 else: temp.setNext(current) previous.setNext(temp) def length(self): # 返回列表中元素数目 current = self.head # 定义中间变量current，列表的头节点赋值给该变量，标记当前位置 count = 0 while current != None: # 列表遍历 count = count + 1 # 每当指向一个节点，变量count递加1 current = current.getNext() # 返回当前指向下一个节点的引用并赋值给变量current return count def search(self, item): # 在列表中搜索元素item，需参数item current = self.head # 定义中间变量current，列表的头节点赋值给该变量，标记当前位置 found = False stop = False while current != None and not found and not stop: if current.getData() == item: # 若定义的中间变量的数据等于要搜索的元素时，则将布尔值True赋值给变量found，改变其值 found = True else: # 若不是要搜索的元素，即对下一个节点进行搜索 if current.getData() > item: # 若遇到中间值大于目标元素的节点，则将stop值设为True stop = True else: current = current.getNext() # 否则返回当前指向下一个节点的引用并赋值给变量current return found def remove(self, item): # 从列表中删除元素item，需参数item current = self.head # 定义中间变量current，列表的头节点赋值给该变量，标记当前位置 previous = None # 定义变量previous值为空 found = False while not found: # 若定义的found变量布尔值为True时，while循环一直执行下去 if current.getData() == item: found = True else: # 若found变量布尔值改变，执行以下操作 previous = current # 将列表的头节点赋值给该变量previous current = current.getNext() # 返回当前指向下一个节点的引用并赋值给变量current if previous == None: # 若要删除的元素是列表中的头节点时，需改变列表的头节点 self.head = current.getNext() # 返回当前指向下一个节点的引用并赋值给列表的头节点 else: previous.setNext(current.getNext()) # 使用previous的setNext方法来完成移除操作，添加新的指向引用，修改后的引用都指向当前指向下一个节点的引用 # 测试 mylist = OrderedList() # 创建一个有序链表 print(mylist.isEmpty()) # 检查链表是否为空 mylist.add(39) # 添加元素 mylist.add(154) mylist.add(10) print(mylist.isEmpty()) print(mylist.length()) # 返回列表的元素数目 print(mylist.search(21)) mylist.remove(39) # 移除元素39 print(mylist.length()) print(mylist.search(39))
运行结果如下：
