当前位置：首页 > article >正文

Java中的linkedList类及与ArrayList的异同

article 2025/1/20 13:26:31

继承实现关系

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

由于涉及的类过多，画起来过于繁琐，这里只展示最外层的继承实现关系

可以看到它是继承自AbstractSqquentialList，并且实现了多个接口类，感兴趣的小伙伴可以去深入查看LinkedList具体怎样实现了它们的方法。

与ArrayList的相同之处

和ArrayList类似，LinkedList也是集合的一种，也是用来存放对象类型的数据的，而且存放对象的类型可以不同，由于都继承自Collection类，他们都有一些相同的方法，作用也是相同的，比如添加数据删除数据这些。

与ArrayList的不同之处

光看名字就可以看出来，ArrayList是以数组为存储结构，底层是一个对象数组，LinkedList是以链表为存储结构，底层是一个双向链表，找到源码可以看到如下的存储结构

    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

除了存储对象以外，每个节点都有一个指向前面的引用和一个指向后面的引用

由这个存储结构的不同我们可以区分它们的特点

1.ArrayList由于底层是数组，所以用来查询和修改的效率是很高的，时间复杂度可以达到O(1)，而增加和删除的时间复杂度为O(n)，而且特殊情况下需要重新分配空间，效率低下

2.LinkedList底层是双向链表，用来增加和删除节点的效率是很高的，时间复杂度可以达到O(1)，而如果想要查询和修改需要遍历链表，效率较低

常用方法

1.添加元素

（1） public boolean add(E e)

第一种方法和ArrayList的一样，括号中传入要加入集合中的对象，会默认插入到链表的末尾

		LinkedList l=new LinkedList();
		
		l.add("test1");//默认插入到链表末尾

（2）public void add(int index, E element)

和ArrayList的方法一样，第一个参数传入要插入的位置，后面传入要插入的对象，注意下标不能超过链表中实际的元素数量

		LinkedList l=new LinkedList();
		l.add("test1");//默认插入到末尾
		l.add(1,"test2");//插入到链表中下标为1的地方

（3）public void addFirst(E e)

看方法名就可以猜出来，这个方法会将传入的对象插入到链表的最前面

		LinkedList l=new LinkedList();
		l.add("test1");//默认插入到末尾
		l.add(1,"test2");//插入到链表中下标为1的地方
		
		l.addFirst("testfirst");//插入到链表最前面

（4）public void addLast(E e)

看方法名就可以猜出来，这个方法会将传入的对象插入到链表的最后面，其实第一个add方法就是调用了这个方法，将对象插入到末尾

		LinkedList l=new LinkedList();
		l.add("test1");//默认插入到末尾
		l.add(1,"test2");//插入到链表中下标为1的地方
		
		l.addFirst("testfirst");//插入到链表最前面
		l.addLast("testlast");//插入到链表最后面