比较顺序表和链表的优缺点
程序员文章站
2023-12-26 07:58:15
比较顺序表和链表的优缺点
线性表分为顺序表和链表,链表又分为单链表,双向链表和循环链表。对于链表的结构又分为带头链表和不带头链表。
一,顺序表
定义:将表中元素一个接一个的存入一组连续的存储单元中,...
比较顺序表和链表的优缺点
线性表分为顺序表和链表,链表又分为单链表,双向链表和循环链表。对于链表的结构又分为带头链表和不带头链表。
一,顺序表
定义:将表中元素一个接一个的存入一组连续的存储单元中,这种存储结构是顺序结构。采用顺序存储结构的线性表简称为“ 顺序表”。
特点:1.存储空间连续,即允许元素的随机访问
2.长度固定,必须在分配内存之前确定数组的长度
优点:1.便于随机访问
2.cpu缓存利用率高
缺点:不便于插入删除等操作,因为插入删除一个元素需要移动其后的所有元素。但是在末尾插入或删除数据比较方便。
适用情况:一般尾插,尾删多的用顺序表和需要大量访问元素的 而少量增添/删除元素的程序。
二,链表
单链表是只包含指向下一个节点的指针,只能单向遍历。
双链表即包含指向下一个节点的指针,也包含指向前一个节点的指针,因此可以双向遍历。
循环单链表则是将尾节点与首节点链接起来,形成了一个环状结构
特点:1.长度不固定,可以随意增删改
2.存储空间不连续,数据元素之间靠指针联系
3. 不支持随机查找
4. 在特定的数据元素之后插入或删除元素,不涉及到其他元素的移动
适用情况:适用于需要进行大量增添/删除元素操作 而对访问元素无要求的程序