列表是常用的数据结构，也是队列和栈的基础。本文将介绍两种列表的简单实现：数组列表和链表。

列表接口Github源代码

public interface IList {
    /**
     * 插入
     * @param i 位置
     * @param data 要插入的数据
     */
    void insert(int i, T data);

    /**
     * 获取
     * @param i 位置
     * @return i 位置上的元素
     */
    T get(int i);

    /**
     * 删除
     * @param i 位置
     * @return 被删除的元素
     */
    T delete(int i);

    /**
     * 列表内元素的数量
     * @return 数量
     */
    int size();

    /**
     * 列表是否为空
     * @return
     */
    boolean isEmpty();
}

数组列表Github源代码
数组列表测试Github源代码（测试用例不完全覆盖）

public class MyArrayList implements IList {

    private T[] datas;
    private int count = 0;
    private int capacity;

    public MyArrayList(int capacity) {
        datas = (T[]) new Object[capacity];
        this.capacity = capacity;
    }

    @Override
    public void insert(int i, T data) {
        if (count == capacity)
            throw new RuntimeException("列表已满");
        if (i  count)
            throw new RuntimeException("下标非法");
        if (i == count)
            datas[count++] = data;
        else {
            System.arraycopy(datas, i, datas, i + 1, count - i);
            datas[i] = data;
            count++;
        }
    }

    @Override
    public T get(int i) {
        if (i = count)
            throw new RuntimeException("下标非法");
        return datas[i];
    }

    @Override
    public T delete(int i) {
        if (i = count)
            throw new RuntimeException("下标非法");
        T tmp = datas[i];
        System.arraycopy(datas, i + 1, datas, i, count - i);
        count--;
        return tmp;
    }

    @Override
    public int size() {
        return this.count;
    }

    @Override
    public boolean isEmpty() {
        return this.size() == 0;
    }
}

链表Github源代码
链表测试类Github源代码（用例不完全覆盖）

public class MyLinkedList implements IList {

    private int count = 0;
    private Node head = new Node();
    private class Node{
        T data;
        Node next;

        public Node() {
        }

        Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

    @Override
    public void insert(int i, T data) {
        if (i  this.count)
            throw new RuntimeException("下标非法");
        Node prev = getNode(i - 1);
        prev.next = new Node(data, prev.next);
        count++;
    }

    @Override
    public T get(int i) {
        if (i = count)
            throw new RuntimeException("下标非法");
        return this.getNode(i).data;
    }

    @Override
    public T delete(int i) {
        if (i = count)
            throw new RuntimeException("下标非法");
        Node prev = getNode(i - 1);
        Node node = prev.next;
        prev.next = node.next;
        count--;
        return node.data;
    }

    @Override
    public int size() {
        return this.count;
    }

    @Override
    public boolean isEmpty() {
        return this.size() == 0;
    }

    /**
     * 得到第i个位置的元素
     * 注意k的初始条件和while循环递增
     * @param i 若i为-1，返回head
     * @return
     */
    private Node getNode(int i) {
        int k = - 1;
        Node res = head;
        while (k++

总结

数组列表的插入、删除的时间复杂度是O(n)，查询的时间复杂度是O(1);
链表的插入、删除的时间复杂度是O(1)，查询的时间复杂度是O(n);
因此，读多写少用数组列表，写多读少用链表。

ITPub博客

数据结构——列表

最新文章