比较顺序表和链表的优缺点

比较顺序表和链表的优缺点

线性表分为顺序表和链表，链表又分为单链表，双向链表和循环链表。对于链表的结构又分为带头链表和不带头链表。

一，顺序表

定义：将表中元素一个接一个的存入一组连续的存储单元中，这种存储结构是顺序结构。采用顺序存储结构的线性表简称为“ 顺序表”。

特点：1.存储空间连续，即允许元素的随机访问

2.长度固定，必须在分配内存之前确定数组的长度

优点：1.便于随机访问

2.cpu缓存利用率高

缺点：不便于插入删除等操作，因为插入删除一个元素需要移动其后的所有元素。但是在末尾插入或删除数据比较方便。

适用情况：一般尾插，尾删多的用顺序表和需要大量访问元素的 而少量增添/删除元素的程序。

二，链表

单链表是只包含指向下一个节点的指针，只能单向遍历。

双链表即包含指向下一个节点的指针，也包含指向前一个节点的指针，因此可以双向遍历。

循环单链表则是将尾节点与首节点链接起来，形成了一个环状结构

特点：1.长度不固定，可以随意增删改

2.存储空间不连续，数据元素之间靠指针联系

3. 不支持随机查找

4. 在特定的数据元素之后插入或删除元素，不涉及到其他元素的移动

适用情况：适用于需要进行大量增添/删除元素操作 而对访问元素无要求的程序