LinkedList链表是List接口的实现类，其内部结构为双向链表

内部结构

ListIterator接口

链表是一个有序集合(ordered collection)。LinkedList.add会把元素直接添加到链表尾部，无法添加到链表中间位置。而迭代器可以描述集合中位置信息，故这种依赖于位置的add方法可以通过迭代器实现。链表集合可以LinkedList.listIterator()方法获取获取实现了ListIterator接口的列表迭代器

interface ListIterator<E> extends Iterator<E>
{
    void add(E element);
    boolean hasNext();
    E next();
    boolean hasPrevious();
    E previous();
    void remove();
    void set(E element);
    ...
}

双向遍历

ListIterator迭代器提供了反向遍历链表的方法:hasPrevious()和 previous(),其和 next()方法机制一样，只不过是从后往前移动迭代器，并返回刚刚越过的元素

ListIterator.add方法　

该方法将始终在迭代器的前面位置添加该元素。而和迭代器是正向遍历next还是反向遍历previous到当前位置无关。

如下图所示，迭代器在#2位置时添加新元素 element 5后，会将其放置在#2前面。所以，如果此时调用next()向后遍历，将会返回 element2；如果调用previous向前遍历，则将会返回新插入的元素 element 5

ListIterator.remove方法

该方法始终删除刚刚越过的元素，所以其删除的元素和迭代器的状态(正向遍历/反向遍历)有关。如果之前调用了next方法，则将删除其前面的元素；如果之前调用了previous方法，则将删除其后面的元素

ListIterator.set方法

迭代器的set方法，用一个新元素来取代之前刚刚越过的元素(调用next、previous)

LinkedList中的方法

操作表头、表尾

LinkedList 还提供了专门操作表头、表尾的方法（因其实现了Deque接口）,因此可当作堆栈、队列、双端队列使用

void addFirst(E element);   // 添加元素到链表头部
void addLast(E element);    // 添加元素到链表尾部
E getFirst();              // 返回链表头部的元素
E getLast();               // 返回链表尾部的元素

使用实例:

// test List Frist/Last element Method
public static void LinkedListTest3()
{
    LinkedList<Integer> list = new LinkedList<>();

    for(int i=1; i<5; i++)
    {
        list.addFirst(i);
        list.addLast(-1 * i);
        System.out.println( "LinkedList: " + list.toString());
    }

    System.out.println( "First Element: " + list.getFirst() );
    System.out.println( "Last Element: " + list.getLast() );
}

输出如下:

LinkedList: [1, -1]
LinkedList: [2, 1, -1, -2]
LinkedList: [3, 2, 1, -1, -2, -3]
LinkedList: [4, 3, 2, 1, -1, -2, -3, -4]
First Element: 4
Last Element: -4

get、set方法

LinkedList中提供了2个看似按“索引”访问、修改链表元素的方法，但实际上链表不支持快速地随机访问，如果需要访问第n个元素，就必须从表开始遍历越过n-1个元素。所以该方法效率并不高

1 2	E get(int index); // 获取指定位置的元素 E set(int index, E element); // 用新元素取代指定位置的元素，并返回被取代的元素

特点

底层使用双向链表实现
排列有序
元素可重复
查找慢(无随机访问能力)，增加、删除元素快
线程不安全

xyZGHio

Java集合: LinkedList链表