Java集合: LinkedList链表

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

abstract.jpeg

内部结构

figure 1.jpeg

ListIterator接口

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

1
2
3
4
5
6
7
8
9
10
11
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()方法机制一样,只不过是从后往前移动迭代器,并返回刚刚越过的元素

figure 2.jpeg

ListIterator.add方法 

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

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

figure 3.jpeg

ListIterator.remove方法

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

figure 4.jpeg

ListIterator.set方法

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

LinkedList中的方法

操作表头、表尾

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

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

使用实例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 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() );
}

输出如下:

1
2
3
4
5
6
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); // 用新元素取代指定位置的元素,并返回被取代的元素

特点

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