NON-CONTIGUOUS MEMORY & POINTER DYNAMICS
上一节的“数组”是买下一整排连续的太空港。但如果内存碎片化,没有一大块空地怎么办?链表应运而生。
每个数据(能量舱)可以随机散落在宇宙的任何角落,只要每个舱室携带一个发射器(Pointer / 指针),指向下一个舱室的物理坐标(内存地址)即可。
优势:插入和删除极快(O(1)),只需改变激光指针的朝向,不用任何人搬家。
劣势:想要找到第 N 个人?对不起,你只能从 HEAD (锚点) 出发,顺藤摸瓜一个一个找过去(O(N))。
* 插入动作本身 O(1),但寻址到该位置需 O(N)