跳到主要内容

线性表 (Linear List)

也称顺序表 (Sequential List)或有序表 (Ordered List)。它是元素的一个有序集合，其长度有限，并且可以根据需要自动伸缩。其形式如下：

Ln={e0,e1,…,en−1}L_{n} = \{e_0, e_1,\dots,e_{n-1}\}

其中 nn 是有穷自然数，eie_i 是线性表中的一个元素，ii 是元素的索引，索引从 0 开始，nn 是线性表的长度或大小。当 n=0n=0 时，线性表为空。en−1e_{n-1} 是线性表的最后一个元素1。

线性表中的顺序通常是指数据添加的顺序，并非按照元素大小的顺序存储。

按照元素大小顺序存储的线性表称为排序列表 (Sorted List) ，它是一个始终保持其元素按指定顺序排列的列表。元素的顺序可以基于自然顺序（如数字的升序或降序）或自定义比较规则（如字符串的字典序）。它是线性表的一种，其实现也会在后文中讲述。

抽象数据类型（ADT）​

ADT LinearList {
属性
    elements; // 有限个元素的有序集合
操作
    size();
    isEmpty();
    get(int index);
    ... // 更多操作见下文
}

线性表的操作​

在 Java 中对应的接口为 java.util.List，其主要的一些方法说明如下：

  • size：返回线性表的长度
  • isEmpty：判断线性表是否为空
  • contains(Object e)：判断一个元素是否在顺序表中
  • get(int index)：获取指定位置的元素
  • add(T e)：添加元素
  • add(int index, T e)：添加元素到指定位置，此为止的元素后移
  • remove(T e)：删除元素
  • remove(int index)：删除指定位置元素，其后元素前移
  • indexOf(Object o)：获取元素的所在位置
  • iterator：生成序列表的迭代器，用于元素遍历

参考资料​

  1. Sartaj Sahni. 数据结构、算法与应用：C++语言描述.（第二版）. （王立柱,刘志红译）. 北京：机械工业出版社. 2015. ISBN 978-7-111-49600-7 ↩