数据结构： 线性表中线性表与链表的区别

Love The Way You Lie 2023-02-13 08:57 21阅读 0赞

#

  1. 线性表与单链表的区别

在这里插入图片描述

结论：

使用到的线性表需要频繁查找时，使用线性表结构；
频繁插入和删除是，采用单链表结构

补充说明：

线性表的元素地址是连续的。
链表里的地址是不连续的，是通过指针联系起来的。

PS：线性表是逻辑结构，各个元素存储的先后位置反映逻辑上的线性关系。
单链表是线性结构，是靠指针来反映这种关系的。
线性表中各存储类型的区分

2##

2.1 顺序存储：

顺序表，使用数组实现，是一组连续的存储单元，数组的大小有静态分配与动态扩展两种方式。 值得注意的是线性表是从1开始，而数组是从0开始。

优点：随机访问特性，查找O(1)时间，存储密度高；逻辑上相邻的元素，物理上也相邻；

缺点：插入删除需移动大量元素。

顺序表相关的操作跟数组有关，一般都是移动数组元素。

2.2 单链表

使用任意存储单元来存储线性表中的数据元素，节点类型如上。

单链表分为带头结点和不带头结点两种，不管有没有头结点，头指针都指向链表的第一个节点（有头结点指向头结点）。

头结点：数值域可不设任何信息，头结点的指针域指向链表的第一个元素。

带头节点的好处有：

（1）链表第一位置节点上的操作和其它位置上的操作一致

（2）无论链表是否为空，头指针都指向头结点（非空），空表和非空表处理一样

注：链表麻烦的地方是插入和删除时指针的修改，保证不断链，一般先断后链。

发表评论

表情：
评论列表 （有 0 条评论，21人围观）

还没有评论，来说两句吧...

相关阅读