1 说明
- LinkedList是一个双向链表,继承看List接口和Duque接口。
- LinkedList不是线程安全,确保线程安全方法
List list = Collections.synchronizedList(new LinkedList(...))
2 源码分析
2.1 静态内部类
LinkedList是一个链表,需要一个node类作为节点,因此他在内部构建了一个静态内部类。
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; }}
静态内部类,该类不能直接访问LinkedLIst的非静态成员(属性和方法),因为Java的约束:静态方法不能直接访问非静态的成员。
2.2 add()方法
往==链表尾部==添加元素,boolean修饰,总是返回true
public boolean add(E e) { linkLast(e); return true;}
再看linkLast(e)方法
void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++;}
如果l为空,则表示链表为空,插入的元素作为列表的第一个元素。
last是一个全局变量
transient Node<E> last;
然后相应的size也增加。size也是一个全局变量
transient int size = 0;
这样的话就可以写个获取size的方法,所以的size的方法为
public int size() { return size;}
2.3 get()方法
public E get(int index) { checkElementIndex(index); return node(index).item;}
==checkElementIndex(index)== 判断寻找的索引是否越界,如果越界则抛出异常。
==node(index).item== 通过方法取得nod对象,然后取得item的值。
Node<E> node(int index) { // assert isElementIndex(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; }}
这里通过位运算找出寻找范围的中间值,如果小于中间值,则出链头开始寻找,否则从链尾往回寻找。值得借鉴。
2.4 toArray()方法
将列表转成数组的一个桥梁方法
public Object[] toArray() { Object[] result = new Object[size]; int i = 0; for (Node<E> x = first; x != null; x = x.next) result[i++] = x.item; return result;}
2.5 clear()方法
此调用返回后,列表将为空
public void clear() { // Clearing all of the links between nodes is "unnecessary", but: // - helps a generational GC if the discarded nodes inhabit // more than one generation // - is sure to free memory even if there is a reachable Iterator for (Node<E> x = first; x != null; ) { Node<E> next = x.next; x.item = null; x.next = null; x.prev = null; x = next; } first = last = null; size = 0; modCount++;}
可以利用该方法清空list列表,达到list多次复用的目的,减少内存花销