Java容器(二):强大的LinkedList

时间:2021-04-06 17:21:54

一、强大的LinkedList

LinkedList是一个双向链表,而ArrayList是一个动态数组,这就造成了LinkedList不能够随机访问,查询时会遍历整个链表,因此在get和set时,不如ArrayList高效,但是在add和remove时,LinkedList则比较占优势(当然对于在list的最后增加或删除,两种List都一样)

LinkedList很强大,它有一系列特定的方法,使得它可以被用作栈,队列或双向队列。

这一系列方法:

  1. getFirst()和element():完全一样,获取表头但不移除,若List为空,抛出NoSuchElementException。
  2. peek():获取表头但不移除,若List为空,返回null。
  3. remove()和removeFirst():完全一样,获取表头并移除,若List为空,抛出NoSuchElementException。
  4. poll():获取表头并不移除,若List为空,返回null。
  5. removeLast():移除并返回列表最后一个元素,若List为空,抛出NoSuchElementException。
  6. add()和addLast(): 将一个元素插入队尾
  7. offer():将一个元素插入队尾(与Queue相关)

二、LinkedList用作栈

用作栈使用的方法:
pop和push 或 addFirst和removeFirst,两对是等效的

class Stack<T> {
private LinkedList<T> stack = new LinkedList<T>();
public void push(T t){//加入栈顶
stack.addFirst(t);
}
public T peek(){//获取栈顶元素
return stack.getFirst();
}
public T pop(){//弹出栈顶元素
return stack.removeFirst();
}
public boolean empty(){
return stack.isEmpty();
}
public String toString(){
return stack.toString();
}
}

public class TestStack {
public static void main(String[] args){
Stack<Character> stack = new Stack<>();
String s = "+u+n+c---+e+r+t";
for(int i = 0; i < s.length(); i++){//'+'则把后一个元素假如栈顶,'-'则弹出栈顶元素
char a = s.charAt(i);
if(a == '+'){
stack.push(s.charAt(++i));
System.out.println(stack.toString());
}else if(a == '-'){
Character character = stack.pop();
System.out.println(character);
}
}
}
}

结果为:

[u]
[n, u]
[c, n, u]
c
n
u
[e]
[r, e]
[t, r, e]

三、LinkedList用作队列

public class TestQueue {

public static<T> void printQueue(Queue<T> queue){
while(queue.peek() != null){
System.out.print(queue.poll() + " ");
}
}

public static void main(String[] args){
Random random = new Random(47);
Queue<Integer> queue = new LinkedList<>();
for(int i = 1; i < 10; i++){
queue.offer(random.nextInt(20));
}
System.out.println(queue);
printQueue(queue);
}
}

结果为:

[18, 15, 13, 1, 1, 9, 8, 0, 2]
18 15 13 1 1 9 8 0 2

四、何时使用ArrayList和LinkedList

ArrayList:需要进行大量的随机访问时
LinkedList:经常需要在表中间插入或删除元素时,并且需要各种Queue以及栈的行为时。

值得注意的问题

问题一:

我们经常看到这样的代码:

List<T> list = new ArrayList<T>();

至少我当时第一次使用的时候就会有疑问,为什么要上转型为List,好好地就用ArrayList不就好了吗?
这是为了后期的维护性。由于ArrayList和LinkedList都是继承自List,因此List list = new ArrayList()可以很方便的改为List list = new LinkedList();

ArrayList在随机访问方面很出色,LinkedList在中间插入和移除元素方面很出色。设想一下,假如一开始你在代码中使用ArrayList并没有上转为List,到了后期,你要对ArrayList中间进行大量的插入和移除元素,于是你想到了LinkedList在这方面比较出色,你想把ArrayList换成LinkedList。此时,你发现你已经大量地使用了ArrayList中的方法,如果直接换成LinkedList,整个程序就相当于要重构了。

但是如果你从一开始就使用List,换成LinkedList也就是直接修改ArrayList的事,因此两者都有List的方法。

问题二:

List.subList()的陷阱:

subList()所产生的列表幕后就是初始列表,对所有sublist返回的列表的操作都会反映到初始列表,就是说修改返回的列表,初始列表也会被修改。

List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9));
System.out.println(list);

List<Integer> sublist = list.subList(0, 5);//返回index从0-4的List
sublist.set(0, 9);
System.out.println(sublist);

System.out.println(list);

结果为:

[1, 2, 3, 4, 5, 6, 7, 8, 9]
[9, 2, 3, 4, 5]
[9, 2, 3, 4, 5, 6, 7, 8, 9]

可见第一个元素确实被修改了,如果指向修改返回的列表,而不影响初始列表,则应该这样做:

List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9));
System.out.println(list);

List<Integer> sublist2 = new ArrayList<>(list.subList(0, 5));
sublist2.set(0, 9);
System.out.println(sublist2);

System.out.println(list);

结果为:

[1, 2, 3, 4, 5, 6, 7, 8, 9]
[9, 2, 3, 4, 5]
[1, 2, 3, 4, 5, 6, 7, 8, 9]