LinkedList的基本存储结构是链表
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;
}
}
LinkedList的add源码为：
public boolean add(E e){
linkLast(e);
return true;
}
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++;
}
因为LinkedList的基本结构是链表，所以add就是在链表的末尾添加一个节点，然后size++，当last==null代表改list为空的，所以头结点置为newNode
linkedList的remove源码为：
public boolean remove(Object o){
if(o==null){
for(Node<E> x=first;x!=null;x=x.next){
if(x.item == null){
unlink(x);
return true;
}
}
}else{
for(Node<E> x=first;x!=null;x=x.next){
if(o.equals(x.item)){
unlink(x);
return true;
}
}
}
return false;
}
linkedList的remove就是从头遍历节点，然后调用unlink来remove节点，unlink的源码如下：
E unlink(Node<E> x){
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if(prev == null){
first=next;
}else{
prev.next = next;
x.prev = null;
}
if(next == null){
last=prev;
}else{
next.prev=prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
``unlink就是把元素的前节点的next指向该元素的next,把元素的后节点的prev指向该元素的prev,然后把该元素的prev和next和item置为null,方便GC回收。
linkedList的get的源码为：
public E get(int index){
checkElementIndex(index);
return node(index).item;
}
get的时候先检测了index是否<0或者大于size,若是则抛出异常。node()的源码为：
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;
}
}
node方法就是先判断一下index接近first还是last，然后决定从哪个方向开始查找。
linkedList的contains的源码为：
public boolean contains(Object o){
return indexOf(o)!=-1;
}
public int indexOf(Object o){
int index = 0;
if(o==null){
for(Node<E> x=first;x!=null;x=x.next){
if(x.item == null)
return index;
index++;
}
}else{
for(Node<E> x = first;x!=null;x=x.next){
if(o.equals(x.item))
return index;
index++;
}
}
return -1;
}
contains就是从first开始遍历，查到就返回index
linkedList的clone的源码为：
public Object clone(){
LinkedList<E> clone = superClone();
clone.first = clone.last=null;
clone.size=0;
clone.modCount = 0;
for(Node<E> x=first;x!=null;x=x.next)
clone.add(x.item);
return clone;
}
``LinkedList的clone是浅克隆，只是克隆了引用。
网友评论