python 并发
并发与并行的区别
并发（Concurrency）和 并行（Paralle）是两个相关但不同的概念。
并行：指的是在同一时刻，多个任务可以同时进行，彼此之间互不干扰。在这种情况下，多个处理单元（如多核处理器）同时执行不同的任务。并行处理意味着任务之间真正同时执行。
并发：指的是在一段时间内，多个任务交替进行，每个任务都在一段时间内得到执行。尽管这些任务可能在同一时刻被处理，但它们之间可能交替执行或并行执行（如果有多个处理单元）。并发强调的是多个任务之间存在时间上的交替，而不一定是真正的同时执行。
举例来说：
假设有一条高速公路，有双向4车道。每辆车（数据）可以在自己的车道上行驶（传输），这是并行。在同一时刻，每条车道上可能同时有车辆行驶，这是并行。而在一段时间内，有多辆车要通过，这是并发。
总之，并行是指多个任务在同一时刻真正同时执行，而并发是指多个任务在一段时间内交替执行，可能同时发生，也可能不同时发生。并行通常是通过水平扩展方式来解决并发问题的一种手段。
进程和线程
进程（Process）
进程是计算机中程序关于某数据集合上的一次运行活动，是系统进行资源分配和调度的基本单位，也是操作系统结构的基础。以下是关于进程的一些重要概念：
- 定义：进程是程序被操作系统加载到内存中后的执行实例，包含指令和数据，是程序执行的环境。
- 进程和程序关系：程序是源代码编译后的文件，而进程是程序在内存中的执行实例，也是线程的容器。
- 特点：每个进程都有自己独立的内存空间，相互之间不会直接影响，可以独立运行和管理。
- 父子关系：Linux 中的进程有父进程和子进程之分，而在 Windows 中，进程之间是平等关系。
线程（Thread）
线程是操作系统能够进行运算调度的最小单位，是进程中的实际运作单位。以下是关于线程的一些重要概念：
- 定义：线程是程序执行流的最小单元，有时被称为轻量级进程（Lightweight Process，LWP）。
- 组成：一个标准的线程由线程ID、当前指令指针（PC）、寄存器集合和堆、栈组成。
- 特点：线程是进程的一部分，共享相同的地址空间和其他资源，但拥有独立的栈空间和指令执行流程。
- 创建效率：在许多系统中，创建一个线程比创建一个进程快 10-100 倍。
进程、线程的理解
- 现代操作系统提出进程的概念，每一个进程都认为自己独占所有的计算机硬件资源;
- 进程就是独立的王国，进程间不可以随便的共享数据;
- 线程就是省份，同一个进程内的线程可以共享进程的资源，每一个线程拥有自己独立的堆栈。
线程的状态
| 状态 | 含义 |
|---|---|
| 就绪(Ready) | 线程能够运行，但在等待被调度。可能线程刚刚创建启动，或刚刚从阻塞中恢复，或者被其他线程抢占。 |
| 运行(Running) | 线程正在运行。 |
| 阻塞(Blocked) | 线程等待外部事件发生而无法运行，如 I/O 操作。 |
| 终止(Terminated) | 线程完成，或退出，或被取消。 |
python中的进程和线程
运行程序会启动一个解释器进程，线程共享一个解释器进程;
python的线程开发
python的线程开发使用标准库threading;
进程靠线程执行代码、至少有一个主线程，其它线程是工作线程;
主线程是第一个启动的线程;
父线程: 如果线程A中启动了一个线程B,A就是B的父线程;
子线程: B就是A的子线程。
Thread类
# 签名 def __init__(self, group=None, target=None, name=None, args=(), kwargs=None, *, daemon=None):
| 参数名 | 含义 |
|---|---|
target |
线程调用的对象，就是目标函数。 |
name |
为线程起个名字。 |
args |
为目标函数传递实参，元组。 |
kwargs |
为目标函数关键字传参，字典。 |
线程启动
import threading import time # 定义一个函数 def worker(): print('I am working ~~~') num = 50 for i in range(int(num)): time.sleep(0.3) print('working...' + '===' * i + '>' + '###' * (int(num) - i - 1), end='\r') print('I am finished ~~~') t = threading.Thread(target=worker, name='worker') # target 是一个函数，name 是线程的名字,只创建了一个线程管理对象 t.start() # 启动线程 ,调用系统调用，创建真正的操作系统的线程，启动运行target函数
线程退出
Python没有提供退出的方法, 线程在下面情况时退出;
- 线程函数内语句执行完毕;
- 线程函数中抛出未处理的异常;
import threading import time # 定义一个函数 def worker(): print('I am working ~~~') num = 50 for i in range(int(num)): time.sleep(0.3) print('working...' + '===' * i + '>' + '###' * (int(num) - i - 1), end='\r') print('I am finished ~~~') t = threading.Thread(target=worker, name='worker') # target 是一个函数，name 是线程的名字,只创建了一个线程管理对象 t.start() # 启动线程 ,调用系统调用，创建真正的操作系统的线程，启动运行target函数
因此在线程中应该尽可能捕获异常
线程传参
# 线程的传参问题 def add(x,y): print() print (x + y) return x + y # 目前情况下, 线程的返回值拿不到 # t = threading.Thread(target=add, args=(3,4), name='add') t = threading.Thread(target=add, name='add', args=(), kwargs={'x':3, 'y':4}) t.start()
threading的属性和方法
| 名称 | 含义 |
|---|---|
current_thread() |
返回当前线程对象。 |
main_thread() |
返回主线程对象。 |
active_count() |
当前处于alive状态的线程个数。 |
enumerate() |
返回所有活着的线程的列表，不包括已经终止的线程和未开始的线程。 |
get_ident() |
返回当前线程的ID，非0整数。 |
# # 定义一个函数 def showthreadinfo(): print(threading.main_thread(), threading.current_thread(), threading.active_count()) # 返回主线程的线程对象,返回当前线程的线程对象,返回当前活跃的线程数 def worker(): showthreadinfo() print('I am working ~~~') num = 50 for i in range(int(num)): time.sleep(0.2) if i != 20: print('working...' + '===' * i + '>' + '###' * (int(num) - i - 1), end='\r') else: print('\rNow 初始化工具 完成了 ！！！', end='\r') time.sleep(1) print('I am finished ~~~') t = threading.Thread(target=worker, name='worker') # target 是一个函数，name 是线程的名字,只创建了一个线程管理对象 time.sleep(2) showthreadinfo() t.start() # 启动线程 ,调用系统调用，创建真正的操作系统的线程，启动运行target函数 # <_MainThread(MainThread, started 7982456512)> <_MainThread(MainThread, started 7982456512)> 1 # <_MainThread(MainThread, started 7982456512)> <Thread(worker, started 6106722304)> 2 # I am working ~~~ # I am finished ~~~============================================================================================================================================>
import threading import time class MyThread(threading.Thread): def start(self) -> None: print('start ----') super().start() def run(self) -> None: print('run ----') super().run() def worker(): print('I am working ~~~') num = 50 for i in range(int(num)): time.sleep(0.2) if i != 20: print('working...' + '===' * i + '>' + '###' * (int(num) - i - 1), end='\r') else: print('\r]\t\t\t\t\tNow 初始化工具 完成了 ！！！', end='\r') time.sleep(1) print('I am finished ~~~') t = MyThread(target=worker,name='worker') time.sleep(2) # t.start() 调用 系统调用，创建真正的操作系统的线程，启动运行target函数，且只能start一次，否则报错: RuntimeError: threads can only be started once #t.run() # run是直接调函数，不会创建新的线程，只是调用了target函数 t.start() # start 是创建线程后,并启动线程 x = threading.main_thread() print(type(x).mro()) print(x.name, x.ident, x.is_alive()) # 正常情况下，主线程就要是管理线程的，如果有任务，就创建一个线程管理对象，然后启动子线程 while True: time.sleep(1) if t.is_alive(): print(threading.active_count(),threading.enumerate()) if threading.active_count() == 1: break #print('I will restart t ~~~') # t.start() 因此要注意，只要线程启过一次，就不能再启动了，否则报错: RuntimeError: threads can only be started once # start ---- # run ---- # I am working ~~~ # [<class 'threading._MainThread'>, <class 'threading.Thread'>, <class 'object'>] # MainThread 7982456512 True # 2 [<_MainThread(MainThread, started 7982456512)>, <MyThread(worker, started 6146437120)>]##################################################################### # 2 [<_MainThread(MainThread, started 7982456512)>, <MyThread(worker, started 6146437120)>]##################################################################### # 2 [<_MainThread(MainThread, started 7982456512)>, <MyThread(worker, started 6146437120)>]##################################################################### # 2 [<_MainThread(MainThread, started 7982456512)>, <MyThread(worker, started 6146437120)>]##################################################################### # 2 [<_MainThread(MainThread, started 7982456512)>, <MyThread(worker, started 6146437120)>]##################################################################### # 2 [<_MainThread(MainThread, started 7982456512)>, <MyThread(worker, started 6146437120)>]##################################################################### # 2 [<_MainThread(MainThread, started 7982456512)>, <MyThread(worker, started 6146437120)>]=====>############################################################### # 2 [<_MainThread(MainThread, started 7982456512)>, <MyThread(worker, started 6146437120)>]====================>################################################ # 2 [<_MainThread(MainThread, started 7982456512)>, <MyThread(worker, started 6146437120)>]===================================>################################# # 2 [<_MainThread(MainThread, started 7982456512)>, <MyThread(worker, started 6146437120)>]==================================================>################## # 2 [<_MainThread(MainThread, started 7982456512)>, <MyThread(worker, started 6146437120)>]=================================================================>### # I am finished ~~~============================================================================================================================================> # start() 创建一个系统线程，并把一个未来要执行的函数扔进去，然后启动线程,为线程关联目标函数、因此就是并行的效果; # run() 只是调用了target函数，不会创建新的线程，只是调用了target函数，因此是串行的效果;
- 同时启动多个线程、查看对应交替运行
当使用start()方法启动后，进程内有多个活动的线程并行工作，就是多线程;
一个进程中至少且一个线程，并作为程序的入口，这个线程就是主线程;
一个进程至少有一个主线程;
其他线程称为工作线程;
import threading import time import sys from termcolor import colored class MyThread(threading.Thread): def start(self) -> None: print('start ----') super().start() def run(self) -> None: print('run ----') super().run() def worker(f='green'): print('I am working ~~~') num = 50 for i in range(int(num)): time.sleep(0.2) if i != 20 and f == 'green': print(colored('working...' + '===' * i + '>' + '###' * (int(num) - i - 1),'green'), end='\r') elif i != 20 and f == 'red': print(colored('working...' + '===' * i + '>' + '###' * (int(num) - i - 1),'red'), end='\r') print('I am finished ~~~') t = MyThread(target=worker,name='worker') time.sleep(2) # t.start() 调用 系统调用，创建真正的操作系统的线程，启动运行target函数，且只能start一次，否则报错: RuntimeError: threads can only be started once #t.run() # run是直接调函数，不会创建新的线程，只是调用了target函数 t.start() # start 是创建线程后,并启动线程 t = MyThread(target=worker,name='new_worker',kwargs={'f':'red'}) t.start() x = threading.main_thread() print(type(x).mro()) print(x.name, x.ident, x.is_alive())
daemon
t = threading.Thread(target=worker, name='worker', daemon=True) t.start() #t.setDaemon(threading.main_thread().daemon) time.sleep(3) # daemon=True 守护线程，主线程没有任务退出，守护线程也会退出，就不管子线程的任务是否完成 # daemon=False 主线程退出，子线程还会继续执行 # 除主线程外，回眼看一下子线程的状态，只要有一个non-daemon线程还在运行，主线程就不会退出,但不会管daemon线程是否还在运行 # 主线程会等到最后一个non-daemon线程退出后，再退出，但不会管daemon线程是否还在运行; print(threading.main_thread().daemon,'state') # 主线程的状态 False 主线程是non-daemon线程
| 名称 | 含义 |
|---|---|
daemon |
表示线程是否是daemon线程，这个值必须在 start() 之前设置，否则引发 RuntimeError。 |
isDaemon() |
是否是daemon线程。 |
setDaemon() |
设置为daemon线程，必须在 start() 方法之前设置。 |
线程的 daemon 属性总结
以下是关于线程的 daemon 属性的总结：
- 线程具有一个
daemon属性，可以手动设置为 True 或 False，也可以不设置，此时取默认值 None。 - 如果不设置
daemon属性，那么会取当前线程的daemon属性来设置它。 - 主线程是 non-daemon 线程，即
daemon=False。 - 从主线程创建的所有线程如果不设置
daemon属性，则默认都是daemon=False，即非守护线程。 - 当 Python 程序中没有活跃的非守护线程运行时，程序会退出。换句话说，除了主线程之外，剩下的所有线程都是守护线程，主线程只有等待它们结束后才能退出。
这个特性可以用于控制程序的退出行为，通过合理设置守护线程和非守护线程，可以确保程序在需要时可以正常退出，而不会因为线程未结束而被阻塞。
join()方法
import threading import time import sys from termcolor import colored class MyThread(threading.Thread): def start(self) -> None: print('start ----') super().start() def run(self) -> None: print('run ----') super().run() def worker(f='green'): print('I am working ~~~') num = 50 for i in range(int(num)): time.sleep(0.2) if i != 20 and f == 'green': print(colored('[ working... ]' + '===' * i + '>' + '###' * (int(num) - i - 1),'green'), end='\r') elif i != 20 and f == 'red': print(colored('[ working... ]' + '===' * i + '>' + '###' * (int(num) - i - 1),'red'), end='\r') print('\nI am finished ~~~') x = threading.main_thread() t = threading.Thread(target=worker, name='worker', daemon=True) t.start() print(type(x).mro()) print(x.name, x.ident, x.is_alive()) time.sleep(3) #t.join() # 主线程阻塞态，一直到条件满足，主线程才会继续执行, join 谁 ,join t 就是等待t线程执行完毕，主线程才会继续执行，即阻塞等t线程执行完毕 print('main thread is finished ~~~') # t.join()执行结果 # I am working ~~~ # [<class 'threading._MainThread'>, <class 'threading.Thread'>, <class 'object'>] # MainThread 7982456512 True # [ working... ]===================================================================================================================================================> # I am finished ~~~ # main thread is finished ~~~ # 注释掉t.join()执行结果 # I am working ~~~ # [<class 'threading._MainThread'>, <class 'threading.Thread'>, <class 'object'>] # MainThread 7982456512 True # main thread is finished ~~~==========================>############################################################################################################
线程的 join() 方法总结
join() 方法是线程的标准方法之一，以下是关于 join() 方法的总结：
- 当一个线程调用另一个线程的
join()方法时，调用者线程将被阻塞，直到被调用线程终止，或者等待超时。 - 一个线程可以被多个线程调用其
join()方法，这意味着一个线程可以等待多个其他线程的结束。 timeout参数可以指定调用者等待的时间，如果没有设置超时，调用者将一直等待被调用线程结束。- 调用谁的
join()方法，就是等待谁的结束，即调用者线程将等待被调用线程的结束。
join() 方法常用于控制线程的执行顺序，确保某些线程在其他线程结束后再执行。它可以协调线程之间的执行顺序，避免出现数据竞争等问题。
daemon 线程的应用场景
daemon 线程是一种特殊类型的线程，在某些场景下非常适用。以下是 daemon 线程的主要应用场景：
后台任务：如发送心跳包、监控等后台任务。这种场景下，daemon 线程可以在后台默默地执行任务，不会影响主线程的执行。
主线程工作才有用的线程：有些线程的工作依赖于主线程，如果主线程退出，那么这些线程也就没有存在的必要了。此时可以将这些线程设置为 daemon=True，这样当主线程退出时，这些工作线程也会随之退出。
随时可以被终止的线程：有些线程的工作是随时可以被终止的，不需要等待所有任务完成。这种情况下，可以将这些线程设置为 daemon，以便在主线程退出时一起退出。
daemon 线程的特点是一旦创建就可以忘记它，不需要手动关闭线程，只需要关心主线程的退出即可。这样简化了程序员手动关闭线程的工作，提高了程序的健壮性和可维护性。
Thread-Local
import threading import time import sys from termcolor import colored import logging FORMAT = '%(asctime)s %(threadName)s %(thread)d %(message)s' logging.basicConfig(level=logging.INFO, format=FORMAT) class MyThread(threading.Thread): def start(self) -> None: print('start ----') super().start() def run(self) -> None: print('run ----') super().run() class A(): def __init__(self): self.x = 0 global_data = A() # 那么使用threading.local()创建的对象，每个线程都有自己的数据，互不影响 global_data = threading.local() def worker(f='green'): logging.info('I am working ~~~') num = 50 global_data.x = 0 # x = 0 # x 是局部变量，局部变量和每一次函数调用的栈帧有关，每次调用函数都会创建一个新的栈帧，所以x的值不会受到其他线程的影响 # 如果多个线程运行，使用的都是局部变量，是很安全的 for i in range(int(num)): time.sleep(0.1) global_data.x += 1 if f == 'green': print(colored('[ working... ]' + '===' * i + '>' + '###' * (int(num) - i - 1),'green'), end='\r') elif f == 'red': print(colored('[ working... ]' + '===' * i + '>' + '###' * (int(num) - i - 1),'red'), end='\r') logging.info('\nI am finished ~~~ {} ==> {} '.format(global_data.x, threading.current_thread().name)) for i in range(10): # 判断i 为偶数时，创建线程对象 if i % 2 == 0: t = threading.Thread(target=worker,name='work-{}'.format(i),kwargs={'f':'red'},daemon=False) t.start() else: t = threading.Thread(target=worker,name='work-{}'.format(i),kwargs={'f':'green'},daemon=False) t.start() print('main thread is finished ~~~')
作业
- 用面向对象实现 LinkedList 链表
单向链表
实现方法
append(value): 在链表尾部添加节点iternodes(): 遍历链表，返回所有节点的值
双向链表
实现方法
append(value): 在链表尾部添加节点pop(): 弹出尾部节点insert(value, index): 在指定位置插入节点remove(index): 移除指定位置的节点iternodes(): 遍历链表，返回所有节点的值
提供的特殊方法
__getitem__(index): 获取指定位置节点的值__iter__(): 迭代链表，返回节点的值__setitem__(index, value): 设置指定位置节点的值
- 链表
实现LinkedList链表
链表有单向链表、双向链表
对于链表来说
- 每一个结点是一个独立的对象，结点对象有内容，还知道下一跳是什么。
- 链表则是一个容器，它内部装着一个个结点对象。
所以，建议设计2个类，一个是结点Node类，一个是链表LinkedList类。
如同一个箱子是容器，里面放的小球就是一个个节点。
如同一串珠子，节点对象是一个个珠子，每一颗珠子关联其前后的珠子，所有珠子形成串珠的概念，相当于容器。一串珠子可以从固定一头提起，这是单向链表；如果这串珠子可以从两头中的任意一头提起，这就是双向链表。
- 单向链表
from __future__ import annotations # 使用打补丁的方式，使得Node类可以在定义的时候使用Node类型提示 class Node: def __init__(self,value,next:Node=None): #3.10之后的版本，可以使用Node作为类型提示 self.item = value self.next = next def __repr__(self) -> str: return str(self.item) class LinkedList: # 容器类 def __init__(self): self.head = None self.tail = None def append(self,item): node = Node(item) # empty if self.head is None: self.head = node self.tail = node else: # else not empty self.tail.next = node self.tail = node return self def internodes(self): current:Node = self.head while current: yield current current = current.next ll = LinkedList() ll.append(1).append(2).append(3) for node in ll.internodes(): print(node) # 1 2 3
双向链表
pop方法实现
from __future__ import annotations # 使用打补丁的方式，使得Node类可以在定义的时候使用Node类型提示 # 双向链表 class Node: def __init__(self,value,next:Node=None,prev:Node=None): #3.10之后的版本，可以使用Node作为类型提示 self.item = value self.next = next self.prev = prev def __repr__(self) -> str: return "{} <== {} ==> {}".format( #self.prev,# 注意这个是实例，会导致递归调用 self.prev.item if self.prev else None, self.item, self.next.item if self.next else None ) # def __str__(self) -> str: # return str(self.item) class LinkedList: # 容器类 def __init__(self): self.head = None self.tail = None def append(self,item): # 实现尾部添加 node = Node(item) # empty if self.head is None: #empty self.head = node else: self.tail.next = node node.prev = self.tail # 原来的尾节点 self.tail = node # 更新尾节点 return self # 链式调用 def pop(self): # 实现尾部弹出 if self.head is None: raise Exception('empty') # 不为空 # 假设只有一个元素 node = self.tail if self.head is self.tail: self.head = None self.tail = None else: # 假设有两个元素 prev = node.prev prev.next = None self.tail = prev return node def internodes(self,reverse=False): current:Node = self.head if not reverse else self.tail while current: yield current current = current.next if not reverse else current.prev ll = LinkedList() ll.append(1).append(2).append(3).append('end') ll.pop() for node in ll.internodes(): print(node) # 1 2 3 # None <== 1 ==> 2 # 1 <== 2 ==> 3 # 2 <== 3 ==> None
insert方法
from __future__ import annotations # 使用打补丁的方式，使得Node类可以在定义的时候使用Node类型提示 # 双向链表 class Node: def __init__(self,value,next:Node=None,prev:Node=None): #3.10之后的版本，可以使用Node作为类型提示 self.item = value self.next = next self.prev = prev def __repr__(self) -> str: return "{} <== {} ==> {}".format( #self.prev,# 注意这个是实例，会导致递归调用 self.prev.item if self.prev else None, self.item, self.next.item if self.next else None ) # def __str__(self) -> str: # return str(self.item) class LinkedList: # 容器类 def __init__(self): self.head = None self.tail = None def append(self,item): # 实现尾部添加 node = Node(item) # empty if self.head is None: #empty self.head = node else: self.tail.next = node node.prev = self.tail # 原来的尾节点 self.tail = node # 更新尾节点 return self # 链式调用 def insert(self,index,value): # 指定索引位置插入 if index< 0: raise IndexError('Not negative index {}'.format(index)) current = None for i,node in enumerate(self.internodes()): if index == i: current = node break else: self.append(value) # 尾部插入写完了 return # 说明了什么 ?: index >= 0 and index < length 找到插入点，至少一个元素 # 只有一个元素 node = Node(value) prev = current.prev if index == 0: # 2 头部插入 self.head = node else: # 3 中间插入 node.prev = prev prev.next = node node.next = current current.prev = node def pop(self): # 实现尾部弹出 if self.head is None: raise Exception('empty') # 不为空 # 假设只有一个元素 node = self.tail if self.head is self.tail: self.head = None self.tail = None else: # 假设有两个元素 prev = node.prev prev.next = None self.tail = prev return node def internodes(self,reverse=False): current:Node = self.head if not reverse else self.tail while current: yield current current = current.next if not reverse else current.prev ll = LinkedList() ll.append(1).append(2) ll.append(3).append('end') for node in ll.internodes(True): print(node) # 1 2 3 print('-----------') ll.pop() ll.pop() for node in ll.internodes(True): print(node) ll.insert(0,'start') ll.insert(3,'end') ll.insert(3,3) print('-----------') for node in ll.internodes(): print(node) # 1 2 3 # 3 <== end ==> None # 2 <== 3 ==> end # 1 <== 2 ==> 3 # None <== 1 ==> 2 # ----------- # 1 <== 2 ==> None # None <== 1 ==> 2 # ----------- # None <== start ==> 1 # start <== 1 ==> 2 # 1 <== 2 ==> 3 # 2 <== 3 ==> end # 3 <== end ==> None
remove方法
from __future__ import annotations # 使用打补丁的方式，使得Node类可以在定义的时候使用Node类型提示 # 双向链表 class Node: def __init__(self,value,next:Node=None,prev:Node=None): #3.10之后的版本，可以使用Node作为类型提示 self.item = value self.next = next self.prev = prev def __repr__(self) -> str: return "{} <== {} ==> {}".format( #self.prev,# 注意这个是实例，会导致递归调用 self.prev.item if self.prev else None, self.item, self.next.item if self.next else None ) # def __str__(self) -> str: # return str(self.item) class LinkedList: # 容器类 def __init__(self): self.head = None self.tail = None def append(self,item): # 实现尾部添加 node = Node(item) # empty if self.head is None: #empty self.head = node else: self.tail.next = node node.prev = self.tail # 原来的尾节点 self.tail = node # 更新尾节点 return self # 链式调用 def insert(self,index,value): # 指定索引位置插入 if index< 0: raise IndexError('Not negative index {}'.format(index)) current = None for i,node in enumerate(self.internodes()): if index == i: current = node break else: self.append(value) # 尾部插入写完了 return # 说明了什么 ?: index >= 0 and index < length 找到插入点，至少一个元素 # 只有一个元素 node = Node(value) prev = current.prev if index == 0: # 2 头部插入 self.head = node else: # 3 中间插入 node.prev = prev prev.next = node node.next = current current.prev = node def pop(self): # 实现尾部弹出 if self.head is None: raise Exception('empty') # 不为空 # 假设只有一个元素 node = self.tail if self.head is self.tail: self.head = None self.tail = None else: # 假设有两个元素 prev = node.prev prev.next = None self.tail = prev return node def remove(self,index): # 删除指定索引位置的元素 if self.head is None: raise Exception('empty') if index < 0: raise IndexError('Not negative index {}'.format(index)) current = None for i , node in enumerate(self.internodes()): if index == i: current = node break else: # 没有找到,该追加了 raise IndexError('Index out of range:{}'.format(index)) # 找到了 prev = current.prev next = current.next if self.head is self.tail: # only one element self.head = None self.tail = None elif prev is None: # 不止一个元素, 或者current is self.head self.head = next next.prev = None elif next is None: #不止一个元素, 移除末尾 self.tail = prev prev.next = None else:# 不止一个元素，中能是中间 prev.next = next next.prev = prev del current # 释放内存,回收垃圾 def internodes(self,reverse=False): current:Node = self.head if not reverse else self.tail while current: yield current current = current.next if not reverse else current.prev ll = LinkedList() ll.append(1).append(2) ll.append(3).append('end') for node in ll.internodes(True): print(node) # print('-----------') ll.pop() ll.pop() for node in ll.internodes(True): print(node) ll.insert(0,'start') ll.insert(3,'end') ll.insert(3,3) print('-----------') for node in ll.internodes(): print(node) # print('============') ll.remove(4) ll.remove(0) for node in ll.internodes(): print(node)
- 开始完善容器功能
from __future__ import annotations # 使用打补丁的方式，使得Node类可以在定义的时候使用Node类型提示 # 双向链表 class Node: def __init__(self,value,next:Node=None,prev:Node=None): #3.10之后的版本，可以使用Node作为类型提示 self.item = value self.next = next self.prev = prev def __repr__(self) -> str: return "{} <== {} ==> {}".format( #self.prev,# 注意这个是实例，会导致递归调用 self.prev.item if self.prev else None, self.item, self.next.item if self.next else None ) # def __str__(self) -> str: # return str(self.item) class LinkedList: # 容器类 def __init__(self): self.head = None self.tail = None self._size = 0 # 用于记录链表的长度 size = property(lambda self: self._size) # 只读属性, 重写size方法 def __len__(self): return self.size # 重写len方法 def append(self,item): # 实现尾部添加 node = Node(item) # empty if self.head is None: #empty self.head = node else: self.tail.next = node node.prev = self.tail # 原来的尾节点 self.tail = node # 更新尾节点 self._size += 1 return self # 链式调用 def insert(self,index,value): # 指定索引位置插入 # if index< 0: # raise IndexError('Not negative index {}'.format(index)) # current = None # for i,node in enumerate(self.internodes()): # if index == i: # current = node # break # else: # self.append(value) # 尾部插入写完了 # return if index >= len(self): self.append(value) return if index < -len(self): index = 0 current = self[index] # 1. 重写__getitem__方法 # 说明了什么 ?: index >= 0 and index < length 找到插入点，至少一个元素 # 只有一个元素 node = Node(value) prev = current.prev if index == 0: # 2 头部插入 self.head = node else: # 3 中间插入 node.prev = prev prev.next = node node.next = current current.prev = node self._size += 1 def pop(self): # 实现尾部弹出 if self.head is None: raise Exception('empty') # 不为空 # 假设只有一个元素 node = self.tail if self.head is self.tail: self.head = None self.tail = None else: # 假设有两个元素 prev = node.prev prev.next = None self.tail = prev self._size -= 1 return node def remove(self,index): # 删除指定索引位置的元素 if self.head is None: raise Exception('empty') # if index < 0: # raise IndexError('Not negative index {}'.format(index)) # current = None # for i , node in enumerate(self.internodes()): # if index == i: # current = node # break # else: # 没有找到,该追加了 # raise IndexError('Index out of range:{}'.format(index)) current = self[index] # 找到了 prev = current.prev next = current.next if self.head is self.tail: # only one element self.head = None self.tail = None elif prev is None: # 不止一个元素, 或者current is self.head self.head = next next.prev = None elif next is None: #不止一个元素, 移除末尾 self.tail = prev prev.next = None else:# 不止一个元素，中能是中间 prev.next = next next.prev = prev self._size -= 1 del current # 释放内存,回收垃圾 def internodes(self,reverse=False): current:Node = self.head if not reverse else self.tail while current: yield current current = current.next if not reverse else current.prev # def __iter__(self): # yield from self.internodes() # # return self.internodes() __iter__ = internodes # 重写__iter__方法， 等价于上面的代码 def __reversed__(self): # 1. 实现该方术方法，reversed 优先使用 # 2. 如果没有实现该方法，那么使用__len__ __getitem__方法 return self.internodes(reverse=True) def __getitem__(self,index): if index >= len(self) or index < -len(self): raise IndexError('Index out of range: {}'.format(index)) # if index >= 0: # for i ,node in enumerate(self.internodes(False),0): # if index == i: # return node # if index < 0: # for i ,node in enumerate(self.internodes(True),1): # if -index == i: # return node # 开始简化以上判断 reverse = False if index >= 0 else True start = 0 if index >= 0 else 1 for i,node in enumerate(self.internodes(reverse),start): if abs(index) == i: return node def __setitem__(self,index,value): self[index].item =value ll = LinkedList() ll.append(0).append(1).append(2) ll.append(3).append('end') ll[-1] = 'end2' for i in range(5): print(ll[i]) print('-'* 30 ) for i in range(-1,-6,-1): print(ll[i])
