LinkedList的结构特点

ArrayList在查找元素这件事上向来很利索，但一旦涉及新增、删除，效率就没那么理想了。

要补上这块短板，通常会用到List接口的另一个实现类LinkedList。

LinkedList内部有两个Node类型的属性，分别是first和last，用来维护一个双向循环链表。

链表里的每个元素，都会通过引用记录自己的前一个元素和后一个元素。这样一来，所有元素就能首尾关联、串联成链。

插入新元素时，本质上只需要调整这些元素之间的引用关系。

删除节点时，处理方式也是一样。

也正因为这种存储结构，LinkedList在元素的增删操作上通常表现得更高效。LinkedList集合添加元素和删除元素的过程如图1所示。

图1 双向循环链表结构图

图1所示的增删过程

图1用两张示意图，把LinkedList在新增和删除元素时的处理过程讲得很直观。

左边这张图展示的是插入一个新元素。原本元素1和元素2在集合里互为前后节点。

如果要在它们中间插入一个新元素，其实只需要调整两处关联即可。

• 让元素1记录它后面的节点变成这个新元素
• 让元素2记录它前面的节点也是这个新元素

右边这张图对应的是删除元素。

如果要移除位于元素1和元素2之间的元素3，那么直接让元素1和元素2重新建立前后关系，就完成了删除操作。

LinkedList中的特有方法

LinkedList集合除了从接口Collection和List中继承并实现了集合操作方法外，还专门针对元素的增删操作定义了一些特有的方法，如表1所示。

表1 LinkedList中的特有方法

表1中，列出的方法主要针对集合中的元素进行增加、删除和获取操作。

接下来通过一个案例，学习LinkedList中常用方法的使用，如文件1所示。

案例：LinkedList常用方法演示

文件1 Example02.ja va

 1    import ja va.util.LinkedList;
 2    public class Example02 {
 3        public static void main(String[] args) {
 4              // 创建LinkedList集合
 5            LinkedList link = new LinkedList();  
 6            // 1、添加元素
 7            link.add("stu1");
 8            link.add("stu2");
 9             System.out.println(link);   // 输出集合中的元素
 10            link.offer("offer");         // 向集合尾部追加元素
 11            link.push("push");           // 向集合头部添加元素
 12            System.out.println(link);   // 输出集合中的元素
 13            // 2、获取元素
 14             Object object = link.peek();//获取集合第一个元素
 15            System.out.println(object); // 输出集合中的元素
 16            // 3、删除元素
 17            link.removeFirst();          // 删除集合第一个元素
 18            link.pollLast();              // 删除集合最后一个元素
 19            System.out.println(link);
 20        }
 21    }

运行结果如图2所示。

图2 运行结果

案例执行过程说明

文件1中，首先创建了一个LinkedList集合。

接着，分别使用add()、offer()、push()方法向集合中插入元素。

然后，使用peek()方法获取了集合的第一个元素。

最后，分别使用removeFirst()、pollLast()方法将集合中指定位置的元素移除。

这样就完成了元素的增、查、删操作。

由此可见，使用LinkedList对元素进行增删操作是非常便捷的。

《夸克》非常好用的免费AI浏览器

下载APP查看