Java容器（一）：LinkedList

水深无声 2022-05-16 01:49 155阅读 0赞

# **一、强大的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]