首页 > 基础教程 > 集合框架 > LinkedList类

Java LinkedList类

LinkedList类是双向列表,列表中的每个节点都包含了对前一个和后一个元素的引用.，它和ArrayList一样实现了List接口，但是她执行插入和删除操作时比ArrayList更加高效，因为她是基于链表的，但同时也决定了她在随机访问方面要比ArrayList弱一点。

结构原理

LinkedList底层的数据结构是基于双向循环链表的，且头结点中不存放数据,如下：

LinkedList数据结构

既然是双向链表，那么必定存在一种数据结构——我们可以称之为节点，节点实例保存业务数据，前一个节点的位置信息和后一个节点位置信息，如下图所示：

LinkedList数据结构

构造方法

public LinkedList() {//生成空的链表
    header.next = header.previous = header;
}
public LinkedList(Collection<? extends E> c) {//复制构造函数
    this();
   addAll(c);
}

第一个构造方法不接受参数，将header实例的previous和next全部指向header实例（注意，这个是一个双向循环链表，如果不是循环链表，空链表的情况应该是header节点的前一节点和后一节点均为null），这样整个链表其实就只有header一个节点，用于表示一个空的链表。执行完构造函数后，header实例自身形成一个闭环，如下图所示：

Java LinkedList类

第二个构造方法接收一个Collection参数c，调用第一个构造方法构造一个空的链表，之后通过addAll将c中的元素全部添加到链表中。

私有属性

private transient Entry<E> header = new Entry<E>(null, null, null);
private transient int size = 0;

header是双向链表的头节点，它是双向链表节点所对应的类Entry的实例。Entry中包含成员变量： previous, next, element。其中，previous是该节点的上一个节点，next是该节点的下一个节点，element是该节点所包含的值。 size是双向链表中节点实例的个数。

方法

1. add(E e): 将指定元素添加到此列表的结尾。
2. add(int index, E element)：在此列表中指定的位置插入指定的元素。
3. addAll(Collection<? extends E> c)：添加指定 collection 中的所有元素到此列表的结尾，顺序是指定 collection 的迭代器返回这些元素的顺序。
4. addAll(int index, Collection<? extends E> c)：将指定 collection 中的所有元素从指定位置开始插入此列表。
5. AddFirst(E e): 将指定元素插入此列表的开头。
6. addLast(E e): 将指定元素添加到此列表的结尾。
7. clear()：从此列表中移除所有元素。
8. remove()：获取并移除此列表的头（第一个元素）。
9. remove(int index)：移除此列表中指定位置处的元素。
10. remove(Objec o)：从此列表中移除首次出现的指定元素（如果存在）。
11. removeFirst()：移除并返回此列表的第一个元素。
12. removeFirstOccurrence(Object o)：从此列表中移除第一次出现的指定元素（从头部到尾部遍历列表时）。
13. removeLast()：移除并返回此列表的最后一个元素。
14. removeLastOccurrence(Object o)：从此列表中移除最后一次出现的指定元素（从头部到尾部遍历列表时）。
15. get(int index)：返回此列表中指定位置处的元素。
16. getFirst()：返回此列表的第一个元素。
17. getLast()：返回此列表的最后一个元素。
18. indexOf(Object o)：返回此列表中首次出现的指定元素的索引，如果此列表中不包含该元素，则返回 -1。
19. lastIndexOf(Object o)：返回此列表中最后出现的指定元素的索引，如果此列表中不包含该元素，则返回 -1。

Iterator遍历数据

public ListIterator<E> listIterator(int index) {
    return new ListItr(index);
}

在LinkedList中提供了获取ListItr对象的方法：listIterator(int index)，该方法只是简单的返回了一个ListItr对象。LinkedList中还有通过集成获得的listIterator()方法，该方法只是调用了listIterator(int index)并且传入0。

public Iterator<E> descendingIterator() {
   return new DescendingIterator();
}

LinkedList还有一个提供Iterator的方法：descendingIterator()。该方法返回一个DescendingIterator对象。DescendingIterator是LinkedList的一个内部类。

例子

public static void main(String[] args) {
    List < String > a = new LinkedList < >();
    a.add("Amy");
    a.add("Carl");
    a.add("Erica");

    List < String > b = new LinkedList < >();
    b.add("Bob");
    b.add("Doug");
    b.add("Frances");
    b.add("Gloria");

    ListIterator < String > aIter = a.listIterator();
    Iterator < String > bIter = b.iterator();

    while (bIter.hasNext()) {
        if (aIter.hasNext()) aIter.next();
        aIter.add(bIter.next());
    }
    System.out.println(a);

    bIter = b.iterator();
    while (bIter.hasNext()) {
        bIter.next();
        if (bIter.hasNext()) {
            bIter.next();
            bIter.remove();
        }
    }
    System.out.println(b);

    a.removeAll(b);

    System.out.println(a);
}