数据结构学习笔记:数组与链表的区别

时间:2022-07-29 19:26:16
  • 数组中的元素在内存中连续存放,可以通过下标快速访问元素。
    链表中的元素不是顺序存储的,通过指针相连。

  • 数组从中分配空间,方便快速但*度小
    链表从中分配空间,*度高但申请和管理比较麻烦

  • 数组访问元素时间为O(1),但插入和删除元素都要移动大量元素,时间为O(n)
    链表访问元素需要通过指针寻找,时间为O(n),但删除和插入元素只需更改指针指向,时间为O(1)

  • 数组必须事先定义固定的长度(元素个数),不能适应数据动态地增减的情况。
    链表动态地进行存储分配,可以适应数据动态地增减的情况,且可以方便地插入、删除数据项。