Java中的linkedList类及与ArrayList的异同

继承实现关系

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");//插入到链表最后面

2.删除元素

（1）public E remove() 

删除并返回第一个元素

（2）public E remove(int index)

删除指定下标处的元素。

（3）public boolean remove(Object o)

删除传入的元素，返回是否成功，成功为 true，失败为 false。

（4）public E removeFirst()

删除并返回第一个元素。

（5）public E removeLast()

删除并返回最后一个元素。

（6）public void clear()

清空链表。

还有很多常用的方法这里就不再阐述了，等用到的时候再去搜，不必要马上就记住，知道了LinkedList的特性就好了，在了解他和ArrayList的异同。