（二）线性表 ---→ 顺序表

文章目录

定义
分类
特点
java代码实现

定义

摘抄自维基百科

顺序表 是在计算机内存中以数组的形式保存的 线性表，是指用一组地址连续的存储单元依次存储数据元素的线性结构。

分类

在数据结构分类中，属于 逻辑上的线性结构，物理上的顺序存储结构 分支下。

特点

底层实现是利用数组，数组名代表首地址，通过计算每个元素占用的字节数，乘以角标，可以快速的算出角标为 index 的元素的内存地址。因此，对于顺序存储结构来说，存取操作的时间复杂度为 O(1) 。

对于线性表的有序特点，顺序表的实现很鸡贼，它底层使用的数组，数组本身就是在内存中开辟一片连续的空间，因此，放在其中的元素就是在这一片连续的内存中，所以必然有序。还获得了一种无敌的能力：随机访问能力。

鸡贼的实现有序，代价也是有的，在删除和插入的时候，为了维护有序的特点，而底层是连续的一大片空间，在中间进行插入、删除，需要移动大量的元素。**
优点：

存、取的复复杂度都是 O(1)
不需要额外空间去维护前后元素的关系

缺点：

插入、删除的复杂度都是 O(n)
表中元素个数变化较大的时候，造成空间的不确定性，浪费空间

java代码实现

java代码实现

/*
 * listEmpty() 判断线性表是否为空，为空返回 true ，否则返回 false
 * clearList()将线性表清空，置为空表
 * getElem(index)返回线性表中的第 index+1 元素
 * setElem(index,elem) 设置线性表中角标为 index 的元素为 elem
 * getElemIndex(elem) 返回线性表中元素 elem 的下标 index ，返回 -1 代表线性表中没有该元素。
 * insertElem(int index,elem) 在线性表的 index 下标处，插入元素 elem
 * delete(index) 删除并返回线性表中下标为 index 的元素
 * length() 返回线性表的长度
 * size() 返回线性表中元素的个数
 */

import java.util.Arrays;

/**
 * @author Yaz
 * @date 2019-07-11 7:41
 **/
@SuppressWarnings("unused")
public class ArrayList<T> {
    private int size = 0;
    private int length = 0;
    private T[] arrayList;


    public ArrayList() {
//        底层构造泛型数组，初始容量为10
        arrayList = (T[]) new Object[10];
        length = 10;
    }

    public ArrayList(int length) {
        arrayList = (T[]) new Object[length];
        this.length = length;
    }

    public boolean listEmpty() {
        return size == 0;
    }

    public void clearList() {
        size = 0 ;
        arrayList = null;
    }

    public T getElem(int index) {
        checkIndex(index,false);
        return arrayList[index];
    }


    public T setElem(int index, T elem) {
        checkIndex(index,false);
        T temp = arrayList[index];
        arrayList[index] = elem;
        return temp;
    }

    public int getElemIndex(T elem) {
        for (int i = 0; i < size; i++) {
            if (arrayList[i] == elem || arrayList[i].equals(elem)) {
                return i;
            }
        }
        return -1;
    }

    public void insertElem(int index, T elem) {
        checkIndex(index,true);
        ensureCapacity();
        for (int i = size - 1; i >= index; i--) {
            arrayList[i + 1] = arrayList[i];
        }
        arrayList[index] = elem;
        size++;

    }

    public T delete(int index) {
        checkIndex(index,false);
        T temp = arrayList[index];
        for (int i = index; i < size - 1; i++) {
            arrayList[i] = arrayList[i + 1];
        }
        arrayList[size--] = null;
        return temp;
    }

    public int getLength() {
        return length;
    }

    public int getSize() {
        return size;
    }

    private void checkIndex(int index, boolean isInsert) {
        if (isInsert) {
            if (index < 0 || index > size) {
                throw new RuntimeException("下标越界，下标合法范围：0-" + size);
            }
        }else {
            if (index < 0 || index >= size) {
                throw new RuntimeException("下标越界，下标合法范围：0-" + (size - 1));
            }
        }
    }

    private void ensureCapacity() {
        if (size == length) {
            length *= 2;
            arrayList = Arrays.copyOf(arrayList, length);
        }
    }
}

junit 测试代码

import org.junit.Before;
import org.junit.Test;

import static org.hamcrest.Matchers.is;
import static org.junit.Assert.*;


/**
 * @author Yaz
 * @Description
 * @create 2019-07-11 23:09
 **/
public class ArrayListTest {

    private ArrayList<String> arrayList;


    @Before
    public void setUp() {
        arrayList = new ArrayList<>();
    }

    @Test
    public void listEmpty() {
        assertTrue(arrayList.listEmpty());
        arrayList.insertElem(0, "aha");
        assertThat(false, is(arrayList.listEmpty()));
    }

    @Test
    public void clearList() {
        assertThat(0, is(arrayList.getSize()));
        arrayList.insertElem(0, "index");
        assertThat(1, is(arrayList.getSize()));
        arrayList.clearList();
        assertThat(0, is(arrayList.getSize()));
    }

    @Test(expected = RuntimeException.class)
    public void getElem() {
        arrayList.getElem(0);
        arrayList.insertElem(3, "aha");
        arrayList.getElem(2);
        arrayList.insertElem(0, "test");
        assertThat(arrayList.getElem(0), is("test"));

    }

    @Test(expected = RuntimeException.class)
    public void setElem() {
        arrayList.setElem(0, "update");
    }

    @Test
    public void getElemIndex() {
        assertThat(-1, is(arrayList.getElemIndex("ha")));
        arrayList.insertElem(0, "ha");
        assertThat(arrayList.getElemIndex("ha"), is(0));
        arrayList.insertElem(1, "haa");
        assertEquals(1, arrayList.getElemIndex("haa"));
    }

    @Test(expected = RuntimeException.class)
    public void insertElem() {
        arrayList.insertElem(12, "12");
    }

    @Test(expected = RuntimeException.class)
    public void delete() {
        arrayList.delete(5);
        arrayList.insertElem(0, "test");
        assertThat("test", is(arrayList.delete(0)));
        assertThat(arrayList.getElemIndex("test"), is(-1));
    }

    @Test
    public void getLength() {
        assertThat(10, is(arrayList.getLength()));
        for (int i = 0; i < 11; i++) {
            arrayList.insertElem(i, "num-" + i);
        }
        assertThat(20, is(arrayList.getLength()));
    }

    @Test
    public void getSize() {
        assertThat(0, is(arrayList.getSize()));
        arrayList.insertElem(0, "apple");
        arrayList.insertElem(1, "dog");
        assertThat(2, is(arrayList.getSize()));
        arrayList.delete(0);
        assertThat(1, is(arrayList.getSize()));
    }

}