HI技术分享-数据结构与算法

4.2.1、API设计

类名	SequenceList
构造方法	SequenceList(int capacity)：创建容量为capacity的SequenceList对象
成员方法	public void clear()：清空线性表 public boolean isEmpty()：判断线性表是否为空，是返回true，否返回false public int length()：返回线性表的个数 public T get(int i)：获取指定下标的元素 public void insert(int i,T t)：指定位置插入元素 public void insert(T t)：插入到线性表的最后 public T remove(int t)：删除并返回线性表的第i个元素 public int indexOf(T t)：返回线性表中首次出现指定数据元素的位置序号，若不存在，返回-1
成员变量	private T[] eles：存储元素的数组 private int N：当前线性表的长度

4.2.2、实现与测试

实现类

package cn.test.algorithm.datastruct;


import java.util.Arrays;

public class SequenceList<T> {
    //存储元素的数组
    private T[] eles;

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

    //构造方法
    public SequenceList(int capacity) {
        System.out.println("构造方法，容量为:" + capacity);
        //初始化数据
        this.eles = (T[]) new Object[capacity];
        //初始化长度
        this.N = 0;
    }

    //清空顺序表
    public void clear() {
        this.N = 0;
    }

    //判断线性表是否为空
    public boolean isEmpty() {
        if (this.N == 0) {
            return true;
        }
        return false;
    }

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

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


    //插入元素
    public void insert(T t) {
        eles[N++] = t;
    }

    //指定位置插入
    public void insert(T t, int i) {
        //长度加1
        N++;
        //把索引I处的元素及其后面的元素向后移动一位
        for (int index = N - 1; index > i; index--) {
            eles[index] = eles[index - 1];
        }
        //再把t元素放在i处
        eles[i] = t;
    }

    //删除指定位置的元素
    public T remove(int i) {
        //记录索引i处的值
        T value = eles[i];

        //把i后面的元素向前移动一位
        for (int index = i; i < N - 1; i++) {
            eles[index] = eles[index + 1];
        }

        //容量减1
        N--;

        return value;
    }

    //获取某个值所在的序号
    public int indexOf(T t) {
        for (int index = 0; index < N; index++) {
            if (eles[index].equals(t)) {
                return index;
            }
        }
        return -1;
    }

    //toString方法，打印对应的数据进行查看
    @Override
    public String toString() {
        return "SequenceList{" +
                "eles=" + Arrays.toString(eles) +
                ", N=" + N +
                '}';
    }
}

测试类

package cn.test.algorithm.test;

import cn.test.algorithm.datastruct.SequenceList;

public class SequenceListTest {
    public static void main(String[] args) {
        SequenceList<String> list = new SequenceList<>(10);
        list.insert("张三");
        System.out.println(list.toString());
        list.insert("李四");
        System.out.println(list.toString());
        list.insert("王五");
        System.out.println(list.toString());
        list.insert("赵六", 0);
        System.out.println(list.toString());
        System.out.println("第一个元素值：" + list.get(0));
        System.out.println("第三个元素值：" + list.get(3));
        list.remove(2);
        System.out.println(list.toString());
        System.out.println("第二个元素值：" + list.get(2));
        list.clear();//清空
        System.out.println("容量：" + list.length());
        System.out.println(list.toString());
    }
}

运行结果

构造方法，容量为:10
SequenceList{eles=[张三, null, null, null, null, null, null, null, null, null], N=1}
SequenceList{eles=[张三, 李四, null, null, null, null, null, null, null, null], N=2}
SequenceList{eles=[张三, 李四, 王五, null, null, null, null, null, null, null], N=3}
SequenceList{eles=[赵六, 张三, 李四, 王五, null, null, null, null, null, null], N=4}
第一个元素值：赵六
第三个元素值：王五
SequenceList{eles=[赵六, 张三, 王五, 王五, null, null, null, null, null, null], N=3}
第二个元素值：王五
容量：0
SequenceList{eles=[赵六, 张三, 王五, 王五, null, null, null, null, null, null], N=0}

4.2.3、遍历方式

作为一种容器存储数据，都需要向外提供遍历的方式，因此我们也需要给顺序表提供遍历方式。

在java中，遍历集合的方式一般都使用foreach循环，如果要让SequenceList也支持foreach循环，就需要做如下操作：

让SequenceList实现Iterable接口，重写Iterator方法
在SequenceList内部提供一个内部类Slterator，实现Iterator接口，重写hasNext方法和next方法

实现类

package cn.test.algorithm.datastruct;


import java.util.Arrays;
import java.util.Iterator;

public class SequenceList<T> implements Iterable<T> {
    //存储元素的数组
    private T[] eles;

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

    //构造方法
    public SequenceList(int capacity) {
        System.out.println("构造方法，容量为:" + capacity);
        //初始化数据
        this.eles = (T[]) new Object[capacity];
        //初始化长度
        this.N = 0;
    }

    //清空顺序表
    public void clear() {
        this.N = 0;
    }

    //判断线性表是否为空
    public boolean isEmpty() {
        if (this.N == 0) {
            return true;
        }
        return false;
    }

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

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


    //插入元素
    public void insert(T t) {
        eles[N++] = t;
    }

    //指定位置插入
    public void insert(T t, int i) {
        //长度加1
        N++;
        //把索引I处的元素及其后面的元素向后移动一位
        for (int index = N - 1; index > i; index--) {
            eles[index] = eles[index - 1];
        }
        //再把t元素放在i处
        eles[i] = t;
    }

    //删除指定位置的元素
    public T remove(int i) {
        //记录索引i处的值
        T value = eles[i];

        //把i后面的元素向前移动一位
        for (int index = i; i < N ; i++) {
            eles[index] = eles[index + 1];
        }

        //容量减1
        N--;

        return value;
    }

    //获取某个值所在的序号
    public int indexOf(T t) {
        for (int index = 0; index < N; index++) {
            if (eles[index].equals(t)) {
                return index;
            }
        }
        return -1;
    }

    //toString方法，打印对应的数据进行查看
    @Override
    public String toString() {
        return "SequenceList{" +
                "eles=" + Arrays.toString(eles) +
                ", N=" + N +
                '}';
    }


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

    //内部类
    private class SIterator implements Iterator {

        private int cusor;//定义一个指针

        public SIterator() {
            this.cusor = 0;//初始化0开始
        }

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

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

测试类

package cn.test.algorithm.test;

import cn.test.algorithm.datastruct.SequenceList;

public class SequenceListTest {
    public static void main(String[] args) {
        SequenceList<String> list = new SequenceList<>(10);
        list.insert("张三");
        System.out.println(list.toString());
        list.insert("李四");
        System.out.println(list.toString());
        list.insert("王五");
        System.out.println(list.toString());
        list.insert("赵六", 0);

        //添加遍历方法
        for (String s : list) {
            System.out.println("遍历元素：" + s);
        }

        System.out.println(list.toString());
        System.out.println("第一个元素值：" + list.get(0));
        System.out.println("第三个元素值：" + list.get(3));
        list.remove(2);
        System.out.println(list.toString());
        System.out.println("第二个元素值：" + list.get(2));
        list.clear();//清空
        System.out.println("容量：" + list.length());
        System.out.println(list.toString());
    }
}

运行结果

构造方法，容量为:10
SequenceList{eles=[张三, null, null, null, null, null, null, null, null, null], N=1}
SequenceList{eles=[张三, 李四, null, null, null, null, null, null, null, null], N=2}
SequenceList{eles=[张三, 李四, 王五, null, null, null, null, null, null, null], N=3}
遍历元素：赵六
遍历元素：张三
遍历元素：李四
遍历元素：王五
SequenceList{eles=[赵六, 张三, 李四, 王五, null, null, null, null, null, null], N=4}
第一个元素值：赵六
第三个元素值：王五
SequenceList{eles=[赵六, 张三, 王五, 王五, null, null, null, null, null, null], N=3}
第二个元素值：王五
容量：0
SequenceList{eles=[赵六, 张三, 王五, 王五, null, null, null, null, null, null], N=0}

4.2.4、顺序表容量变化

前面我们实现的顺序表如果我们设置的容量为3个，我们一直往里面插入数据，当插入第4个元素的时间就会报错，原因就是我们内部存储元素的数组的容量只有3，所以造成了下标越界。那么我们如何解决这样的问题呢？这里就需要对原始数组进行扩容处理，其实就是容量变化。

什么时候需要容量变化：

添加元素时
- 添加元素时，应该检查当前数组的大小是否能容纳新的元素，如果不能就需要创建一个新的容量更大的数组，这里创建新数组的容量是原数组容量的2倍
移除元素时
- 移除元素时，应该检查当前数组的大小是否太大，如果正在用100个容量的数组存储10个元素，这样就造成了内存空间的浪费，应该创建一个容量更小的数组存储数据，如果我们发现数据元素的数量不足数组容量的1/4，则创建一个是原来数组容量的1/2的新数组来存储元素。

实现类

package cn.test.algorithm.datastruct;


import java.util.Arrays;
import java.util.Iterator;

public class SequenceList<T> implements Iterable<T> {
    //存储元素的数组
    private T[] eles;

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

    //构造方法
    public SequenceList(int capacity) {
        System.out.println("构造方法，容量为:" + capacity);
        //初始化数据
        this.eles = (T[]) new Object[capacity];
        //初始化长度
        this.N = 0;
    }

    //清空顺序表
    public void clear() {
        this.N = 0;
    }

    //判断线性表是否为空
    public boolean isEmpty() {
        if (this.N == 0) {
            return true;
        }
        return false;
    }

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

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


    //插入元素
    public void insert(T t) {
        if (N == eles.length) {
            reset(N * 2);
        }
        eles[N++] = t;
    }

    //指定位置插入
    public void insert(T t, int i) {

        if (N == eles.length) {
            reset(N * 2);
        }

        //长度加1
        N++;
        //把索引I处的元素及其后面的元素向后移动一位
        for (int index = N - 1; index > i; index--) {
            eles[index] = eles[index - 1];
        }
        //再把t元素放在i处
        eles[i] = t;
    }

    //删除指定位置的元素
    public T remove(int i) {
        //记录索引i处的值
        T value = eles[i];

        //把i后面的元素向前移动一位
        for (int index = i; i < N; i++) {
            eles[index] = eles[index + 1];
        }

        //容量减1
        N--;

        if (N < eles.length / 4) {
            reset(eles.length / 2);
        }

        return value;
    }

    //获取某个值所在的序号
    public int indexOf(T t) {
        for (int index = 0; index < N; index++) {
            if (eles[index].equals(t)) {
                return index;
            }
        }
        return -1;
    }

    //根据newSize，重置eles大小
    private void reset(int newSize) {
        //定义一个临时数组，指向原数组
        T[] temp = eles;
        //创建新数组
        eles = (T[]) new Object[newSize];
        //把原来数组的数据拷贝到新数组中
        for (int i = 0; i < N; i++) {
            eles[i] = temp[i];
        }
    }

    //toString方法，打印对应的数据进行查看
    @Override
    public String toString() {
        return "SequenceList{" +
                "eles=" + Arrays.toString(eles) +
                ", N=" + N +
                '}';
    }


    @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;
        }

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

测试类

package cn.test.algorithm.test;

import cn.test.algorithm.datastruct.SequenceList;

public class SequenceListTest {
    public static void main(String[] args) {
        SequenceList<String> list = new SequenceList<>(3);
        System.out.println(list.toString());
        list.insert("张三");
        System.out.println(list.toString());
        list.insert("李四");
        System.out.println(list.toString());
        list.insert("王五");
        System.out.println(list.toString());
        list.insert("赵六");
        System.out.println(list.toString());
        list.insert("孙七");
        list.insert("钱八");
        list.insert("周九");
        System.out.println(list.toString());
        list.remove(6);
        list.remove(5);
        list.remove(4);
        list.remove(3);
        list.remove(2);
        list.remove(1);
        System.out.println(list.toString());
    }
}

运行结果

构造方法，容量为:3
SequenceList{eles=[null, null, null], N=0}
SequenceList{eles=[张三, null, null], N=1}
SequenceList{eles=[张三, 李四, null], N=2}
SequenceList{eles=[张三, 李四, 王五], N=3}
SequenceList{eles=[张三, 李四, 王五, 赵六, null, null], N=4}
SequenceList{eles=[张三, 李四, 王五, 赵六, 孙七, 钱八, 周九, null, null, null, null, null], N=7}
SequenceList{eles=[张三, null, null, null, null, null], N=1}

4.2.5、顺序表时间复杂度

get(i)：从代码中可以看出，不论数据元素N有多少，只需要一次就可以获取到，所以该方法的时间复杂度为O(1)
insert(T t,int i)：每一次插入都需要把后面的数据移动一次，随着元素量N的增大，移动的元素也越多，时间复杂度为O(n)
remove(int i)：每一次删除一个元素，都需要把后面的元素向前移动一次，随着元素量N的增大，移动的元素也很多，时间复杂度为O(n)

由于顺序表的底层是数组实现的，数组的长度是固定的，所以在操作的过程中涉及到了容器的扩容，这样就导致了顺序表在使用过程中的时间复杂度不是线性的，在某些元素的时候要快，插入需要扩容的就会比较慢。

4.2.6、java中ArrayList实现

java的ArrayList集合底层也是一种顺序表，使用数组实现，同样提供了增删改查的方法。通过查看ArrayList源码，我们分析是否符合以下三个功能：

①是否用到数组

transient Object[] elementData;

②是否有扩容

//在add方法中，有如下方法，确保容量
ensureCapacityInternal(size + 1);

//方法内容
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

//进入ensureExplicitCapacity方法
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

//进入grow方法
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}
//这里就是实现了数组的复制

③是否有遍历方式

#iterator方法
public Iterator<E> iterator() {
    return new Itr();
}

#重写了Iterator接口Itr
private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

    public boolean hasNext() {
        return cursor != size;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }
    //....这里还有其他方法
}

ArrayList为了具有通用型，所以代码比较雍肿。所以我们需要自己了解这些数据结构如何实现，以便后期自己可以写出适用场景的顺序表。

4.2、线性表之顺序表(Sequence List)

4.2.1、API设计

4.2.2、实现与测试

4.2.3、遍历方式

4.2.4、顺序表容量变化

4.2.5、顺序表时间复杂度

4.2.6、java中ArrayList实现