线性表

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

  • 前驱元素:若$A$元素在$B$元素的前面,则称$A$为$B$的前驱元素
  • 后继元素:若$B$元素在$A$元素的后面,则称$B$为$A$的后继元素
线性表的特征

数据元素之间具有一种一对一的逻辑关系

  1. 第一个数据元素没有前驱,这个数据元素被称为头结点
  2. 最后一个数据元素没有后继,这个数据元素被称为尾结点
  3. 除了第一个和最后一个数据元素外,其他数据元素有且仅有一个前驱和一个后继

如果把线性表用数学语言来定义,则可以表示为$a1,...,ai-1,ai,ai+1,...,an$,$ai-1$领先于$ai$,$ai$领先于$ai+1$,称$ai-1$是$ai$的前驱元素,$ai+1$是$ai$的后继元素

graph LR
        a1-->a2
        a2-.-ai-1
        ai-1-->ai
        ai-->ai+1
        ai+1-.-an-1
        an-1-->an
线性表的分类

线性表中数据存储的方式可以是顺序存储,也可以是链式存储,按照数据的存储方式不同,可以把线性表分为顺序表和链表

顺序表

顺序表是在计算机内存中以数组的形式保存的线性表,线性表的顺序存储是指用一组地址连续的存储单元,依次存储线性表中的各个单元,使得线性表中在逻辑结构上相应的数据元素存储在相邻的物理存储单元中,即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系

顺序表的实现

顺序表API设计
类名SequenceList``
构造方法SequenceList(int capacity):创建容量为capacity的SequenceList对象
成员方法1.public void clear():空置线性表 2.public boolean isEmpty():判断线性表是否为空,是返回true,否则返回false 3.public int length():获取线性表中元素的个数 4.public T get(int i):读取并返回线性表中的第i个元素的值 5.public void insert(int i,T t):在线性表的第i个元素之前插入一个值为t的数据元素 6.public void insert(T t):向线性表中添加一个元素 7.public T remove(int i):删除并返回线性表中 8.public int indexOf(T t):返回线性表中首次出现的指定的数据元素的位序号,若不存在,则返回-1
成员变量1.orivate T[] eles:存储元素的数组 2.private int N:当前线性表的长度
顺序表代码

SequenceList

public class SequenceList<T> {

  /**
   * 存储元素的数组
   */
  private T[] eles;

  /**
   * 记录当前顺序表中的元素个数
   */
  private int N;

  /**
   * 构造方法
   */
  public SequenceList(int capacity) {
    //初始化数组
    this.eles = (T[]) new Object[capacity];
    //初始化长度
    this.N = 0;

  }

  /**
   * 将一个线性表置为空表
   */
  public void clear() {
    this.N = 0;
  }

  /**
   * 判断当前线性表是否为空表
   */
  public boolean isEmpty() {
    return N == 0;
  }

  /**
   * 获取线性表的长度
   */
  public int length() {
    return N;
  }

  /**
   * 获取指定位置的元素
   */
  public T get(int i) {
    return eles[i];
  }

  /**
   * 向线性表中添加元素t
   */
  public void insert(T t) {
    eles[N++] = t;
  }

  /**
   * 在i元素处插入元素t
   */
  public void insert(int i, T t) {
    //元素个数加1
    this.N++;
    //先把i索引处的元素及其后面的元素依次向后移动一位
    for (int index = N - 1; index > i; index--) {
      eles[index] = eles[index - 1];
    }
    //再把t元素放到位置i即可,这时候需要考虑如果插入的数的位置是原数组最后一个,则直接else[N++]=t;
    if (i == N - 2) {
      eles[i + 1] = t;
    } else {
      eles[i] = t;
    }
  }

  /**
   * 删除指定位置i处的元素,并返回该元素
   */
  public T remove(int i) {
    //记录索引i处的值
    T current = eles[i];
    //让索引i后面元素依次向前移动一位
    for (int index = i; index < N - 1; index++) {
      eles[index] = eles[index + 1];
    }
    //元素个数减1
    this.N--;
    return current;
  }

  /**
   * 查找t元素第一次出现的位置
   */
  public int indexOf(T t) {
    for (int index = 0; index < N; index++) {
      if (eles[index] == t) {
        return index;
      }
    }
    return -1;
  }
}

SequenceListTest

public static void main(String[] args) {
    //创建顺序表对象
    SequenceList<String> sl = new SequenceList<>(10);
    //测试插入
    sl.insert("猪肚鸡");
    sl.insert("蛋包饭");
    sl.insert("乌冬面");
    sl.insert(2, "白切鸡");
    sl.insert(4, "寿司");
    //测试获取数据
    String getResult = sl.get(1);
    System.out.println("第一个数据为索引1的:" + getResult);
    System.out.println(sl.get(4));
    //测试删除
    String removeResult = sl.remove(0);
    System.out.println("删除的元素为:+" + removeResult);
    //测试清空
    sl.clear();
    System.out.println("现在顺序表中的元素个数为:" + sl.length());
  }
顺序表的遍历

一般作为容器存储数据,都需要向外部提供遍历的方式,因此我们需要给顺序表提供遍历方式,在$java$中遍历集合的方式一般都是使用的是$foreach$循环,如果想让我们的SequenceList也能支持$foreach$循环,则需要做如下操作

  1. 让SequenceList实现$Iterable$接口,重写$iterable$方法
  2. 在SequenceList内部提供一个内部类$SIterator$,实现$Iteratot$接口,重写$hasNext$方法和$next$方法

代码:

SequenceList

public class SequenceList<T> implements Iterable<T> {

  /**
   * 存储元素的数组
   */
  private T[] eles;

  /**
   * 记录当前顺序表中的元素个数
   */
  private int N;

  /**
   * 构造方法
   */
  public SequenceList(int capacity) {
    //初始化数组
    this.eles = (T[]) new Object[capacity];
    //初始化长度
    this.N = 0;

  }

  /**
   * 将一个线性表置为空表
   */
  public void clear() {
    this.N = 0;
  }

  /**
   * 判断当前线性表是否为空表
   */
  public boolean isEmpty() {
    return N == 0;
  }

  /**
   * 获取线性表的长度
   */
  public int length() {
    return N;
  }

  /**
   * 获取指定位置的元素
   */
  public T get(int i) {
    return eles[i];
  }

  /**
   * 向线性表中添加元素t
   */
  public void insert(T t) {
    eles[N++] = t;
  }

  /**
   * 在i元素处插入元素t
   */
  public void insert(int i, T t) {
    //元素个数加1
    this.N++;
    //先把i索引处的元素及其后面的元素依次向后移动一位
    for (int index = N - 1; index > i; index--) {
      eles[index] = eles[index - 1];
    }
    //再把t元素放到位置i即可,这时候需要考虑如果插入的数的位置是原数组最后一个,则直接else[N++]=t;
    if (i == N - 2) {
      eles[i + 1] = t;
    } else {
      eles[i] = t;
    }
  }

  /**
   * 删除指定位置i处的元素,并返回该元素
   */
  public T remove(int i) {
    //记录索引i处的值
    T current = eles[i];
    //让索引i后面元素依次向前移动一位
    for (int index = i; index < N - 1; index++) {
      eles[index] = eles[index + 1];
    }
    //元素个数减1
    this.N--;
    return current;
  }

  /**
   * 查找t元素第一次出现的位置
   */
  public int indexOf(T t) {
    for (int index = 0; index < N; index++) {
      if (eles[index] == t) {
        return index;
      }
    }
    return -1;
  }

  @Override
  public Iterator<T> iterator() {
    return new SIterator();
  }

  private class SIterator implements Iterator {

    private int cusor;

    public SIterator() {
      this.cusor = 0;
    }

    @Override
    public boolean hasNext() {
      return cusor <= N - 1;
    }

    @Override
    public Object next() {
      return eles[cusor++];
    }
  }
}

SequenceListTest

public static void main(String[] args) {
    //创建顺序表对象
    SequenceList<String> sl = new SequenceList<>(10);
    //测试插入
    sl.insert("猪肚鸡");
    sl.insert("蛋包饭");
    sl.insert("乌冬面");
    sl.insert(2, "白切鸡");
    sl.insert(4, "寿司");
    for (String s : sl) {
      System.out.println(s);
    }
    System.out.println("----------------------------");
    //测试获取数据
    String getResult = sl.get(1);
    System.out.println("第一个数据为索引1的:" + getResult);
    System.out.println(sl.get(4));
    //测试删除
    String removeResult = sl.remove(0);
    System.out.println("删除的元素为:+" + removeResult);
    //测试清空
    sl.clear();
    System.out.println("现在顺序表中的元素个数为:" + sl.length());
  }
顺序表的容量可变

在之前的实现中,当我们使用SequenceList时,先使用new SequenceList(5)创建一个对象,创建对象时就需要指定容器的大小,初始化指定大小的数组来存储元素,当我们插入元素时,如果已经插入了5个元素,还要继续插入数据,则会报错,就不能插入了,这种设计不符合容器的设计理念,因为我们在实际项目当中,顺序表长度一定会是边长变短的,而不是只是永远固定的,所以我们在设计顺序表时候,就应该考虑它的容量的伸缩性

例:在数组容量范围内,正常无报错

  public static void main(String[] args) {
    SequenceList<String> sl = new SequenceList<>(3);
    sl.insert("上海");
    sl.insert("东京");
    sl.insert("纽约");
  }

当超过数组长度时,报出越界报错

public static void main(String[] args) {
    SequenceList<String> sl = new SequenceList<>(3);
    sl.insert("上海");
    sl.insert("东京");
    sl.insert("纽约");
    sl.insert("巴黎");
  }

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 3
    at linear.SequenceList.insert(SequenceList.java:67)
    at linear.SequenceListTest2.main(SequenceListTest2.java:14)

考虑容器的容量伸缩性,其实就是改变存储数据元素的数组的大小,要分为两种情况

  1. 添加元素时,应该增长数组长度

添加元素时,应该检查当前数组的大小是否能够容纳新的元素,如果不能容纳,则需要创建新的容量更大的数组,我们这里创建一个是原数组两倍容量的新数组存储元素

  1. 移除元素,对数组进行缩小

移除元素时,应该检查当前数组的大小是否太大,比如正在用$100$个容量的数组存储$10$个元素,这样就会造成内存空间的浪费,应当创建一个容量更小的数组存储元素,如果我们发现数据元素的数量不足数组容量的$\frac{1}{4}$,则创建一个原数组容量的$\frac{1}{2}$的新数组存储元素

容量变换代码实现
/**
   * 根据newSize,重置数组eles的长度大小
   */
  public void resize(int newSize) {
    //定义一个临时数组,指向原数组
    T[] temp = eles;
    //创建新数组
    eles = (T[]) new Object[newSize];
    //把原数组的数据拷贝到新数组即可
    for (int i = 0; i < N; i++) {
      eles[i] = temp[i];
    }
  }

///////////////////////

  public void insert(T t) {
    //扩大数组
    if (N == eles.length) {
      resize(N * 2);
    }
    eles[N++] = t;
  }

  /**
   * 在i元素处插入元素t
   */
  public void insert(int i, T t) {
    //扩大数组
    if (N == eles.length) {
      resize(N * 2);
    }
    //元素个数加1
    this.N++;
    //先把i索引处的元素及其后面的元素依次向后移动一位
    for (int index = N - 1; index > i; index--) {
      eles[index] = eles[index - 1];
    }
    //再把t元素放到位置i即可,这时候需要考虑如果插入的数的位置是原数组最后一个,则直接else[N++]=t;
    if (i == N - 2) {
      eles[i + 1] = t;
    } else {
      eles[i] = t;
    }
  }

/////////////////////////

  /**
   * 删除指定位置i处的元素,并返回该元素
   */
  public T remove(int i) {
    //记录索引i处的值
    T current = eles[i];
    //让索引i后面元素依次向前移动一位
    for (int index = i; index < N - 1; index++) {
      eles[index] = eles[index + 1];
    }
    //元素个数减1
    this.N--;

    //缩小数组
    if (N < eles.length / 4) {
      resize(eles.length / 2);
    }
    return current;
  }
顺序表的时间复杂度

get(i)

/**
   * 获取指定位置的元素
   */
  public T get(int i) {
    return eles[i];
  }

不难看出,无论数据元素量$N$有多大,只需要一次eles[i]就可以获取到对应的元素,所以时间复杂度为$O(1)$

insert(int i, T t)

/**
   * 在i元素处插入元素t
   */
  public void insert(int i, T t) {
    //扩大数组
    if (N == eles.length) {
      resize(N * 2);
    }
    //元素个数加1
    this.N++;
    //先把i索引处的元素及其后面的元素依次向后移动一位
    for (int index = N - 1; index > i; index--) {
      eles[index] = eles[index - 1];
    }
    //再把t元素放到位置i即可,这时候需要考虑如果插入的数的位置是原数组最后一个,则直接else[N++]=t;
    if (i == N - 2) {
      eles[i + 1] = t;
    } else {
      eles[i] = t;
    }
  }

每一次插入,都需要把$i$位置后面的元素移动一次,随着元素数量$N$的增大,移动的元素也越来越多,时间复杂度为$O(n)$

remove(int i)

/**
   * 删除指定位置i处的元素,并返回该元素
   */
  public T remove(int i) {
    //记录索引i处的值
    T current = eles[i];
    //让索引i后面元素依次向前移动一位
    for (int index = i; index < N - 1; index++) {
      eles[index] = eles[index + 1];
    }
    //元素个数减1
    this.N--;

    //缩小数组
    if (N < eles.length / 4) {
      resize(eles.length / 2);
    }
    return current;
  }

每一次删除,都需要把$i$位置后面的元素移动一次,随着数据量$N$的增大,移动的元素也越来越多,时间复杂度为$O(n)$

由于顺序表的底层是由数组实现的,数组的长度是固定的,所以在操作的过程中涉及到了容器扩容操作,这样就会导致顺序表在使用过程中的时间复杂度不是线性的,在某些需要扩容的节点处,耗时会突增,尤其是元素越多,这个问题越明显

java中ArrayList实现

java中ArrayList集合的底层也是一种顺序表,使用数组实现,同样提供了增删改查以及扩容等功能

Last modification：April 12, 2021
© Allow specification reprint
If you think my article is useful to you, please feel free to appreciate