LinkedList的底层实现原理
LinkedList 底层数据结构为双向链表,链表结构,基于一个个链表节点Node
1,Inner Class 内部类
private static class Node
E item;//当前节点下的当前元素
Node
Node
//constructor
Node(Node
this.item = element;
this.next = next;
this.prev = prev;
}
}
2,属性 fields
transient size = 0;
transient Node
transient Node
//LinkedList 底层是链表结构,所以其属性就是封装了链表中一个有多少个节点,以及第一个节点,最后一个节点。
3,构造方法 constructor
//无参构造方法
public LinkedList(){
}
//public LinkedList(Collection extends E> c){
this();
addAll(size,c);
}
public boolean addAll(int index,Collection extends E>c){
checkPositionIndex(index);
Object[] a = c.toArray();
int numNew = a.length;
if(numNew == 0)
return false;
Node
例:{“good”,"bad","bye","see","to","two","you","me"} 要实现在index = 2 处insert 一个集合,那么Node
if(index == size){
succ = null;
pred = last;
//按着顺序插入的情况会相等,必须先插入长度为3的集合,然后顺着插入在index 为4 的位置继续插入
}else{
succ = node(index);//-[]-[]-[]-[]-[]/\-[]-[] /\代表插入,succ 后节点就是/\ 之后的节点
pred = succ.prev;
}
//开始插入
for(Object o:a){
@SupressWarnings("unchecked") E e = (E)o;
Node
if(pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;//为了循环中下一次的赋值,得把pred赋值成当前元素
}
if(succ == null){
last = pred;
}else{
pred.next = succ;
succ.prev = pred;
//因为pred 在for 循环中插入时候一直有更新,所以这段代码的作用是为了将插入的最后一个节点后变化后的节点连接起来,形成一个新的链表。
}
}
//找到即将有变化的节点,这个节点永远是变化的后节点
Node
//二分法,如果变化在前半部分,则找出first 如果变化在后半部分,则找出last
if(index <(size >> 1)){//前半部分
Node
for(int i &#61; 0; i
return x;
}else{
Node
for(int i &#61; size - 1; i>index; i--){
x &#61; x.prev;
return x;
}
}
}
private void checkPositionIndex(int index){
if(!isPositionIndex(index))
throw new IndexOutOfBoundsException(OutOfBoundsMsg(index));
}
private boolean isPositionIndex(index){
return index >&#61;0 && index <&#61;size;
}
//addAll(int index,Collection extends E> c)这个方法可以用于LinkedList 的初始化中&#xff0c;
可以加载指定集合到目标集合中。
另外&#xff0c;这个方法也可以用于在目标集合指定位置插入指定集合。
4,add
public boolean add(E e){
linkLast(e);
return true;
}
void linkLast(E e){
final Node
final Node
last &#61; newNode;
if(l &#61;&#61; null){
first &#61; newNode;
}else{
l.next &#61; newNode;
}
size&#43;&#43;;
modCount&#43;&#43;;
}
//add方法中范型E控制add元素的类型&#xff0c;如果类型不对&#xff0c;则编译报错&#xff0c;否则不会出现异常。
在最后一个节点后面增加新元素,上一个节点是last,当前是e,下一个null,需要判断当前增加的是不是第一个元素&#xff0c;是则将新增元素赋值为链中的first,不是则将当前元素赋值为last的next元素。
5 addFirst
public void addFirst(E e){
linkFirst(e);
}
private void linkFirst(E e){
Final Node
Final Node
first &#61; newNode;
//每增加一个节点&#xff0c;都要创建和已知节点的关联
if(f &#61;&#61; null)
last &#61; newNode;
else
f.prev &#61; newNode;
size&#43;&#43;;
modCount&#43;&#43;;
}
6,addLast
调用的也是linkLast(E e)方法&#xff0c;和add(E e) 是调用一样的方法&#xff0c;只不过add(E e) 返回类型是boolean 型&#xff0c;addLast是void.
7,removeFirst
public E removeFirst(E e){
final Node
if(f &#61;&#61; null)
throw new NoSuchElementException();
return unLinkFirst(f);
}
privte E unLinkFirst(Node
final E element &#61; f.item;
Node
//f 将删除&#xff0c;f的节点关系也需被删除
f.item &#61; null;
f.next &#61; null;
first &#61; next;
if(next &#61;&#61; null)
last &#61; next;
else
next.prev &#61; null;
size--;
modCount&#43;&#43;;
return element;
}
8,removeLast
public E removeLast(E e){
final Node
if(last &#61;&#61; null)
throw new NoSuchElementException();
return unLinkLast(l);
}
private E unLinkLast(Node
final E element &#61; l.item;
fianl Node
//clear relationship
l.item &#61; null;
l.prev &#61; null;
//重新设定
last &#61; prev;
if(prev &#61;&#61; null)
first &#61; prev;
else
prev.next &#61; null;
size--;
modeCount&#43;&#43;:
return element;
}
9,getFirst
public E getFirst(){
fianl Node
if(f &#61;&#61; null)
throw new NoSuchElementException();
return f.item;
}
10,getLast
public E getLast(){
final Node
if(l &#61;&#61; null)
throw new NoSuchElementException();
return l.item;
}
11,查询
public E get(int index){
CheckElementIndex(index);
return node(index).item;//通过node方法获取到当前index 的节点
}