LinkedList集合的底层原理
- 基于双链表实现的。
双链表在数据结构中涉及到，我们简单看一遍单向链表和双向链表的结构：
- 特点：查询慢，增删相对较快，但对首尾元素进行增删改查的速度是极快的。
特有方法
LinkedList新增了：很多首尾操作的特有方法
下面将通过LinkedList的两个应用场景来使用这些特有方法。
LinkedList的应用场景之一：用来设计队列
队列
- 队列的特点是：先进先出，后进后出
只是在首尾增删元素，用LinkedList来实现很合适！
import java.util.ArrayList; import java.util.LinkedList; import java.util.List; public class ListDemo2 { public static void main(String[] args) { //1.创建一个队列 LinkedList<String> queue = new LinkedList<>(); queue.addLast("第一号人"); //[] <- 第一号人 queue.addLast("第二号人"); //[第一号人] <- 第二号人 queue.addLast("第三号人"); //[第一号人,第二号人] <- 第三号人 queue.addLast("第四号人"); //...... System.out.println(queue); //出队 System.out.println(queue.removeFirst()); // <- [第一号人, 第二号人, 第三号人, 第四号人] System.out.println(queue.removeFirst()); //第一号人 <- [ 第二号人, 第三号人, 第四号人] System.out.println(queue.removeFirst()); //第一号人 第二号人 <- [ 第三号人, 第四号人] System.out.println(queue); //第一号人 第二号人 第三号人, <- [第四号人] } }
运行结果：
LinkedList的应用场景之一：用来设计栈
栈
- 栈的特点：后进先出，先进后出
只是在首部增删元素，同样地，用LinkedList来实现。
- 数据进入栈模型的过程称为：压/进栈（push)
- 数据离开栈模型的过程称为：弹/出栈（pop)
所以，原本我们应该使用的addFirst可以用push代替；removeFirst可以用pop代替。
import java.util.ArrayList; import java.util.LinkedList; import java.util.List; public class ListDemo2 { public static void main(String[] args) { //2.创建一个栈对象 LinkedList<String> stack = new LinkedList<>(); //压栈 stack.push("第一颗子弹"); //第一颗子弹 -> [] stack.push("第二颗子弹"); //第二颗子弹 -> [第一颗子弹] stack.push("第三颗子弹"); //第三颗子弹 -> [第二颗子弹, 第一颗子弹] stack.push("第四颗子弹"); //第四颗子弹 -> [第三颗子弹, 第二颗子弹, 第一颗子弹] System.out.println(stack); //[第四颗子弹, 第三颗子弹, 第二颗子弹, 第一颗子弹] //出栈 System.out.println(stack.pop()); // <- [第四颗子弹, 第三颗子弹, 第二颗子弹, 第一颗子弹] System.out.println(stack.pop()); // 第四颗子弹 <- [第三颗子弹, 第二颗子弹, 第一颗子弹] System.out.println(stack); // [第二颗子弹, 第一颗子弹] } }
运行结果：
END
