LinkedList

• LinkedList底层的数据结构是基于双向循环链表
• LinkedList是有序的、可重复的、非同步的
• LinkedList最经常使用的两种数据结构：栈和队列

创建对象

LinkedList list = new LinkedList();

添加元素

list.push("wei");
list.push("ijunfu");
list.push(12);
list.push(17);

list.add(29); 

push和add的区别：

• push：将元素添加到栈顶，等同于addFirst

通过上述源码可知，push内部调用了addFirst，而addFirst调用了linkFirst。总之，真正实现将元素添加到栈顶的还是linkFirst。

• add：将元素添加到队尾，等同于addLast

通过以上源码可知，add内部调用了linkLast，真正实现元素添加的是linkLast。

获取栈顶（队首）元素

在LinkedList中，获取栈顶（队首）元素有三种方式：pop、poll、peek。

list.pop()
list.poll()
list.peek()

pop、poll、peek三者的区别：

• pop和poll，删除并返回栈顶（队首）元素，而peek，仅返回栈顶元素
• pop栈结构，后进先出，删除并返回第一个元素（栈顶），栈顶为null值时抛出异常
• poll是队列结构，删除并返回第一个元素（队首），队首为null时，返回null

其它示例，可参考ArrayList也就如此了，都是继承自List，使用方法也有较多的相似，这里仅介绍与ArrayList的不同之处。

LinkedList和ArrayList的区别

• 时间复杂度

对于随机访问，ArrayList通过索引快速定位元素位置，而LinkedList需要多列表中元素挨个查找，所以ArrayList快于LinkedList;

对于删除插入操作，ArrayList需要对数组重新排序，而在数组填满时，需要将所有的数据重新装入一个新的数组；LinkedList只需要添加一项Entry对象，所以LinkedList快于ArrayList。

• 空间复杂度

LinkedList需要更多的内存，因为ArrayList的每个索引的位置是实际的数据，而LinkedList中的每个节点存储的是实际的数据和前后节点的位置。

ArrayList效率

ArrayList list = new ArrayList();
long start = System.currentTimeMillis();
for(int i=0; i<50000; i++) {
  list.add(i);
}
long tmp = System.currentTimeMillis();
for(int i=0; i<50000; i++) {
  list.get(i);
}
long end = System.currentTimeMillis();

Duration duration1 = Duration.ofMillis(tmp - start);
System.out.printf("插入耗时：\n\t相当于：%dms \n\t相当于：%ds \n\t相当于：%dm \n\t相当于：%dh\n", duration1.toMillis(), duration1.toSeconds(), duration1.toMinutes(), duration1.toHours());

Duration duration2 = Duration.ofMillis(end - tmp);
System.out.printf("获取耗时：\n\t相当于：%dms \n\t相当于：%ds \n\t相当于：%dm \n\t相当于：%dh", duration2.toMillis(), duration2.toSeconds(), duration2.toMinutes(), duration2.toHours());

LinkedList效率：

LinkedList list = new LinkedList();
long start = System.currentTimeMillis();
for(int i=0; i<50000; i++) {
  list.add(i);
}
long tmp = System.currentTimeMillis();
for(int i=0; i<50000; i++) {
  list.get(i);
}
long end = System.currentTimeMillis();

Duration duration1 = Duration.ofMillis(tmp - start);
System.out.printf("插入耗时：\n\t相当于：%dms \n\t相当于：%ds \n\t相当于：%dm \n\t相当于：%dh\n", duration1.toMillis(), duration1.toSeconds(), duration1.toMinutes(), duration1.toHours());

Duration duration2 = Duration.ofMillis(end - tmp);
System.out.printf("获取耗时：\n\t相当于：%dms \n\t相当于：%ds \n\t相当于：%dm \n\t相当于：%dh", duration2.toMillis(), duration2.toSeconds(), duration2.toMinutes(), duration2.toHours());

以上数据，不同电脑运行后结果可能会稍有不同，但结果相似，即LinkedList获取元素较慢，效率明显低于ArrayList。

如果您有其它的测试案例，欢迎留言交流！！！