LinkedList集合

ArrayList集合在查询元素时速度很快，但在增删元素时效率较低，为了克服这种局限性，可以使用List接口的另一个实现类LinkedList。LinkedList集合内部包含有两个Node类型的first和last属性维护一个双向循环链表，在链表中的每一个元素都使用引用的方式来记住它的前一个元素和后一个元素，从而可以将所有的元素彼此连接起来。当插入一个新元素时，只需要修改元素之间的这种引用关系即可，删除一个节点也是如此。正因为这样的存储结构，所以LinkedList集合对于元素的增删操作表现出很高的效率，LinkedList集合添加元素和删除元素的过程如图1所示。

图1 双向循环链表结构图

在图1中，通过两张图描述了LinkedList集合新增元素和删除元素的过程。其中，左图为新增一个元素，图中的元素1和元素2在集合中彼此为前后关系，在它们之间新增一个元素时，只需要让元素1记住它后面的元素是新元素，让元素2记住它前面的元素为新元素就可以了。右图为删除元素，要想删除元素1和元素2之间的元素3，只需要让元素1与元素2变成前后关系就可以了。

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

表1 LinkedList中的特有方法

表1中，列出的方法主要针对集合中的元素进行增加、删除和获取操作，接下来通过一个案例来学习LinkedList中常用方法的使用，如文件1所示。

文件1 Example02.java

 1    import java.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对元素进行增删操作是非常便捷的。