ArrayList 与 LinkedList 的方法及其区别

写在前面: 我是「扬帆向海」,这个昵称来源于我的名字以及女朋友的名字。我热爱技术、热爱开源、热爱编程。技术是开源的、知识是共享的。

这博客是对自己学习的一点点总结及记录,如果您对 Java算法 感兴趣,可以关注我的动态,我们一起学习。

用知识改变命运,让我们的家人过上更好的生活

一、聊聊 LinkedList

1.LinkedList 的底层源码

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

双链表实现了 List 和Deque接口。 实现所有可选列表操作,并允许所有元素(包括null )。
所有的操作都能像双向列表一样。 索引到列表中的操作将从开始或结束遍历列表,以更接近指定的索引为准。

2.LinkedList 的构造方法

  • LinkedList() 构造一个空列表。
  • LinkedList(Collection<? extends E> c) 构造一个包含指定集合的元素的列表,按照它们由集合的迭代器返回的顺序。

3.LinkedList 的常用方法

  • boolean add(E e) 将指定的元素追加到此列表的末尾
  • int size() 返回此列表中的元素数
  • E get(int index) 返回此列表中指定位置的元素
  • E remove(int index) 删除该列表中指定位置的元素
  • void addFirst(E e) 在该列表开头插入指定的元素
  • void addLast(E e) 将指定的元素追加到此列表的末尾
  • E getFirst() 返回此列表中的第一个元素
  • E getLast() 返回此列表中的最后一个元素
  • void push(E e) 将元素推送到由此列表表示的堆栈上
  • E pop() 从此列表表示的堆栈中弹出一个元素

测试代码:

public class LinkedListTest {
    public static void main(String[] args) {

        LinkedList<String> list = new LinkedList<String>();
        // boolean add(E e) 将指定的元素追加到此列表的末尾。
        list.add("aaa");
        list.add("ddd");
        list.add("ccc");
        list.add("111");
        list.add("aaa");
        list.add("eee");

        // int size() 返回此列表中的元素数
        System.out.println(list.size()); // 6
        System.out.println(list); // [aaa, ddd, ccc, 111, aaa, eee]

        // E get(int index) 返回此列表中指定位置的元素。
        System.out.println(list.get(0)); // aaa
        System.out.println(list.get(list.size() - 1)); // eee

        System.out.println("*****************************");
        // E remove(int index) 删除该列表中指定位置的元素
        System.out.println(list.remove(3)); //  111

        System.out.println("*****************************");
        // void addFirst(E e) 在该列表开头插入指定的元素
        list.addFirst("111");
        System.out.println(list); //  [111, aaa, ddd, ccc, aaa, eee]

        // void addLast(E e) 将指定的元素追加到此列表的末尾。
        list.addLast("666");
        System.out.println(list); // [111, aaa, ddd, ccc, aaa, eee, 666]

        // E getFirst() 返回此列表中的第一个元素
        System.out.println(list.getFirst()); // 111

        // E getLast() 返回此列表中的最后一个元素。
        System.out.println(list.getLast()); // 666

        System.out.println("*****************************");
        // void push(E e) 将元素推送到由此列表表示的堆栈上
        list.push("888");
        System.out.println(list); //  [888, 111, aaa, ddd, ccc, aaa, eee, 666]

        // E pop() 从此列表表示的堆栈中弹出一个元素
        String pop = list.pop();
        System.out.println(pop); // 888

        System.out.println("****************************");

        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }

        System.out.println("****************************");
        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
    }
}

测试结果:

6
[aaa, ddd, ccc, 111, aaa, eee]
aaa
eee
*****************************
111
*****************************
[111, aaa, ddd, ccc, aaa, eee]
[111, aaa, ddd, ccc, aaa, eee, 666]
111
666
*****************************
[888, 111, aaa, ddd, ccc, aaa, eee, 666]
888
****************************
111
aaa
ddd
ccc
aaa
eee
666
****************************
111
aaa
ddd
ccc
aaa
eee
666

二、聊聊 ArrayList

1. ArrayList 的底层源码

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

ArrayList 是从JDK1.2 引入的。

它是可调整大小的数组,实现了List接口。 实现所有可选列表操作,并允许所有元素包括null 。 除了实现List 接口之外,该类还提供了一些方法来操纵内部使用的存储列表的数组的大小。 (这个类是大致相当于Vector,不同之处在于它是不同步的)。

内部封装一个数组,用数组来存储数据。内部数组的默认初始容量 10,存满后 1.5 倍增长

从 JDK1.8开始, ArrayList 一开始创建一个长度为 0 的数组,当添加第一个元素时再创建一个始容量为 10 的 数组。

2. ArrayList 的构造方法

  • ArrayList() 构造一个初始容量为十的空列表。
  • ArrayList(Collection<? extends E> c) 构造一个包含指定集合的元素的列表,按照它们由集合的迭代器返回的顺序。
  • ArrayList(int initialCapacity) 构造具有指定初始容量的空列表。

3. ArrayList 的常用方法

ArrayList 的方法和 LinkedList 相同,但它没有两端操作数据的方法

  • boolean add(E e) 将指定的元素追加到此列表的末尾
  • int size() 返回此列表中的元素个数
  • E get(int index) 返回此列表中指定位置的元素
  • E remove(int index) 删除该列表中指定位置的元素
  • boolean remove(Object o) 从列表中删除指定元素的第一个出现(如果存在)
  • boolean contains(Object o) 如果此列表包含指定的元素,则返回 true
  • boolean addAll(int index, Collection<? extends E> c) 将指定集合中的所有元素插入到此列表中,从指定的位置开始
    - void clear() 从列表中删除所有元素
  • for / iterator 集合遍历

测试代码:

public class ArrayListTest {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        // boolean add(E e) 将指定的元素追加到此列表的末尾
        list.add(111);
        list.add(666);
        list.add(333);
        list.add(888);
        list.add(111);
        list.add(999);
        // int size() 返回此列表中的元素个数
        System.out.println(list.size()); // 6
        System.out.println(list); // [111, 666, 333, 888, 111, 999]

        // E get(int index) 返回此列表中指定位置的元素
        System.out.println(list.get(3)); // 888

        // E remove(int index) 删除该列表中指定位置的元素。
        list.remove(3);
        System.out.println(list); // [111, 666, 333, 111, 999]

        // boolean remove(Object o) 从列表中删除指定元素的第一个出现(如果存在)
        System.out.println(list.remove(Integer.valueOf(111))); // true
        System.out.println(list); // [666, 333, 111, 999]

        System.out.println("******************************");
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }

        // 用三种方式遍历集合
        System.out.println("******************************");
        Iterator<Integer> it = list.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }

        System.out.println("******************************");
        for (Integer integer : list) {
            System.out.println(integer);
        }

        System.out.println("******************************");
        // boolean contains(Object o) 如果此列表包含指定的元素,则返回 true
        boolean contains = list.contains(666);
        System.out.println(contains); // true

        System.out.println("******************************");
        ArrayList<Integer> list1 = new ArrayList<Integer>();
        list1.add(123);
        list1.add(456);
        //  boolean addAll(int index, Collection<? extends E> c)
        //  将指定集合中的所有元素插入到此列表中,从指定的位置开始。
        list.addAll(1, list1);
        System.out.println(list); // [666, 123, 456, 333, 111, 999]
        System.out.println(list1); // [123, 456]

        // void clear() 从列表中删除所有元素
        list1.clear();
        System.out.println(list1); // []
    }
}

测试结果:

6
[111, 666, 333, 888, 111, 999]
888
[111, 666, 333, 111, 999]
true
[666, 333, 111, 999]
******************************
666
333
111
999
******************************
666
333
111
999
******************************
666
333
111
999
******************************
true
******************************
[666, 123, 456, 333, 111, 999]
[123, 456]
[]

三、两者与 Vector 的区别

1.ArrayList 和 LinkedList 的区别

二者都线程不安全,但是效率比 Vector 的高

  • ArrayList 底层是以 数组 的形式保存数据,随机访问集合中的元素比LinkedList 快(原因是 LinkedList 要移动指针);
  • LinkedList 内部以 链表 的形式保存集合里面数据,它随机访问集合中的元素性能比较慢,但是新增和删除时速度比 ArrayList 快(原因是 ArrayList 要移动数据)。

2.ArrayList 和 Vector 的区别

  • ArrayList 和 Vector 底层都是 数组
  • ArrayList 每次扩容的情况下扩容为原来的1.5 倍。线程不安全,当多个线程同时访问同一个ArrayList 集合时,如果两个或两个以上的线程修改了 ArrayList 集合,则必须手动保证该集合的同步性。
  • Vector 是同步类,其线程安全,但是它的访问比较慢。Vector 每次扩容为其空间大小的 2 倍。