LinkedList的学习笔记

1、LinkedList的简单介绍

  1. LinkedList是双向链表(Jdk1.8)

  2. LinkedList是线程不安全的

  3. LikedList底层由Node节点构成

    1. private static class Node<E> {
    2.  E item;
    3.  Node<E> next;
    4.  Node<E> prev;
    6.  Node(Node<E> prev, E element, Node<E> next) {
    7.      this.item = element;
    8.      this.next = next;
    9.      this.prev = prev;
    10.  }
    11. }


因为同同时存在前驱节点和后继节点，所以LinkedList是双向的链表

  1. LinkedList对于添加和删除操作花费时间近似为常数

  2. LinkedList对数据的查找时间花费为O(n)

Tips

LinkedList的使用范围

①需要多次添加或删除的数据情况

②不需要经常访问末端数据

③数据不需要连续存储

2、LinkedList的构造器

LinkedList提供了两种构造器

①public LinkedList()

  1. public LinkedList() {
  2. }

基础的空构造器

②public LinkedList(Collection<? extends E> c)

  1. public LinkedList(Collection<? extends E> c) {
  2.     this();
  3.     addAll(c);
  4. }

创建一个LinkedList，保护Collection中的全部元素

c为一个实现过Collection接口且数据类型和LinkedList一样的数据类型

3、LinkedList的继承关系

LinkedList的学习笔记 - 图1

首先根据继承关系，一层一层推到出LinkedList的继承情况

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

①首先继承了AbstractSequentialList接口

②实现了 List, Deque, Cloneable, java.io.Serializable等接口

Tips

1、Cloneable接口的作用

答：Cloneable接口也是一个标记性接口，实现这个接口代表着你可被clone，能够使用Object.clone()方法

  1. public interface Cloneable {
  2.     //接口主体为空
  3. }

2、什么是序列化

答：

把对象转换为字节序列的过程称为对象的序列化。
把字节序列恢复为对象的过程称为对象的反序列化。
对象的序列化主要有两种用途：
1） 把对象的字节序列永久地保存到硬盘上，通常存放在一个文件中；
2） 在网络上传送对象的字节序列。

简单来说，就是LinkedList可以保存在你的硬盘上

3、什么是List接口

我们打开List接口的源码

  1. public interface List<E> extends Collection<E>

一上来展示的就是List接口继承与Collection接口，那我们再翻到Collection接口

  1. public interface Collection<E> extends Iterable<E>

这时我们发现，怎么还有接口，那么继续往上翻

  1. public interface Iterable<T>

这下终于没有接口了，舒服了。。。。

这时我们发现 Iterable迭代器接口是ArrayList的顶级父类，这三个接口继承到底让List接口获得了那些功能呢

①Iterable接口

  1. public interface Iterator<E> {
  2.      /**
  3.      * Returns an iterator over elements of type {@code T}.
  4.      *
  5.      * @return an Iterator.
  6.      */
  7.     Iterator<T> iterator();
  9.     // 1.8新增了两个方法，暂不讨论
  10. }

上面的代码说明表示会返回一个Iterator类型的变量

Iterator是迭代器接口，这就表明获得了一个迭代器

所以说，Iterable使List接口获得了迭代器功能

②Collection接口

  1. public interface Collection<E> extends Iterable<E> {
  2.     // Query Operations
  4.     int size();
  6.     boolean isEmpty();
  8.     boolean contains(Object o);
  10.     Iterator<E> iterator();
  12.     <T> T[] toArray(T[] a);
  14.     boolean add(E e);
  16.     boolean remove(Object o);
  18.     boolean containsAll(Collection<?> c);
  20.     boolean addAll(Collection<? extends E> c);
  22.     boolean removeAll(Collection<?> c);
  24.     boolean retainAll(Collection<?> c);
  26.     void clear();
  28.     boolean equals(Object o);
  30.     int hashCode();
  32. }

Collection是List和set接口的父类，他提供了操作数据的基本方法名称

由此可知Collection使得List获得了基本操作方法的名称

③List接口

List接口继承了上述两个接口的所有特性，但是List接口代表着的是有序的Collection接口

即它用某种特定的插入顺序来维护元素顺序。用户可以对列表中每个元素的插入位置进行精确地控制，同时可以根据元素的整数索引（在列表中的位置）访问元素，并搜索列表中的元素

4、什么是Deque接口

同样，我们打开Deque接口源码

  1. public interface Deque<E> extends Queue<E>

我们发现Deque接口是继承Queue接口的

  1. public interface Queue<E> extends Collection<E>

现在我们发现Queue接口又继承到了我们熟悉的Collection接口

学过数据结构的同学看到Queue接口肯定就会明白是队列的意思

那么Deque接口是什么含义呢

  1. public interface Deque<E> extends Queue<E> {
  3.     void addFirst(E e);
  5.     void addLast(E e);
  7.     boolean offerFirst(E e);
  9.     boolean offerLast(E e);
  11.     E removeFirst();
  13.     E removeLast();
  15.     // ..........

我们列举其中一些函数，通过函数名可以发行，Deque接口实际上是可以直接在队头和队尾操作的队列

队列这种数据结构必须要满足，队头进队，队尾出队这种结构

但是Deque既可以在队头入队又可以在队头出队，这就代表着Deque是一个双向队列

5、什么是AbstractSequentialList抽象类

我们先查看AbstractSequentialList抽象类的源码

  1. public abstract class AbstractSequentialList<E> extends AbstractList<E>

还没结束，我们继续往上翻

  1. public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E>

到这里我们发现了一个我们熟悉的List接口，但是还没结束，继续翻

  1. public abstract class AbstractCollection<E> implements Collection<E>

到这里呢，我们又见到了我们熟悉的Collection接口

那么问题来了，我们为什么要创建一个AbstractCollection抽象类呢？

在此呢，我们需要复习几个概念

①当一个类实现某一个接口时，必须要实现这个接口的所有方法

②当一个类继承某一个类时，可以重写也可以不重写父类的方法

③抽象类是具有抽象方法的类，有抽象方法的类一定是抽象类，没有抽象方法的类也可能是抽象类

④抽象类无法创建实例，必须被继承后重写抽象方法

答：当我们需要实现Collection接口时，我们必须重写Collection接口中的全部方法，而AbstractCollection则帮我们实习了大多数的方法，我们只需要重写其中的几个方法，即可完成Collection接口的使用

未实现的方法为

  1. public abstract Iterator<E> iterator();
  3. public abstract int size();

同理

  1. public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E>

在AbstractList抽象类中，实现了List的大多数方法，只剩下几个必须要子类实现的函数没有实现

比如add(), set(),remove(),还有size()

  1. public void add(int index, E element) {
  2.     throw new UnsupportedOperationException();
  3. }

如不重写add()方法就会抛出异常

那么到目前为止，我们发现了AbstractList抽象类继承了AbstractCollection抽象类

①AbstractCollection抽象类完成了Collection接口的基本方法但还保留了抽象方法等待子类去重写实现

②AbstractList抽象类进一步完善了AbstractCollection抽象类的方法，使得其变成了表结构，也就是说数据开始有序起来，在几个关键函数中AbstractList强制子类重写方法不然会爆出异常

好了，到目前为止我们已经了解到AbstractList抽象类了，那么我们继续往下推进

  1. public abstract class AbstractSequentialList<E> extends AbstractList<E> {

AbstractSequentialList继承了AbstractList，它是一个基于迭代器的抽象类，它只实现了最基本的增删改查方法，其中的所有的方法都需要根据迭代器来实现。能看出如果继承这个类，那么一定是和链表相关的类，如果是数组的话，也不能用效率这么低的Iterator来实现增删改查。

学过链表这一数据结构的同学肯定能明白，链表的查找就是通过节点一个一个向后推进的查找，和迭代器的含义差不多

  1. public abstract ListIterator<E> listIterator(int index);

值得注意的是AbstractSequentialList抽象类中抽象了一个listIterator方法

返回值为一个表迭代器ListIterator

我们打开ListIterator的源码

  1. public interface ListIterator<E> extends Iterator<E> {
  3.     boolean hasNext();
  5.     E next();
  7.     boolean hasPrevious();
  9.     E previous();
  11.     int nextIndex();
  13.     int previousIndex();
  15.     void remove();
  17.     void add(E e);
  18. }

根据方法名，我们很容易判断出这是一个双向的迭代器，可以向前也可以向后迭代

还记得我们上面所说的为什么LinkedList是双向的链表，虽然ListIterator和双向链表之间不是is-a的关系

但是ListIterator的存在保证了双向链表的存在，毕竟节点是需要查找

而且既然名字为ListIterator，那么说明只有实现List接口的类才可以继承使用这个双向迭代器