数据结构-线性表

数据结构-线性表

定义

线性表是最基本、最简单、也是最常用的一种数据结构。线性表(linear list)是数据结构的一种,一个线性表是n个具有相同特性的数据元素的有限序列。

线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的(注意,这句话只适用大部分线性表,而不是全部。比如,循环链表逻辑层次上也是一种线性表(存储层次上属于链式存储,但是把最后一个数据元素的尾指针指向了首位结点)。

特征

  1. 集合中必存在唯一的一个“第一元素”。
  2. 集合中必存在唯一的一个 “最后元素” 。
  3. 除最后一个元素之外,均有唯一的后继(后件)。
  4. 除第一个元素之外,均有唯一的前驱(前件)。

存储方式与优缺点

  1. 顺序存储(顺序表)
    优点:
    1.空间利用率高
    2.存取速度快
    缺点:
    1.插入删除操作较慢
    2.初始要定义长度,可能溢出
  2. 链式存储(链表)
    优点:
    1.插入删除操作较快
    2.没有空间限制
    缺点:
    1.空间消耗多
    2.存取速度慢

基本操作

  1. 求当前元素个数
  2. 插入
  3. 删除
  4. 查找
  5. 判断是否为空
---本文结束,感谢阅读---