Java集合框架系列——LinkedList

直通车：Java集合框架系列目录

本篇博文分为六个部分：

基本概念继承关系结构特点常用API遍历方式代码示例

1.基本概念

LinkedList：一种可以在任何位置进行高效地插入和删除操作的有序序列。

2.继承关系

LinkedList是一个继承于AbstractSequentialList的双向链表。 LinkedList实现 List 接口，能对它进行队列操作。 LinkedList实现 Deque 接口，即能将LinkedList当作双端队列使用。 LinkedList实现了Cloneable接口，即覆盖了函数clone()，能被克隆。 LinkedList实现java.io.Serializable接口，意即LinkedList支持序列化，能通过序列化传输。

有关AbstractSequentialList：

其支持按次序访问，而AbstractList 支持随机访问。其主要方法都是通过迭代器实现的。

3.结构特点

底层机制基于双向链表实现插入、删除元素较快，查找元素较慢其空间浪费主要体现在节点指针的存储上（相比ArrayList）不是线程安全的 在并发访问时，如果在迭代同时有其他线程修改了 LinkedList, fail-fast 的迭代器 Iterator/ListIterator 会抛出ConcurrentModificationException异常。 可以采取这样的方式：List list = Collections.synchronizedList(new LinkedList()); 或者考虑在单线程中才使用LinkedList，而在多线程中可以选择ConcurrentLinkedQueue。

4.常用API

5.遍历方式

1.通过迭代器遍历。即通过Iterator去遍历。

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循环遍历。

Integer value = null; for (Integer integ:list) { value = integ; }

4.通过pollFirst()遍历。 java.util.LinkedList.pollFirst() 方法检索并移除此列表的第一个元素，如果此列表为空，则返回null。

while(list.pollFirst() != null);

5.通过pollLast()遍历。 java.util.LinkedList.pollLast() 方法检索并移除此列表的最后一个元素，如果此列表为空，则返回null。

while(list.pollLast() != null);

6.通过removeFirst()遍历。 java.util.LinkedList.removeFirst() 方法移除并返回此列表的第一个元素，如果此列表为空，则抛出异常。

try { while(list.removeFirst() != null); } catch (NoSuchElementException e) { }

7.通过removeLast()遍历。 java.util.LinkedList.removeLast() 方法移除并返回此列表的最后一个元素，如果此列表为空，则抛出异常。

try { while(list.removeLast() != null); } catch (NoSuchElementException e) { }

使用这几种方法遍历LinkedList时，使用removeFist()或removeLast()效率最高，但会删除原始数据。若只读取，不删除，应该使用for循环遍历。

6.代码示例

import java.util.LinkedList; public class LinkTest { public static void main(String[] args) { // TODO Auto-generated method stub Stu s1 = new Stu("大牛",25); Stu s2 = new Stu("二牛",25); Stu s3 = new Stu("三牛",25); LinkedList ll = new LinkedList(); ll.add(s1); ll.addFirst(s2); ll.addLast(s3); for(int i=0;i<ll.size();i++){ Stu s = (Stu) ll.get(i); System.out.println("姓名："+s.getName()); } } } class Stu{ private String name; public String getName() { return name; } public void setName(String name) { this.name = name; } public int getAge() { return age; } public void setAge(int age) { this.age = age; } private int age; public Stu(String name,int age){ this.name=name; this.age=age; } }

如有谬误或不完善之处，恳请斧正！