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);
} 

版权声明:本文为JAVASCHOOL原创文章,未经本站允许不得转载。