Java LinkedList
LinkedList 的双向链表结构、首尾操作与作为栈/队列使用。
创建 LinkedList
new LinkedList<>() starts empty and supports add / get like ArrayList. The difference is the backing structure: indexed access walks the chain, so get(i) inside a loop degrades to O(n²).
import java.util.LinkedList;
public class LinkedListBasic {
public static void main(String[] args) {
LinkedList<String> list = new LinkedList<>();
list.add("a");
list.add("b");
System.out.println(list);
System.out.println(list.get(1));
System.out.println(list.size());
System.out.println(list.getFirst());
System.out.println(list.getLast());
}
}[a, b]
b
2
a
b首尾操作
addFirst / addLast insert at the ends and removeFirst / removeLast delete there, all O(1) — the case where a linked list beats an array.
import java.util.LinkedList;
public class LinkedListEnds {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.addLast(1);
list.addLast(2);
list.addFirst(0);
System.out.println(list);
System.out.println(list.removeFirst());
System.out.println(list.removeLast());
System.out.println(list);
}
}[0, 1, 2]
0
2
[1]作为栈和队列
push / pop give stack semantics at the head, while offer / poll give queue semantics (tail in, head out). In single-threaded code ArrayDeque is faster; LinkedList is mostly used as a List.
import java.util.LinkedList;
public class LinkedListStackQueue {
public static void main(String[] args) {
LinkedList<Integer> stack = new LinkedList<>();
stack.push(1);
stack.push(2);
System.out.println(stack.pop());
LinkedList<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
System.out.println(queue.poll());
System.out.println(queue);
}
}2
1
[2]创建 LinkedList
new LinkedList<>() 创建空链表，可以像 ArrayList 一样 add / get。区别在底层：链表按索引访问要逐个走，所以 get(i) 在循环里用会退化成 O(n²)。
import java.util.LinkedList;
public class LinkedListBasic {
public static void main(String[] args) {
LinkedList<String> list = new LinkedList<>();
list.add("a");
list.add("b");
System.out.println(list);
System.out.println(list.get(1));
System.out.println(list.size());
System.out.println(list.getFirst());
System.out.println(list.getLast());
}
}[a, b]
b
2
a
b首尾操作
addFirst / addLast 在两端插入，removeFirst / removeLast 在两端删除，都是 O(1)。这正是链表相对数组的优势场景。
import java.util.LinkedList;
public class LinkedListEnds {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.addLast(1);
list.addLast(2);
list.addFirst(0);
System.out.println(list);
System.out.println(list.removeFirst());
System.out.println(list.removeLast());
System.out.println(list);
}
}[0, 1, 2]
0
2
[1]作为栈和队列
push / pop 提供栈语义（操作头部），offer / poll 提供队列语义（尾进头出）。但单线程场景下 ArrayDeque 更快，LinkedList 更多是用作 List。
import java.util.LinkedList;
public class LinkedListStackQueue {
public static void main(String[] args) {
LinkedList<Integer> stack = new LinkedList<>();
stack.push(1);
stack.push(2);
System.out.println(stack.pop());
LinkedList<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
System.out.println(queue.poll());
System.out.println(queue);
}
}2
1
[2]