ArrayList和LinkedList

2024-02-26 18:19:40

ArrayList和LinkedList的区别：

相同点
线程安全性
ArrayList和LinkedList都是线程不安全的，可以使用Collections.synchronizedList()方法保证线程的安全性。
存储特点
存储的元素都是有序的，都是可以重复的，新增的元素都是存储到List的末尾处。(尾插)

  1. ArrayList是实现了基于动态数组的数据结构，底层是一个Object类型的数组，初始容量是10，支持动态扩容，扩容后的容量是当前容量的1.5倍，它的最大容量是Integer.MAX-VALUE-8（避免内存溢出，减少出错）
  2. LinkedList 是基于链表的数据结构，底层是一个双向链表，初始的容量是0。
  • LinkedList比ArrayList更占内存，因为LinkedList的结点除了存储数据，还存储了两个引用，一个指向前一个元素，一个指向后一个元素；
  • 对于随机访问，ArrayList要优于LinkedList；
  • 对于插入和删除操作，LinkedList优于ArrayList(理论上)。

查询

  • ArrayList随机访问效率高，因为元素的存储是有序的，通过下标index可以找到所查询数据在内存中的位置，时间复杂度为O(1)
  • LinkedList 查询效率较低，它在查询指定数据的时候需要遍历链表逐个查询，时间复杂度为O(n)

插入

  • ArrayList在尾部插入的效率比较高，时间复杂度O(1)，但是在其他位置插入效率则比较低，需要进行大量的数据移动，时间复杂度O(n)；
  • LinkedList在头部和尾部插入元素的效率比较高，时间复杂度为O(1)，但是在中间指定位置插入元素，需要先遍历找到元素的位置，然后插入，时间复杂度O(n)。

删除

  • ArrayList删除元素除了末尾的结点之外都需要进行大量的数据移动，时间复杂度为O(n)；
  • LinkedList删除元素只需要改变指针的指向，但是删除元素时需要遍历链表查询要删除数据的位置，时间复杂度为O(n)

内存空间

  • ArrayList基于数组实现，每次扩容后的容量是固定的，所以会在尾部预留一定的空间；
  • LinkedList基于双向链表实现，每个结点需要保存数据和指向前后元素的引用，会消耗一部分空间。

扩容机制

  • ArrayList每次扩容需要把原数组的元素复制到新的数组中去；
  • LinkedList是链表，不需要进行扩容。

实现

Arraylist

ArrayList是List接口的实现类，ArrayList的实现原理上是顺序表。
ArrayList和LinkedList
要实现一个ArrayList，首先要实现一个List接口。
ArrayList的常用方法有：

  1. boolean add(Integer e);
  2. void add(int index, Integer e);
  3. Integer remove(int index);
  4. boolean remove(Integer e);
  5. Integer get(int index);
  6. Integer set(int index, Integer e);
  7. int size();
  8. void clear();
  9. boolean isEmpty();
  10. boolean contains(Integer e);
  11. int indexOf(Integer e);
  12. int lastIndexOf(Integer e);

所以List接口的实现为：

//仿写真实的List接口
public interface List extends Iterable {
    boolean add(Integer e);//尾插
    void add(int index, Integer e);//根据下标尾插

    // 根据下标删除
    Integer remove(int index);
    // 删除第一个遇到的元素
    boolean remove(Integer e);

    Integer get(int index);
    Integer set(int index, Integer e);

    int size();
    void clear();
    boolean isEmpty();

    boolean contains(Integer e);
    int indexOf(Integer e);//返回第一个遇到的元素e的下标
    int lastIndexOf(Integer e);//返回最后一个元素e的下标
}

仿写真实的Arraylist实现类：

顺序表的内部结构是是数组，所以需要维护一个数组array以及数组内部的元素个数size

ArrayList的实现代码：

public class ArrayList implements List {
    private int[] array;    // 顺序表内部的数组
    private int size;       // 顺序表内部的元素个数
    public ArrayList() {
        array = new int[10];
        size = 0;
    }
    // 平时时间复杂度是 O(1)
    // 需要扩容时，时间复杂度是 O(n)
    // 平均 O(1)
    @Override
    public boolean add(Integer e) {
        if (array.length == size) {
            // 现在已经满了，需要扩容了
            ensureCapacity(array.length * 2);//扩容的长度一般是数组长度的2倍
        }
        array[size++] = e;
        return true;
    }

    // 调用完这个方法后，保证容量一定是 >= capacity
    // 时间复杂度 O(n)
    public void ensureCapacity(int capacity) {
        // 0. 检查是否需要扩容
        if (this.array.length >= capacity) {
            return;
        }
        // 1. 定义新的数组
        int[] newArray = new int[capacity];
        // 2.从 array 数组中搬到 newArray 数组中
        for (int i = 0; i < size; i++) {
            newArray[i] = this.array[i];
        }
        this.array = newArray;
    }

    @Override
    public void add(int index, Integer e) {
        // 合法的下标 [0, size]
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("不合法的下标: " + index);
        }
        if (array.length == size) {
            ensureCapacity(array.length * 2);
        }
        // 要把 index 及之后的所有元素，全部向后搬移
        // 为了保证元素不被覆盖，从后往前搬
        for (int i = size; i > index; i--) {
            array[i] = array[i - 1];
        }
        array[index] = e;
        size++;
    }

    @Override
    public Integer remove(int index) {
        // 合法的下标: [0 , size-1]
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("不合法的下标: " + index);
        }
        int e = array[index];
        // 从前往后删
        // [index + 1, size-1] 的元素，搬移到 [index, size-2] 的下标处
        for (int i = index + 1; i <= size - 1; i++) {
            array[i - 1] = array[i];
        }
        size--;
        return e;
    }
    
    @Override
    public boolean remove(Integer e) {
        int index = indexOf(e);
        if (index != -1) {
            remove(index);
            return true;
        } else {
            return false;
        }
    }
    @Override
    public Integer get(int index) {
        // 合法下标: [0, size-1]
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("不合法的下标: " + index);
        }
        return array[index];
    }

    @Override
    public Integer set(int index, Integer e) {
        // 合法下标: [0, size-1]
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("不合法的下标: " + index);
        }

        Integer old = array[index];
        array[index] = e;
        return old;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public void clear() {
        //Arrays.fill(array, -1);
        size = 0;
    }

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

    @Override
    public boolean contains(Integer e) {
        return indexOf(e) != -1;
    }

    @Override
    public int indexOf(Integer e) {
        for (int i = 0; i < size; i++) {
            if (array[i] == e) {
                return i;
            }
        }
        return -1;
    }

    @Override
    public int lastIndexOf(Integer e) {
        for (int i = size - 1; i >= 0; i--) {
            if (array[i] == e) {
                return i;
            }
        }
        return -1;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < size; i++) {
            sb.append(array[i]);
            if (i != size - 1) {
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }

    @Override
    public Iterator iterator() {
        // 返回一个 Iterator 接口的实现类的对象
        return new ArrayListIterator(this);
    }
}

对顺序表进行迭代：

public interface Iterable {
    Iterator iterator();
}

public interface Iterator {
    boolean hasNext();
    Integer next();
    void remove();
}

public class ArrayListIterator implements Iterator {
    private ArrayList list;//我们要迭代（遍历）的顺序表
    private int index; // 我们现在在顺序表的哪个位置
    ArrayListIterator(ArrayList list) {
        this.list = list;
        this.index = 0;
    }
    @Override
    public boolean hasNext() {
        return index < list.size();
    }
    /*
    1. 返回迭代器当前所在的位置的元素
    2. 让迭代器走到下一个位置
     */
    @Override
    public Integer next() {
        return list.get(index++);
    }
    @Override
    public void remove() {
    }
}

LinkedList

LinkedList类也是List接口的实现类，它的原理是链表（双向的链表）。

双向链表：既可以向后遍历，也可以向前遍历
既要记录第一个结点，也要记录最后一个结点。

public class Node {
    public Node prev;
    public Node next;
    public Integer element;
    public Node(Integer element) {
        this.element = element;
    }
}

LinkedList的实现：


public interface Iterable {
    Iterator iterator();
}
public interface Iterator {
    boolean hasNext();
    Integer next();
}
public interface List extends Iterable {
    boolean add(Integer e);
    void add(int index, Integer e);

    // 根据下标删除
    Integer remove(int index);
    // 删除第一个遇到的
    boolean remove(Integer e);

    Integer get(int index);
    Integer set(int index, Integer e);

    int size();
    void clear();
    boolean isEmpty();

    boolean contains(Integer e);
    int indexOf(Integer e);
    int lastIndexOf(Integer e);
}

public class LinkedList implements List {
    public Node head;   // 指向第一个结点
    public Node last;   // 指向最后一个结点
    public int size;
    @Override
    //尾插 O(1)
    public boolean add(Integer e) 
        Node newNode = new Node(e);
        if (size == 0) {
            this.head = this.last = newNode;
        } else {
            this.last.next = newNode;
            newNode.prev = this.last;
            this.last = newNode;
        }
        this.size++;
        return true;
    }

    @Override
    // O(n)
    public void add(int index, Integer e) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("下标越界: " + index);
        }
        if (index == size) {
            // 尾插
            add(e);
        } else if (index == 0) {
            // 头插
            Node newNode = new Node(e); // 把值装入结点中
            newNode.next = this.head;
            this.head.prev = newNode;
            this.head = newNode;
            size++;
        } else {
            // 其他情况
            // 找到 index - 1 所在的位置，进行结点的插入
            Node prev;
            if (index - 1 < size / 2) {
                prev = head;
                // 从 head 处出发，找到 index - 1 位置的结点
                //一共要跳 index - 1 次
                for (int i = 0; i < index - 1; i++) {
                    prev = prev.next;
                }
            } else {
                // 从 last 处出发，找到 index - 1 位置的结点
                // 一共要跳 (size - 1) - (index - 1) 次
                prev = last;
                for (int i = 0; i < size - index; i++) {
                    prev = prev.prev;
                }
            }
            // 走到这里时，prev 指向 index - 1 位置的下标
            Node next = prev.next;
            Node newNode = new Node(e); // 把值装入结点中
            newNode.prev = prev;
            newNode.next = next;
            prev.next = newNode;
            next.prev = newNode;
            size++;
        }
    }

    @Override
    // O(n)
    public Integer remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("下标越界: " + index);
        }
        // 走到这里，size 一定是 > 0 的
        Integer v;
        if (index == 0) {//头删
            v = head.element;
            this.head = this.head.next;
            this.head.prev = null;
            size--;
            if (size == 0) {
                last = null;
            }
        } else if (index == size - 1) {//尾删
            v = last.element;
            this.last = this.last.prev;
            this.last.next = null;
            size--;
            if (size == 0) {
                head = null;
            }
        } else {
            // 找到 index - 1 所在的位置，进行结点的插入
            Node prev;
            if (index - 1 < size / 2) {
                prev = head;
                // 从 head 处出发，找到 index - 1 位置的结点
                for (int i = 0; i < index - 1; i++) {
                    prev = prev.next;
                }
            } else {
                // 从 last 处出发，找到 index - 1 位置的结点
                prev = last;
                for (int i = 0; i < size - index; i++) {
                    prev = prev.prev;
                }
            }
            Node toRemove = prev.next;
            v = toRemove.element;
            prev.next = toRemove.next;
            toRemove.next.prev = prev;
            size--;
        }
        return v;
    }
    
    @Override
    // O(n)
    public boolean remove(Integer e) {
        Node prev = null;
        for (Node cur = head; cur != null; prev = cur, cur = cur.next) {
            if (cur.element.equals(e)) {
                if (prev == null) {
                    remove(0);
                    return true;
                } else {
                    prev.next.next.prev = prev;
                    prev.next = prev.next.next;
                    size--;
                    return true;
                }
            }
        }
        return false;
    }

    @Override
    // O(n)
    public Integer get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("下标越界: " + index);
        }
        Node cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur.element;
    }

    @Override
    // O(n)
    public Integer set(int index, Integer e) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("下标越界: " + index);
        }
        Node cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        Integer v = cur.element;
        cur.element = e;
        return v;
    }

    @Override
    // O(1)
    public int size() {
        return size;
    }
    @Override
    // O(1)
    public void clear() {
        head = null;
        last = null;
        size = 0;
    }
    @Override
    // O(1)
    public boolean isEmpty() {
        return size == 0;
    }
    @Override
    // O(n)
    public boolean contains(Integer e) {
        return indexOf(e) != -1;
    }
    @Override
    // O(n)
    public int indexOf(Integer e) {
        int i = 0;
        for (Node cur = head; cur != null; cur = cur.next, i++) {
            if (cur.element.equals(e)) {
                return i;
            }
        }
        return -1;
    }
    @Override
    // O(n)
    public int lastIndexOf(Integer e) {
        int i = size - 1;
        for (Node cur = last; cur != null; cur = cur.prev, i--) {
            if (cur.element.equals(e)) {
                return i;
            }
        }
        return -1;
    }

    @Override
    public Iterator iterator() {
        return new LinkedListIterator(this);
    }
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        for (Node cur = head; cur != null; cur = cur.next) {
            sb.append(cur.element);
            if (cur != last) {
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }
}

public class LinkedListIterator implements Iterator {
    private LinkedList list;
    private Node current;
    public LinkedListIterator(LinkedList list) {
        this.list = list;
        this.current = list.head;
    }
    @Override
    public boolean hasNext() {
        return current != null;
    }

    @Override
    public Integer next() {
        Integer e = current.element;
        current = current.next;
        return e;
    }
}
上一篇：js对数字进行格式化处理


下一篇：el-pagination分页-自定义左右箭头样式