简介：
LinkedList是List接口的实现类【存储结构是链表，特点：每个元素分配的空间不必连续、插入和删除元素时速度非常快、但访问元素的速度较慢】
ArrayList 也是List接口的实现类【存储结构是线性表】
LinkedList 是一个双向链表，当数据量很大或者操作很频繁的情况下，添加和删除元素时具有比ArrayList更好的性能。但在元素查询和修改方便要弱于ArrayList。LinkedList类每个结点用内部类Node表示，LInkedList通过first和last引用分别只想链表的第一个和最后一个元素，当链表为空时，first和last都为NULL值。LinkedList数据结构如下图所示：
//存储对象的结构Node,LinkedList的内部类
private static class Node<E>{
E item;
Node<E> next;//指向下一个节点
Node<E> prev;//指向上一个节点
Node(Node<E> prev,E element,Node<E> next){
this.item = element;
this.next = next;
this.prev = prev;
}
}
Node节点一共有三个属性：item代表节点值，prev代表节点的前一个节点，next代表节点的后一个节点。每个节点都有一个前驱和后继结点，并且在LinkedList中也定义了两个变量分别指向链表的第一个和最后一个节点。
transient Node<E> first;
transient Node<E> last;
1、添加元素到LinkedList
LinkedList提供了多个添加元素的方法；
添加元素到LinkedList示例代码如下：
package addDemo; import java.util.LinkedList; public class LinkedListAddDemo{ public static void main(String[] args){ LinkedList<String> linkedList = new LinkedList<>(); linkedList.add("first"); linkedList.add("second"); linkedList.add("third"); System.out.println(linkedList); linkedList.addFirst("addFirst"); System.out.println(linkedList); linkedList.addLast("addLast"); System.out.println(linkedList); linkedList.add(2,"addByIndex"); System.out.println(linkedList); } }
输出结果如下：
从LinkedList中删除元素
LinkedList提供了多个删除元素的方法：
从LinkedList删除元素示例代码如下：
import java.util.LinkedList; public class test{ public static void main(String[] args) { LinkedList<String> linkedList = new LinkedList<>(); linkedList.add("first"); linkedList.add("second"); linkedList.add("escond"); linkedList.add("third"); linkedList.add("four"); linkedList.add("five"); System.out.println(linkedList); linkedList.remove(); System.out.println("remove:"+linkedList); linkedList.remove("second"); System.out.println("remove(Object):"+linkedList); linkedList.remove("six"); System.out.println("remove(Object) not exist:"+linkedList); linkedList.remove(2); System.out.println("remove(index):"+linkedList); linkedList.removeFirst(); System.out.println("removeFirst:"+linkedList); linkedList.removeLast(); System.out.println("removeLast:"+linkedList); System.out.println("------------------------------------"); linkedList.clear(); linkedList.add("first"); linkedList.add("second"); linkedList.add("escond"); linkedList.add("third"); linkedList.add("four"); linkedList.add("five"); System.out.println(linkedList); linkedList.removeFirstOccurrence("first"); System.out.println("removeFirstOccurrence"+linkedList); linkedList.removeLastOccurrence("first"); System.out.println("removeLastOccurrence"+linkedList); } }
输出结果如下：
从LinkedList获取元素示例代码如下：
LinkedList提供了多个获取元素的方法：
import java.util.LinkedList; public class test{ public static void main(String[] args) { LinkedList<String> linkedList = new LinkedList<>(); linkedList.add("first"); linkedList.add("second"); linkedList.add("escond"); linkedList.add("third"); linkedList.add("four"); linkedList.add("five"); System.out.println(linkedList); linkedList.get(3); System.out.println("get(index)"+linkedList.get(3)); linkedList.getLast(); System.out.println("getLast"+linkedList.getLast(); linkedList.getFirst(); System.out.println("getFirst"+linkedList.getFirst(); } }
输出结果如下图所示：
LInkedList的遍历方法
LinkedList可以通过迭代器、foreach语句、for循环语句等方法遍历集合的所有元素。
import java.util.Iterator; import java.util.LinkedList; public class test{ public static void main(String[] args) { LinkedList<Integer> linkedList = new LinkedList<>(); for(int i=0;i<10000;i++){ linkedList.addLast(i); } //通过一般for循环来遍历LinkedList long start = System.currentTimeMillis(); int size = linkedList.size(); for(int i=0;i<size;i++){ linkedList.get(i); } long end = System.currentTimeMillis(); long total = end-start; System.out.println("byCommonFor-------->"+total+" ms"); //通过迭代器来遍历LinkedList start = System.currentTimeMillis(); for(Iterator iter = linkedList.iterator();iter.hasNext();) iter.next(); end = System.currentTimeMillis(); total = end - start; System.out.println("byIterator--------->"+total+" ms"); //通过foreach来遍历LinkedList start = System.currentTimeMillis(); for (Integer integer : linkedList) ; end = System.currentTimeMillis(); total = end-start; System.out.println("byForeach--------->"+total+" ms"); } }
输出结果如下图所示：
LInkedList 存储元素的数据结构是双向链表结构，由存储元素的结点连接而成，每一个节点都包含前一个节点的引用，后一个节点的引用和节点存储的值。当一个新节点插入时，只需要修改其中保持先后关系的节点的引用即可。
原文：https://www.cnblogs.com/zyc19910109/p/12558420.html
