链式存储结构

什么是链式存储结构

• 元素在物理内存上的分配是随机的（可以是连续的，也可以是不连续的）。
• 每一个存储单元分为两部分数据域（Object）和指针域（引用）。

链式存储结构的特点

• 查找：由于元素之间是不连续的，所以只能从头节点通过指针进行元素的查找，时间复杂度为O(n)。
• 修改：修改和查找一样，找到直接替换即可，时间复杂度为O(n)。
• 插入：元素的插入只需要断开插入位置的指针，并将插入位置的前元素的指针域指向新加入的元素，将新加入的元素的指针指向插入位置前元素的指针所指向的元素即可，时间复杂度为O(1)。
• 删除：和插入的情况相同。 链式存储结构可用于插入和删除比较多的情况，查找或修改比较多时可以使用链式存储结构。