链表课堂笔记

链表课堂笔记链表用一组任意的存储单元存放数据可以是连续也可以是不连续。每个结点包含数据域存数据指针域存下一个结点的位置。单链表每个结点只有一个指向后继的指针双链表有两个指针分别指向前驱和后继。Python里用LinkNode类实现结点包含data属性和next属性头结点用head引用。链表和数组的优缺点相反。链表是不连续空间增加删除方便只需要改指针指向但查找很难得从头遍历。数组是连续空间通过下标能快速访问但增删元素需要移动大量数据。所以链表适合频繁增删的场景数组适合频繁访问的场景。移除链表元素需要遍历链表找到等于目标值的结点就跳过它让前一个结点的next指向它的下一个。注意处理头结点就是要删除的情况可以用虚拟头节点来统一操作避免单独处理头结点。设计链表包含获取指定位置的值、头部插入、尾部插入、指定位置插入和删除操作。关键是找对插入位置的前一个结点。插入和删除时注意边界条件比如插入位置为0时直接在头部操作删除位置为0时移动头结点。操作过程中要正确更新结点的next指向避免链表断裂。课后练习力扣203