Java知识：LinkedList类详解

这篇博客算不上对LinkedList类的详解，我只能把自己浅薄的知识分享出来了。

1、LinkedList的本质是什么？

双向链表

2、LinkedList是基于什么实现的？

JDK1.6的时候是Entry结点实现的，JDK1.7开始改用Node结点实现。
那这两个有什么不同呢，**据说**是1.7优化的。说是从循环链表变成    了非循环链表。

3、LinkedList扩容扩多少呢？

因为LinkedList 是基于链表的，因此不像ArrayList需要扩容机制。

4、为什么LinkedList查询操作慢，增删操作块？

查询操作源代码：

public E get(int index) {  
     checkElementIndex(index);  
     return node(index).item;  
}  
Node<E> node(int index) {  
      if (index < (size >> 1)) {  
        Node<E> x = first;  
        for (int i = 0; i < index; i++)  
            x = x.next;  
        return x;  
    } else {  
        Node<E> x = last;  
        for (int i = size - 1; i > index; i--)  
            x = x.prev;  
            return x;  
  }    
} 

可以看出他根据index和size比较来决定从哪边开始遍历才能更快的查询到该下标的元素。而不是直接访问到该元素。比起ArrayList内部直接对数组下标访问性能确实差一截。

增删操作源代码：
以add(int index, E element)方法为例

public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }

checkPositionIndex(index);//函数如下，这是一个检查异常的函数，我们写程序的时候可以借鉴这种思想，但是他现在不是我们考虑的重点。

private void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

if (index == size) //如果下标是最后的
linkLast(element); //直接添加到最后
else //如果下标不是最后的
linkBefore(element, node(index)); //执行这个添加函数
linkBefore(E e, Node succ)函数如下：

void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

pred 是当前要插入位置节点的上一个节点，即图中的第一个节点。newNode 将要插入的对象包装成node节点(指定上一个节点为pred，下一个节点为node()返回值succ)。
接着将succ节点的上一个节点指定为我们的新节点newNode。那么肯定会有逻辑将pred的next设置为newNode。
果然，最后做了一个判断，如果pred为null，说明succ节点为第一个有数据的节点，就将生成的新节点newNode置为first节点，否则指定上个节点的下一个节点为生成的新节点，即pred.next = newNode。
这样就完成了整个链表数据插入过程。显然是不同于ArrayList那样地进行数组复制。

5、List（包含ArrayList）独有的迭代器ListIterator

• 两者的关系：

  ListIterator接口是Iterator接口的子接口

• 相同点：

  都是迭代器，当需要对集合中元素进行遍历时，这两种迭代器都可以使用。

• 不同点：

  1.使用范围不同，Iterator可以应用于所有的集合，Set、List和Map和这些集合的子类型。而ListIterator只能用于List及其子类型。
  2.ListIterator有add方法，可以向List中添加对象，而Iterator不能。
  3.ListIterator和Iterator都有hasNext()和next()方法，可以实现顺序向后遍历，但是ListIterator有hasPrevious()和previous()方法，可以实现逆向（顺序向前）遍历。Iterator不可以。
  4.ListIterator可以定位当前索引的位置，nextIndex()和previousIndex()可以实现。Iterator没有此功能。
  5.都可实现删除操作，但是ListIterator可以实现对象的修改，set()方法可以实现。Iterator仅能遍历，不能修改。
  ListIterator相比Iterator功能更强，更加适合List类型数据操作

6、LinkedList小Demo(只有关键代码)

1、获取链表的第一个和最后一个元素
System.out.println(“链表的第一个元素是 : ” + lList.getFirst());
System.out.println(“链表最后一个元素是 : ” + lList.getLast());
2、从链表生成子表
List subl = lList.subList(1, 4);
3、添加元素：添加单个元素
如果不指定索引的话，元素将被添加到链表的最后.
public boolean add(Object element)
public boolean add(int index, Object element)
也可以把链表当初栈或者队列来处理:
public boolean addFirst(Object element)
public boolean addLast(Object element)
addLast()方法和不带索引的add()方法实现的效果一样.
4、删除元素
list.removeFirst();
list.removeLast();
5、使用链表实现栈效果 (先进后出)
class StackL {
private LinkedList list = new LinkedList();
public void push(Object v) { //压栈操作
list.addFirst(v);
}
public Object top() { //查看栈顶元素
return list.getFirst();
}
public Object pop() { //出栈操作
return list.removeFirst();
}
}
6、使用链表来实现队列效果(先进先出)
class Queue {
private LinkedList list = new LinkedList();
public void put(Object v) {
list.addFirst(v);
}
public Object get() {
return list.removeLast();
}
public boolean isEmpty() {
return list.isEmpty();
}
}
7、删掉所有元素：清空LinkedList
lList.clear();
8、ArrayList和linkedlist之间的转换
通过构造方法互换
LinkedList linkedList = new LinkedList(arrayList);
ArrayList arrayList = new ArrayList(linkedList);
9、确认链表是否存在特定元素
lList.contains(“4”)；

总结：

1、LinkedList适合增删，不适合查找。
2、LinkedList不同步
3、LinkedList本质是双向链表
参考资料：