有上图可知，其实在《触“类”旁通》系列之前的四篇中，所操作的对象其实一直是节点和节点组成的链式结构，不能算是真正的链表。为此，我们有请单向链表的“主咖”出场：
链表类
1. class List(): 2. def __init__(self, node=None): 3. self.head = node
为了展示和操作方便，需要节点类以及几个最基本的方法协助：
class Node(): def __init__(self, value=None, Next=None): self.val = value self.next = Next if (type(self.next)==Node and self.next.val==None or type(self.next)!=Node and self.next!=None): self.next = None def __repr__(self): return f'{self.val}->{self.next}' @property def values(self): ret,ptr = [],self while ptr is not None: ret.append(ptr.val) ptr = ptr.next return ret def build(*data, split=True): '''把数据转换成节点链表''' lst,ret = [],Node() for val in data: if type(val) is str: if not split: lst.append(val) continue if str=='': continue try: num = int(val) lst.extend([int(_) for _ in val]) except: lst.extend([_ for _ in val]) elif hasattr(val,'__iter__'): lst.extend([_ for _ in val]) elif type(val) is Node: if val is not None: lst.extend(val.values) elif type(val) is List: if val.head is not None: lst.extend(val.head.values) else: lst.append(val) ret = Node() for i in lst[::-1]: ret = Node(i, ret) return ret class List(): def __init__(self, *node): self.head = Node.build(*node) def __repr__(self): return f'[{self.head}]'
创建链表
操作链表总得新建一个链表吧，不管是怎样去实现的(方法很原始)，总之这样新建链表就是非常方便，并且和内置的顺序列表作个对比，创建和返回值都有几分神似：
>>> List(1,2,3,4,5) [1->2->3->4->5->None] >>> List(range(1,11,2)) [1->3->5->7->9->None] >>> list((1,2,3,4,5)) [1, 2, 3, 4, 5] >>> list(range(1,11,2)) [1, 3, 5, 7, 9] >>>
以下所有代码都要放在class List()里，由此开始对单链表“主咖”的探索：
链表长度、判断是否为空
def __len__(self): return self.size() @property def length(self): return self.size() def is_empty(self): if self.head.val==None: return True else: return False def size(self): ret,ptr = 0,self.head if ptr.val==None: return 0 while ptr: ptr = ptr.next ret += 1 return ret
>>> list1 = List() >>> list1.is_empty() True >>> list1.size() 0 >>> len(list1) 0 >>> >>> list2 = List(1,2,3,4,5) >>> list2.is_empty() False >>> list2.size() 5 >>> len(list2) 5 >>>
单链表的尾结点
@property def tail(self): ptr = self.head while ptr.next: ptr = ptr.next return ptr # 方法.tail修饰成只读属性，返回尾节点 # 而.head头指针是可修改，因为指向头节点，一般就代表整个单链表
>>> list1 = List() >>> list1.tail None->None >>> list1.head None->None >>> list1 [None->None] >>> >>> list2 = List(1,2,3,4,5) >>> list2.tail 5->None >>> list2.head 1->2->3->4->5->None >>> list2 [1->2->3->4->5->None] >>>
创建链表副本
1. def copy(self): 2. return List(self.head)
>>> list1 = List(1,2,3) >>> list2 = list1.copy() >>> list2.head.val = 0 >>> list2 [0->2->3->None] >>> list1 [1->2->3->None] >>> list3 = list1 # 直接赋值相当于只是设置一个指针 >>> list3.head.val = 0 >>> list3 [0->2->3->None] >>> list1 [0->2->3->None] >>>
遍历和生成器
@property def values(self): if self.is_empty(): return [] ret,ptr = [],self.head while ptr: ret.append(ptr.val) ptr = ptr.next return ret def __iter__(self): ptr = self.head while ptr: yield ptr.val ptr = ptr.next @property def items(self): yield from self.values
yield 语法糖：
yield form iterable object (python 3.3+)
等价于：
for item in iterable:
yield item
>>> list1 = List(range(9)) >>> list1.items <generator object List.items at 0x0000000002F95270> >>> lstgen = list1.items >>> next(lstgen) 0 >>> next(lstgen) 1 >>> next(lstgen) 2 >>> next(lstgen) 3 >>> [i for i in lstgen] [4, 5, 6, 7, 8] >>> list1.values [0, 1, 2, 3, 4, 5, 6, 7, 8] >>>
头部插入
def push(self, data): if not isinstance(data, List): data = List(data) if self.is_empty(): self.head = data.head else: ret = data.head ret.next,self.head = self.head,ret return self
>>> list1 = List() >>> list1.push(3) [3->None] >>> list1 [3->None] >>> list1.push(Node(2)) [2->3->None] >>> list1 [2->3->None] >>> list1.push(List(1,2,3)) [1->2->3->None] >>> list1.push(range(5)) [0->1->2->3->None] >>> list1 [0->1->2->3->None] >>> >>> # 只增加一个节点
前插合并
def add(self, *data): data = List(*data) if self.is_empty(): self.head = data.head else: ptr = data.head while ptr.next: ptr = ptr.next ptr.next,self.head = self.head,data.head return self
>>> list1 = List() >>> list1.add(3,4,5) [3->4->5->None] >>> list1.add(1,2) [1->2->3->4->5->None] >>> list1 [1->2->3->4->5->None] >>> list1 = List(3,4) >>> list2 = List(1,2) >>> list1.add(list2) [1->2->3->4->None] >>> list1 [1->2->3->4->None] >>> list2 [1->2->None] >>>
尾部追加
def append(self, data): if not isinstance(data, List): data = List(data) if self.is_empty(): self.head = data.head else: ptr = self.head while ptr.next: ptr = ptr.next ptr.next = data.head return self
>>> list1 = List(1,2,3) >>> list1.append(4) [1->2->3->4->None] >>> list1.append(5) [1->2->3->4->5->None] >>> list1 [1->2->3->4->5->None] >>> >>> list2 = List() >>> list2.append(1) [1->None] >>> list2.append(2) [1->2->None] >>> list2.append(Node(3,Node(4))) [1->2->3->4->None] >>> list2 [1->2->3->4->None] >>> list1.append(list2) [1->2->3->4->5->1->2->3->4->None] >>> list1 [1->2->3->4->5->1->2->3->4->None] >>>
追加合并
1. def cat(self, *data): 2. for val in data: 3. self.append(val) 4. return self
>>> list1 = List(1,2,3) >>> list1.cat(4,5,6,7) [1->2->3->4->5->6->7->None] >>> list1 [1->2->3->4->5->6->7->None] >>> list2 = List() >>> list2.cat(1,2) [1->2->None] >>> list2 [1->2->None] >>> list2.cat(3,[4,5],range(6,9),List(9,10)) [1->2->3->4->5->6->7->8->9->10->None] >>> list2 [1->2->3->4->5->6->7->8->9->10->None] >>>
链表加法
def __add__(self, *data): self.cat(*data) return self def __radd__(self, *data): self.add(*data) return self
>>> List()+1+2+3 [1->2->3->None] >>> (1,2,3)+List() [1->2->3->None] >>> list0 = List() >>> list0 = 0 + list1 + 1 + 2 >>> list0 [0->1->2->None] >>> list1 = List(1,2,3) >>> list1 = 0 + list1 + 4 + 5 >>> list1 [0->1->2->3->4->5->None] >>> list2 = List() >>> for i in range(6): list2 += i >>> list2 [0->1->2->3->4->5->None] >>>
反转链表
def __reversed__(self): ptr,ret = self.head,List() while ptr: ret = ptr.val + ret ptr = ptr.next return ret def reverse(self): ptr,ret = self.head,List() while ptr: ret.push(ptr.val) ptr = ptr.next self.head = ret.head return self
>>> list1 = List(1,2,3) >>> reversed(list1) [3->2->1->None] >>> list1 [1->2->3->None] >>> list1.reverse() [3->2->1->None] >>> list1 [3->2->1->None] >>> list2 = List() >>> reversed(list2) [None->None] >>> list2.reverse() [None->None] >>> list2 [None->None] >>>
数据域的最大(小)值
def nlargest(self): if self.is_empty(): return None ptr,ret = self.head,self.head.val while ptr: ret = max(ret, ptr.val) ptr = ptr.next return ret def nsmallest(self): if self.is_empty(): return None ptr,ret = self.head,self.head.val while ptr: ret = min(ret, ptr.val) ptr = ptr.next return ret
>>> list1 = List(1,2,3) >>> list1.nlargest() 3 >>> list1.nsmallest() 1 >>> list2 = List(1,0,2,5,3) >>> list2.nlargest() 5 >>> list2.nsmallest() 0 >>>
指定数值的节点索引
返回数据域等于指定目标值num的第一个节点的索引号，头节点为0；找到返回索引号，若找不到 find() 返回 -1， index() 报错。
def find(self, num): if self.is_empty(): return -1 ptr,ret = self.head,-1 while ptr: ret += 1 if ptr.val == num: break ptr = ptr.next else: ret = -1 return ret def index(self, num): error = lambda i:ValueError(f'{i} is not in List') if self.is_empty(): raise error(num) ptr,ret = self.head,-1 while ptr: ret += 1 if ptr.val == num: break ptr = ptr.next else: raise error(num) return ret
>>> list1 = List(range(1,5)) >>> list1.find(1) 0 >>> list1.find(2) 1 >>> list1.find(5) -1 >>> list1.find(0) -1 >>> list2 = List(range(6)) >>> list2.index(0) 0 >>> list2.index(5) 5 >>> list2.index(6) Traceback (most recent call last): File "<pyshell#22>", line 1, in <module> list2.index(9) File "D:\List0821.py", line 202, in index raise error(num) ValueError: 9 is not in List >>>
指定数值的节点个数
def count(self, value): if self.is_empty(): return 0 ptr,ret = self.head,0 while ptr: if ptr.val==value: ret += 1 ptr = ptr.next return ret
>>> list1 = List(0,1,2,1,0,2,0,3,0,2) >>> list1.count(0) 4 >>> list1.count(1) 2 >>> list1.count(2) 3 >>> list1.count(3) 1 >>> list1.count(4) 0 >>>
包含和等于
def __contains__(self, data): if self.is_empty(): return False if isinstance(data,List): data = data.head if isinstance(data,Node): count = self.find(data.val)+1 if count==0: return False ptr1,ptr2 = self.head,data for _ in range(1,count): ptr1 = ptr1.next if ptr1 is None: return False while ptr2: if ptr1 is None or ptr1.val!=ptr2.val: return False ptr1,ptr2 = ptr1.next,ptr2.next return True else: return bool(1 + self.find(data)) def __eq__(self, data): if not isinstance(data,List): return False if data.is_empty(): if self.is_empty(): return True else: return False return data in self and self in data
>>> list1 = List(range(1,4)); >>> list2 = List(range(6)) >>> list1 in list2 True >>> list2 in list1 False >>> 2 in list1 True >>> 2 in list2 True >>> None in list1 False >>> Node() in list1 False >>> List() in list1 False >>> Node(1) in list1 True >>> List(2) in list1 True >>> Node(2,Node(3)) in list1 True >>> List(2,3,4) in list2 True >>> list3 = List(1, 2, 3) >>> list1 == list2 False >>> list1 == list3 True >>> list1 != list2 True >>> list1 != list3 False >>> List() == List(1) False >>> List() == List() True >>> List() == None False >>> List() != 1 True >>>
链表排序
python没提供重载__sorted__()方法，所有暂不支持内建函数sorted()，可能需要重载切片方法后变相来实现它。以下方法.sort()直接交换节点数据域实现，.sorted()排序但不改变自身：
def sort(self): length = self.size() for i in range(1, length): ptr = self.head for j in range(length - i): if ptr.val>ptr.next.val: ptr.val,ptr.next.val = ptr.next.val,ptr.val ptr = ptr.next return self def sorted(self): if self.size()<2: return self return List(self.head).sort()
>>> list1 = List(2,1,0,3,4,5,3) >>> list1.sorted() [0->1->2->3->3->4->5->None] >>> list1 [2->1->0->3->4->5->3->None] >>> list1.sort() [0->1->2->3->3->4->5->None] >>> list1 [0->1->2->3->3->4->5->None]
重载链表索引
def __getitem__(self, item): return self.values[item] def __setitem__(self, idx, value): length = self.size() if idx<0: idx += length if self.is_empty() or idx+1>length or idx<0: raise IndexError('List() index out of range.') if isinstance(value,Node) or isinstance(value,List): raise TypeError('value type Error') ptr = self.head for i in range(idx): ptr = ptr.next ptr.val = value
>>> list1 = List(range(1,6)) >>> list1 [1->2->3->4->5->None] >>> list1[0],list1[2],list1[4] (1, 3, 5) >>> list1[-1],list1[-3],list1[-5] (5, 3, 1) >>> list1[1] *= 5 >>> list1[3] += 6 >>> list1 [1->10->3->10->5->None] >>> list1[-1] = 0 >>> list1[-5] = -1 >>> list1 [-1->10->3->10->0->None] >>> list1[5], list1[-6] Traceback (most recent call last): File "<pyshell#62>", line 1, in <module> list1[5],list1[-6] File "D:/Python/List0823.py", line 103, in __getitem__ return self.values[item] IndexError: list index out of range >>> # 上节排序中预计的：有了切片功能就支持sorted()函数，但返回的是普通列表 >>> list2 = List(2,1,0,3,4,5,3) >>> sorted(list2) [0, 1, 2, 3, 3, 4, 5] >>> List(sorted(list2)) [0->1->2->3->3->4->5->None] >>> list2 [2->1->0->3->4->5->3->None] >>>
删除头节点或尾节点
def pop(self): if self.is_empty(): raise IndexError('pop from empty List.') if self.head.next is None: ret,self.head = self.head.val,Node() return ret ptr = self.head while ptr.next.next: ptr = ptr.next ret,ptr.next = ptr.next.val,None self = List(self.head) return ret def popfront(self): if self.is_empty(): raise IndexError('pop from empty List.') ret,ptr = self.head.val,self.head.next if ptr is None: self.head = Node() else: self.head = self.head.next return ret
>>> list1 = List(1,2,3) >>> list1.pop() 3 >>> list1.pop() 2 >>> list1.pop() 1 >>> list1.pop() Traceback (most recent call last): File "<pyshell#84>", line 1, in <module> list1.pop() File "D:\List0821.py", line 249, in pop raise IndexError('pop from empty List.') IndexError: pop from empty List. >>> list1 = List(1,2,3) >>> list1.popfront() 1 >>> list1.popfront() 2 >>> list1.popfront() 3 >>> list1.popfront() Traceback (most recent call last): File "<pyshell#89>", line 1, in <module> list1.popfront() File "D:\List0821.py", line 262, in popfront raise IndexError('pop from empty List.') IndexError: pop from empty List. >>>
重载索引删除的功能
删除指定索引的节点
def __delitem__(self, index): length = self.size() if index<0: index += length if self.is_empty() or index+1>length or index<0: raise IndexError('List() index out of range.') ptr = self.head if index>0: for i in range(index-1): ptr = ptr.next ptr.next = ptr.next.next else: if ptr.next is None: self.head = Node() else: self.head = self.head.next return self delete = __delitem__
>>> list1 = List(1,2,3,4) >>> list1.delete(-5) Traceback (most recent call last): File "<pyshell#115>", line 1, in <module> list1.delete(4) File "D:\List0821.py", line 272, in delete raise IndexError('List() index out of range.') IndexError: List() index out of range. >>> list1.delete(0) [2->3->4->None] >>> list1.delete(1) [2->4->None] >>> list1.delete(-2) [4->None] >>> list1.delete(-1) [None->None] >>> list2 = List(1,2,3,4) >>> del list2[0] >>> list2 [2->3->4->None] >>> del list2[1] >>> list2 [2->4->None] >>> del list2 >>> list2 Traceback (most recent call last): File "<pyshell#113>", line 1, in <module> list2 NameError: name 'list2' is not defined >>>
删除指定数值的节点
def remove(self, value): index = self.find(value) if index==-1: raise ValueError('List.remove(x): x not in List') self.delete(index) return self
>>> list1 = List(0,1,2,3) >>> list1.remove(1) [0->2->3->None] >>> list1.remove(0) [2->3->None] >>> list1.remove(3) [2->None] >>> list1.remove(3) Traceback (most recent call last): File "<pyshell#20>", line 1, in <module> list1.remove(3) File "D:\Python\List0823.py", line 169, in remove raise ValueError('List.remove(x): x not in List') ValueError: List.remove(x): x not in List >>> list1.remove(2) [None->None]
