1. LinkedList简介
LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
LinkedList 实现 List 接口，能对它进行队列操作。
LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。
LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
LinkedList 是非同步的。
LinkedList的本质是双向链表。
(01) LinkedList继承于AbstractSequentialList，并且实现了Dequeue接口。
(02) LinkedList包含两个重要的成员：header 和 size。
header是双向链表的表头，它是双向链表节点所对应的类Entry的实例。Entry中包含成员变量： previous, next, element。其中，previous是该节点的上一个节点，next是该节点的下一个节点，element是该节点所包含的值。size是双向链表中节点的个数。
java.lang.Object ↳ java.util.AbstractCollection<E> ↳ java.util.AbstractList<E> ↳ java.util.AbstractSequentialList<E> ↳ java.util.LinkedList<E> public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable {}
2. LinkedList构造函数
// 默认构造函数 LinkedList() // 创建一个LinkedList，保护Collection中的全部元素。 LinkedList(Collection<? extends E> collection)
3. API
LinkedList的API boolean add(E object) void add(int location, E object) boolean addAll(Collection<? extends E> collection) boolean addAll(int location, Collection<? extends E> collection) void addFirst(E object) void addLast(E object) void clear() Object clone() boolean contains(Object object) Iterator<E> descendingIterator() E element() E get(int location) E getFirst() E getLast() int indexOf(Object object) int lastIndexOf(Object object) ListIterator<E> listIterator(int location) boolean offer(E o) boolean offerFirst(E e) boolean offerLast(E e) E peek() E peekFirst() E peekLast() E poll() E pollFirst() E pollLast() E pop() void push(E e) E remove() E remove(int location) boolean remove(Object object) E removeFirst() boolean removeFirstOccurrence(Object o) E removeLast() boolean removeLastOccurrence(Object o) E set(int location, E object) int size() <T> T[] toArray(T[] contents) Object[] toArray()
4. 遍历方式
1）迭代器
for (Iterator iter=list.iterator(); iter.hasNext(); ) iter.next();
2）快速随机访问
int size=list.size(); for(int i=0; i<size;i++){ list.get(i); }
3）for循环
for( Integer integ:list) ;
4）pollFirst() 遍历LinkedList
while(list.pollFirst() !=null) ;
5）pollLast() 遍历
while(list.pooLast() !=null ) ;
6)通过removeFirst遍历
try { while(list.removeFirst()！=null) ; } catch (NoSuchElementException e) { }
7）通过removeLast遍历
try{ while(list.removeLast() != null ) ; } catch (NoSuchElementException e) { }
5.例子
import java.util.List; import java.util.Iterator; import java.util.LinkedList; import java.util.NoSuchElementException; public class LinkedListTest { public static void main(String[] args) { // 测试LinkedList的API testLinkedListAPIs() ; // 将LinkedList当作 LIFO(后进先出)的堆栈 useLinkedListAsLIFO(); // 将LinkedList当作 FIFO(先进先出)的队列 useLinkedListAsFIFO(); } /* * 测试LinkedList中部分API */ private static void testLinkedListAPIs() { String val = null; //LinkedList llist; //llist.offer("10"); // 新建一个LinkedList LinkedList llist = new LinkedList(); //---- 添加操作 ---- // 依次添加1,2,3 llist.add("1"); llist.add("2"); llist.add("3"); // 将“4”添加到第一个位置 llist.add(1, "4"); System.out.println(" Test "addFirst(), removeFirst(), getFirst()""); // (01) 将“10”添加到第一个位置。 失败的话，抛出异常！ llist.addFirst("10"); System.out.println("llist:"+llist); // (02) 将第一个元素删除。 失败的话，抛出异常！ System.out.println("llist.removeFirst():"+llist.removeFirst()); System.out.println("llist:"+llist); // (03) 获取第一个元素。 失败的话，抛出异常！ System.out.println("llist.getFirst():"+llist.getFirst()); System.out.println(" Test "offerFirst(), pollFirst(), peekFirst()""); // (01) 将“10”添加到第一个位置。 返回true。 llist.offerFirst("10"); System.out.println("llist:"+llist); // (02) 将第一个元素删除。 失败的话，返回null。 System.out.println("llist.pollFirst():"+llist.pollFirst()); System.out.println("llist:"+llist); // (03) 获取第一个元素。 失败的话，返回null。 System.out.println("llist.peekFirst():"+llist.peekFirst()); System.out.println(" Test "addLast(), removeLast(), getLast()""); // (01) 将“20”添加到最后一个位置。 失败的话，抛出异常！ llist.addLast("20"); System.out.println("llist:"+llist); // (02) 将最后一个元素删除。 失败的话，抛出异常！ System.out.println("llist.removeLast():"+llist.removeLast()); System.out.println("llist:"+llist); // (03) 获取最后一个元素。 失败的话，抛出异常！ System.out.println("llist.getLast():"+llist.getLast()); System.out.println(" Test "offerLast(), pollLast(), peekLast()""); // (01) 将“20”添加到第一个位置。 返回true。 llist.offerLast("20"); System.out.println("llist:"+llist); // (02) 将第一个元素删除。 失败的话，返回null。 System.out.println("llist.pollLast():"+llist.pollLast()); System.out.println("llist:"+llist); // (03) 获取第一个元素。 失败的话，返回null。 System.out.println("llist.peekLast():"+llist.peekLast()); // 将第3个元素设置300。不建议在LinkedList中使用此操作，因为效率低！ llist.set(2, "300"); // 获取第3个元素。不建议在LinkedList中使用此操作，因为效率低！ System.out.println(" get(3):"+llist.get(2)); // ---- toArray(T[] a) ---- // 将LinkedList转行为数组 String[] arr = (String[])llist.toArray(new String[0]); for (String str:arr) System.out.println("str:"+str); // 输出大小 System.out.println("size:"+llist.size()); // 清空LinkedList llist.clear(); // 判断LinkedList是否为空 System.out.println("isEmpty():"+llist.isEmpty()+" "); } /** * 将LinkedList当作 LIFO(后进先出)的堆栈 */ private static void useLinkedListAsLIFO() { System.out.println(" useLinkedListAsLIFO"); // 新建一个LinkedList LinkedList stack = new LinkedList(); // 将1,2,3,4添加到堆栈中 stack.push("1"); stack.push("2"); stack.push("3"); stack.push("4"); // 打印“栈” System.out.println("stack:"+stack); // 删除“栈顶元素” System.out.println("stack.pop():"+stack.pop()); // 取出“栈顶元素” System.out.println("stack.peek():"+stack.peek()); // 打印“栈” System.out.println("stack:"+stack); } /** * 将LinkedList当作 FIFO(先进先出)的队列 */ private static void useLinkedListAsFIFO() { System.out.println(" useLinkedListAsFIFO"); // 新建一个LinkedList LinkedList queue = new LinkedList(); // 将10,20,30,40添加到队列。每次都是插入到末尾 queue.add("10"); queue.add("20"); queue.add("30"); queue.add("40"); // 打印“队列” System.out.println("queue:"+queue); // 删除(队列的第一个元素) System.out.println("queue.remove():"+queue.remove()); // 读取(队列的第一个元素) System.out.println("queue.element():"+queue.element()); // 打印“队列” System.out.println("queue:"+queue); } }
结果
Test "addFirst(), removeFirst(), getFirst()" llist:[10, 1, 4, 2, 3] llist.removeFirst():10 llist:[1, 4, 2, 3] llist.getFirst():1 Test "offerFirst(), pollFirst(), peekFirst()" llist:[10, 1, 4, 2, 3] llist.pollFirst():10 llist:[1, 4, 2, 3] llist.peekFirst():1 Test "addLast(), removeLast(), getLast()" llist:[1, 4, 2, 3, 20] llist.removeLast():20 llist:[1, 4, 2, 3] llist.getLast():3 Test "offerLast(), pollLast(), peekLast()" llist:[1, 4, 2, 3, 20] llist.pollLast():20 llist:[1, 4, 2, 3] llist.peekLast():3 get(3):300 str:1 str:4 str:300 str:3 size:4 isEmpty():true useLinkedListAsLIFO stack:[4, 3, 2, 1] stack.pop():4 stack.peek():3 stack:[3, 2, 1] useLinkedListAsFIFO queue:[10, 20, 30, 40] queue.remove():10 queue.element():20 queue:[20, 30, 40]