数据结构与算法 | 线性表 —— 顺序表

pexels-photo-577585

原文链接：https://wangwei.one/posts/java-data-structures-and-algorithms-arraylist.html

线性表

定义

将具有线性关系的数据存储到计算机中所使用的存储结构称为线性表。

线性，是指数据在逻辑结构上具有线性关系。

分类

逻辑结构上相邻的数据在物理结构存储分两种形式：

• 数据在内存中集中存储，采用顺序表示结构，称为"顺序存储"；
• 数据在内存中分散存储，采用链式表示结构，称为"链式存储"；

顺序表

定义

逻辑上具有线性关系的数据按照前后的次序全部存储在一整块连续的内存空间中，之间不存在空隙，这样的存储结构称为顺序存储结构。

使用线性表的顺序存储结构生成的表，称为顺序表。

image

实现

顺序表的存放数据的特点和数组一样，所以我们这里采用数组来实现，这里我们来用数组来简单实现Java中常用的ArrayList。

接口定义：

package one.wangwei.algorithms.datastructures.list;

/**
 * List Interface
 *
 * @param <T>
 * @author https://wangwei.one/
 * @date 2018/04/27
 */
public interface IList<T> {

    /**
     * add element
     *
     * @param element
     * @return
     */
    public boolean add(T element);

    /**
     * add element at index
     *
     * @param index
     * @param element
     * @return
     */
    public boolean add(int index, T element);

    /**
     * remove element
     *
     * @param element
     * @return
     */
    public boolean remove(T element);

    /**
     * remove element by index
     *
     * @param index
     * @return
     */
    public T remove(int index);

    /**
     * set element by index
     *
     * @param index
     * @param element
     * @return old element
     */
    public T set(int index, T element);

    /**
     * get element by index
     *
     * @param index
     * @return
     */
    public T get(int index);

    /**
     * clear list
     */
    public void clear();

    /**
     * contain certain element
     *
     * @param element
     * @return
     */
    public boolean contains(T element);

    /**
     * get list size
     *
     * @return
     */
    public int size();

}

源代码

接口实现：

package one.wangwei.algorithms.datastructures.list.impl;

import one.wangwei.algorithms.datastructures.list.IList;

import java.util.Arrays;

/**
 * Array List
 *
 * @param <T>
 * @author https://wangwei.one
 * @date 2018/04/27
 */
public class MyArrayList<T> implements IList<T> {

    /**
     * default array size
     */
    private final int DEFAULT_SIZE = 10;

    /**
     * array size
     */
    private int size = 0;

    /**
     * array
     */
    private T[] array = (T[]) new Object[DEFAULT_SIZE];

    /**
     * add element
     *
     * @param element
     * @return
     */
    @Override
    public boolean add(T element) {
        return add(size, element);
    }

    /**
     * add element at index
     *
     * @param index
     * @param element
     * @return
     */
    @Override
    public boolean add(int index, T element) {
        if (index < 0 || index > size) {
            throw new ArrayIndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        // need grow
        if (size >= array.length) {
            grow();
        }
        // copy array element
        if (index < size) {
            System.arraycopy(array, index, array, index + 1, size - index);
        }
        array[index] = element;
        size++;
        return true;
    }

    /**
     * grow 50%
     */
    private void grow() {
        int growSize = size + (size >> 1);
        array = Arrays.copyOf(array, growSize);
    }

    /**
     * remove element
     *
     * @param element
     * @return
     */
    @Override
    public boolean remove(T element) {
        for (int i = 0; i < size; i++) {
            if (element == null) {
                if (array[i] == null) {
                    remove(i);
                    return true;
                }
            } else {
                if (array[i].equals(element)) {
                    remove(i);
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * remove element by index
     *
     * @param index
     * @return
     */
    @Override
    public T remove(int index) {
        checkPositionIndex(index);
        T oldElement = array[index];
        // need copy element
        if (index != (size - 1)) {
            System.arraycopy(array, index + 1, array, index, size - index - 1);
        }
        --size;
        array[size] = null;
        // shrink 25%
        int shrinkSize = size - (size >> 2);
        if (shrinkSize >= DEFAULT_SIZE && shrinkSize > size) {
            shrink();
        }
        return oldElement;
    }

    /**
     * shrink 25%
     */
    private void shrink() {
        int shrinkSize = size - (size >> 2);
        array = Arrays.copyOf(array, shrinkSize);
    }

    /**
     * set element by index
     *
     * @param index
     * @param element
     * @return
     */
    @Override
    public T set(int index, T element) {
        checkPositionIndex(index);
        T oldElement = array[index];
        array[index] = element;
        return oldElement;
    }

    /**
     * get element by index
     *
     * @param index
     * @return
     */
    @Override
    public T get(int index) {
        checkPositionIndex(index);
        return array[index];
    }

    /**
     * check index
     *
     * @param index
     */
    private void checkPositionIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
    }

    /**
     * clear list
     */
    @Override
    public void clear() {
        for (int i = 0; i < size; i++) {
            array[i] = null;
        }
        size = 0;
    }

    /**
     * contain certain element
     *
     * @param element
     */
    @Override
    public boolean contains(T element) {
        for (int i = 0; i < size; i++) {
            if (element == null) {
                if (array[i] == null) {
                    return true;
                }
            } else {
                if (array[i].equals(element)) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * get list size
     *
     * @return
     */
    @Override
    public int size() {
        return size;
    }
}

源代码

主要注意以下几点：

• 添加元素时 ，判断是否需要对Array进行扩容；
• 删除元素时，判断是否需要对Array进行收缩；
• remove与contains接口，注意element为null的情况；

特点

• 对数据进行遍历的时候，数据在连续的物理空间中进行存放，CPU的内部缓存结构会缓存连续的内存片段，可以大幅降低读取内存的性能开销，所以查询比较快；
• 删除线性表中的元素的时候，后面的元素会整体向前移动，所以删除的效率较低，插入类似，时间复杂度为O(n)；

参考资料

• http://data.biancheng.net/view/4.html
• https://github.com/phishman3579/java-algorithms-implementation
• 《数据结构与算法之美》