AI 助理
备案控制台
开发者社区 云计算 文章 正文

LinkedList源码学习

2022-12-11 77
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： LinkedList 继承 抽象SequentialList、实现list接口，双端队列Deque以及克隆，因此具备列表、队列、双端队列的特性，可克隆。

LinkedList 继承 抽象SequentialList、实现list接口，双端队列Deque以及克隆，因此具备列表、队列、双端队列的特性，可克隆。


一、相关变量信息


//长度为0transientintsize=0;
//首节点transientNode<E>first;
//尾节点transientNode<E>last;
//节点信息包含当前节点元素，下一个元素节点、//前一个元素节点,也就是前驱和后继，//类似于c语言链表private static class Node<E> {Eitem;
Node<E>next;
Node<E>prev;
Node(Node<E>prev, Eelement, Node<E>next) {
this.item=element;
this.next=next;
this.prev=prev;
    }
}


二、构造函数


//空参构造方法publicLinkedList() {
}
//构造一个包含指定集合元素的列表，//其顺序由集合的迭代器返回public LinkedList(Collection<? extends E> c) {//指向空参构造this();
//添加集合caddAll(c);
}
其中addAll方法：//将集合c的元素加入到列表中publicbooleanaddAll(Collection<?extendsE>c) {
returnaddAll(size, c);
}
//插入带有指定元素的集合c到list列表中public boolean addAll(int index,                      Collection<? extends E> c) {//检查当前位子的索引是否越界checkPositionIndex(index);
//将带有特定元素的集合c转成数组Object[] a=c.toArray();
//拿到数组的长度intnumNew=a.length;
//如果长度为0,返回false，不进行添加if (numNew==0)
returnfalse;
//定义节点pred 前节点、succ后节点Node<E>pred, succ;
//如果索引等于列表长度，此时说明//最后一个元素，直接添加即可， if (index == size) {succ=null;
pred=last;
//否者，进行前驱和后继操作 } else {
//找到当前下标指向的节点，要在该节点  //前插入数据，因此令succ等于该节点。  succ = node(index);//前节点等于succ的前驱节点pred=succ.prev;
  }
//对c.array中的元素进行遍历，并将//其元素都强转成E类型  for (Object o : a) {@SuppressWarnings("unchecked")     Ee= (E) o;//创建一个新的节点对象，节点元素为e，//前节点为pred，后节点为null Node<E> newNode = new Node<>(pred, e, null);//如果前节点为null,则将当前节点的//信息变为头结点信息 if (pred == null)first=newNode;
//否者，将当前节点变成前节点的后一个节点elsepred.next=newNode;//令当前节点作为前节点，获取下一个元素，循环   pred = newNode;  }//说明是从当前集合的末尾开始插入数据，//因此数据的最后一个元素，作为当前集合的last if (succ == null) {last=pred;
//后节点不为null,pred为新插入的//最后一个数据，令其的后节点等于之前拆开//位置的后节点，succ为之前拆开位置//的前节点，令其前节点prev等于新插入//的元素的最后一个数据  } else {pred.next=succ;
succ.prev=pred;
    }
//由于增加了元素，因此需要增加元素的长度size+=numNew;
modCount++;
returntrue;}


三、相关操作


(1)添加元素

头插：

//添加头结点publicvoidaddFirst(Ee) {
linkFirst(e);
}
//增加元素e为头节点元素，头插privatevoidlinkFirst(Ee) {
//f为首节点final Node<E> f = first;//创建新节点，前驱节点为null，后继节点为first节点finalNode<E>newNode=newNode<>(null, e, f);
//更新first节点first=newNode;
//如果f节点为空，则两个节点首节点等于尾节点// 则表示newNode = new Node<>(null, e, null);//说明此节点是last节点if (f==null)
last=newNode;
else//f不为空时，则newNode = new Node<>(null, e, f); //表示头节点不为空 //而当前节点在头节点前面，因此此时e变成f的前驱节点f.prev=newNode;
//长度自增size++;
//修改次数自增modCount++;
}

尾插：

//添加尾元素publicvoidaddLast(Ee) {
linkLast(e);
}
//增加e作为链表的尾节点元素，尾插voidlinkLast(Ee) {
//将l设置为尾节点finalNode<E>l=last;
//创建新节点finalNode<E>newNode=newNode<>(l, e, null);
//将当前节点变成尾节点last=newNode;
//如果l==null => //newNode = new Node<>(null, e, null) //因此说明此元素是头结点if (l==null)
first=newNode;
//l不为空，在l的后面，则增加元素往l的后面插elsel.next=newNode;
size++;
modCount++;
}

尾插：

//添加元素，尾插publicbooleanadd(Ee) {
linkLast(e);
returntrue;
}
//插入带有指定元素的集合c到list列表中publicbooleanaddAll(intindex,                   Collection<?extendsE>c) {//检查当前位子的索引是否越界checkPositionIndex(index);
//将带有特定元素的集合c转成数组Object[] a=c.toArray();
//拿到数组的长度intnumNew=a.length;
//如果长度为0,返回false，不进行添加if (numNew==0)
returnfalse;
//定义节点pred 前节点、succ后节点Node<E>pred, succ;
//如果索引等于列表长度，//此时说明最后一个元素，直接添加即可，    if (index == size) {succ=null;
pred=last;
//否者，进行前驱和后继操作   } else {
//找到当前下标指向的节点，要在该节点       //前插入数据，因此令succ等于该节点。       succ = node(index);//前节点等于succ的前驱节点pred=succ.prev;
    }
//对c.array中的元素进行遍历，    //并将其元素都强转成E类型    for (Object o : a) {@SuppressWarnings("unchecked")        Ee= (E) o;    //创建一个新的节点对象，节点元素为e，    //前节点为pred，后节点为null    Node<E> newNode = new Node<>(pred, e, null);//如果前节点为null,则将当前节点的信息        //变为头结点信息        if (pred == null)first=newNode;
//否者，将当前节点变成前节点的后一个节点,//将当前节点作为前节点，获取下一个节点，循环elsepred.next=newNode;        pred=newNode; 
    }
//说明是从当前集合的末尾开始插入数据，    //因此数据的最后一个元素，作为当前集合的last    if (succ == null) {last=pred;
//后节点不为null,pred为新插入的最后一个数据，    //令其的后节点等于之前拆开    // 位置的后节点，succ为之前拆开位置的前节点，    //令其前节点prev等于新插入的元素的最后一个数据    } else {pred.next=succ;
succ.prev=pred;
    }
//由于增加了元素，因此需要增加元素的长度size+=numNew;
modCount++;
returntrue;
}

中间插：

//添加指定元素publicvoidadd(intindex, Eelement) {
checkPositionIndex(index);
//所要添加元素等于长度，则尾插if (index==size)
linkLast(element);
//否者之间插elselinkBefore(element, node(index));
}
//传入元素和后节点，中间插voidlinkBefore(Ee, Node<E>succ) {
// assert succ != null;//前节点是后节点的前驱节点finalNode<E>pred=succ.prev;
//创建一个新节点finalNode<E>newNode=newNode<>(pred,e,succ);
//当前节点等于后节点的前驱节点succ.prev=newNode;
//如果前节点为null，则将新节点变成首节点即可if (pred==null)
first=newNode;
//如果前节点不为空，则为前节点的后一个元素elsepred.next=newNode;
size++;
modCount++;
}

添加指定元素：

//将集合c的元素加入到列表中publicbooleanaddAll(Collection<?extendsE>c){
returnaddAll(size, c);
}

(2)删除操作，释放节点

删除头结点：

//删除头结点publicEremoveFirst() {
finalNode<E>f=first;
if (f==null)
thrownewNoSuchElementException();
//删除头结点信息returnunlinkFirst(f);
}
//释放头结点privateEunlinkFirst(Node<E>f) {
// assert f == first && f != null;//获取元素信息finalEelement=f.item;
//拿到后继节点信息finalNode<E>next=f.next;
f.item=null;
f.next=null; // help GC//将下一个节点变成头结点first=next;
if (next==null)
last=null;
else//同时将头结点的前驱节点置空next.prev=null;
//长度-1size--;
//修改次数+1modCount++;
//返回释放的元素returnelement;
}

删除尾节点：

//删除尾节点publicEremoveLast() {
finalNode<E>l=last;
if (l==null)
thrownewNoSuchElementException();
//删除尾节点returnunlinkLast(l);
}
//释放尾节点privateEunlinkLast(Node<E>l) {
// assert l == last && l != null;//获取当前元素finalEelement=l.item;
//获取尾节点的前驱节点finalNode<E>prev=l.prev;
l.item=null;
l.prev=null; // help GC//将为节点的前驱节点变成尾节点last=prev;
if (prev==null)
first=null;
else//同时将尾节点置空prev.next=null;
size--;
modCount++;
returnelement;
}

删除中间节点：

//删除元素
public boolean remove(Object o) {
  //删除的对象不为null
  if (o == null) {
   //进行遍历
   for(Node<E> x = first; x != null; x=x.next){
            //不为null,进行移除
            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;
}
//释放节点
E unlink(Node<E> x) {
    // assert x != null;
    //获取要释放的元素
    final E element = x.item;
    //获取前驱节点和后继节点
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;
   //如果前驱是空的，则说明释放元素就是   //头结点，将后面元素变成头节点    if (prev == null) {
        first = next; //一个元素的情况
   //如果前驱不为null,则说明当前节点有前驱节点，
   // 则只需将前驱节点的next=当前节点的next，
   // 同时还需要删除节点的引用，因为此时不可用
    } else {
        prev.next = next;
        x.prev = null;
    }
    //如果后继为空，则前置节点成为最后一个节点
    if (next == null) {
        last = prev;
    //后继节点不为空，则后继点击前移
    //将要删除的节点的后继引用删除
    } else {
        next.prev = prev;
        x.next = null;
    }
   //将要删除的元素置空，长度减1，   //修改次数+1，返回要删除的节点元素    x.item = null;
    size--;
    modCount++;
    return element;
}

(3)获取get操作

获取头结点元素：

//获取头结点publicEgetFirst() {
finalNode<E>f=first;
//进行判空if (f==null)
thrownewNoSuchElementException();
//返回元素信息returnf.item;
}

获取尾节点元素：

//获取尾节点publicEgetLast() {
finalNode<E>l=last;
if (l==null)
thrownewNoSuchElementException();
returnl.item;
}

获取指定节点元素：

//获取元素publicEget(intindex) {
//先检查是否越界checkElementIndex(index);
//返回元素信息returnnode(index).item;
}

(4)替换操作：

//替换指定元素publicEset(intindex, Eelement) {
//检查越界情况checkElementIndex(index);
Node<E>x=node(index);
EoldVal=x.item;
x.item=element; //替换节点元素既可returnoldVal;
}

(5)返回元素的索引信息：

//返回第一次出现的索引信息publicintindexOf(Objecto) {
intindex=0;
if (o==null) {
for(Node<E>x=first; x!=null; x=x.next){
if (x.item==null)
returnindex;
index++;
        }
   } else {
for(Node<E>x=first; x!=null; x=x.next){
if (o.equals(x.item))
returnindex;
index++;
        }
    }
return-1;
}
//返回最后出现的索引信息publicintlastIndexOf(Objecto) {
intindex=size;
if (o==null) {
for(Node<E>x=last; x!=null; x=x.prev){
index--;
if (x.item==null)
returnindex;
        }
   } else {
for(Node<E>x=last; x!=null; x=x.prev){
index--;
if (o.equals(x.item))
returnindex;
        }
    }
return-1;
}


四、队列操作


//返回首节点元素信息publicEpeek() {
finalNode<E>f=first;
return (f==null) ?null : f.item;
}
//获取头结点元素publicEelement() {
returngetFirst();
}
//移除头结点publicEpoll() {
finalNode<E>f=first;
return (f==null) ?null : unlinkFirst(f);
}
//删除头结点publicEremove() {
returnremoveFirst();
}
//添加元素到队尾publicbooleanoffer(Ee) {
returnadd(e);
}


五、双端队列操作

//头插，添加元素publicbooleanofferFirst(Ee) {
addFirst(e);
returntrue;
}
//尾插，添加元素publicbooleanofferLast(Ee) {
addLast(e);
returntrue;
}
//返回头节点的元素publicEpeekFirst() {
finalNode<E>f=first;
return (f==null) ?null : f.item;
}
//返回尾节点的元素publicEpeekLast() {
finalNode<E>l=last;
return (l==null) ?null : l.item;
}
//删除头结点信息publicEpollFirst() {
finalNode<E>f=first;
return (f==null) ?null : unlinkFirst(f);
}
//删除尾节点信息publicEpollLast() {
finalNode<E>l=last;
return (l==null) ?null : unlinkLast(l);
}


六、栈操作

//由于支持栈操作，所以支持push头部添加元素，进栈publicvoidpush(Ee) {
addFirst(e);
}
//支持栈操作，pop移除，也就是消费，出栈publicEpop() {
returnremoveFirst();
}


七、迭代操作

//进行元素迭代privateclassListItrimplementsListIterator<E>{
privateNode<E>lastReturned;
privateNode<E>next;
privateintnextIndex;
privateintexpectedModCount=modCount;
ListItr(intindex){
// assert isPositionIndex(index);next= (index==size) ?null : node(index);
nextIndex=index;
   }
//是否进行下一次迭代publicbooleanhasNext() {
returnnextIndex<size;
    }
//返回下一个元素publicEnext() {
checkForComodification();
if (!hasNext())
thrownewNoSuchElementException();
//下一个元素lastReturned=next;
//下一个元素作为参考，当前元素，next元素        //的节点就是next.next        next = next.next;//nextIndex自增nextIndex++;
returnlastReturned.item;
    }
//是否存在前驱元素publicbooleanhasPrevious() {
returnnextIndex>0;
    }
//存在前驱元素，则进行获取publicEprevious() {
checkForComodification();
if (!hasPrevious())
thrownewNoSuchElementException();
lastReturned=next= (next==null) ?last                        : next.prev;     nextIndex--;
returnlastReturned.item;
    }
publicintnextIndex() {
returnnextIndex;
    }
publicintpreviousIndex() {
returnnextIndex-1;
    }
//进行remove操作publicvoidremove() {
checkForComodification();
if (lastReturned==null)
thrownewIllegalStateException();
Node<E>lastNext=lastReturned.next;
unlink(lastReturned);
if (next==lastReturned)
next=lastNext;
elsenextIndex--;
lastReturned=null;
expectedModCount++;
    }
//元素替换publicvoidset(Ee) {
if (lastReturned==null)
thrownewIllegalStateException();
checkForComodification();
lastReturned.item=e;
    }
//添加元素publicvoidadd(Ee) {
checkForComodification();
lastReturned=null;
if (next==null)
linkLast(e);
elselinkBefore(e, next);
nextIndex++;
expectedModCount++;
    }
//进行迭代publicvoidforEachRemaining(Consumer<?superE>action){    Objects.requireNonNull(action);
while (modCount==expectedModCount&&nextIndex<size) {        action.accept(next.item);
lastReturned=next;
next=next.next;
nextIndex++;
       }
checkForComodification();
    }
//检查修改次数与期望修改此时是否相同finalvoidcheckForComodification() {
if (modCount!=expectedModCount)
thrownewConcurrentModificationException();
    }
}


8.克隆操作

publicObjectclone() {
LinkedList<E>clone=superClone();
// Put clone into "virgin" stateclone.first=clone.last=null;
clone.size=0;
clone.modCount=0;
// Initialize clone with our elementsfor (Node<E>x=first; x!=null; x=x.next)
clone.add(x.item);
returnclone;
}


9.序列化操作

//将LinkedList写入流中，也就是将LinkedList保存到流中，//进行自己的个性化序列化//包括序列化数字、size、元素、节点信息privatevoidwriteObject(java.io.                           ObjectOutputStreams)    throwsjava.io.IOException {
// Write out any hidden serialization magics.defaultWriteObject();
// Write out sizes.writeInt(size);
// Write out all elements in the proper order.for (Node<E>x=first; x!=null; x=x.next)
s.writeObject(x.item);
}
//反序列化，从流中将LinkedList读取出来@SuppressWarnings("unchecked")
privatevoidreadObject(java.io.ObjectInputStreams)
throwsjava.io.IOException, ClassNotFoundException {
// Read in any hidden serialization magics.defaultReadObject();
// Read in sizeintsize=s.readInt();
// Read in all elements in the proper order.for (inti=0; i<size; i++)
linkLast((E)s.readObject());
}

当然JDK1.8时出现了迭代 public Spliterator spliterator()，功能与迭代器类似。由于其具有队列和链表的特性，同时还可以像栈一样操作，因此我们可以知道其顺序访问的速度较快，随机访问的速度较慢，插入、删除速度快。

文章标签：
索引
刘亚洲
目录
相关文章
xiaowang_lj
|
6月前
|
存储 缓存 Java
LinkedList 源码解读
LinkedList 源码解读
xiaowang_lj
36 1
理想万岁万万岁
|
6月前
|
存储 Java
ArrayList源码学习
深入学习ArrayList源码
理想万岁万万岁
54 1
ArrayList源码学习
理想万岁万万岁
|
6月前
|
调度 uml 索引
LinkedList源码学习
LinkedList源码学习
理想万岁万万岁
19 0
LinkedList源码学习
张思睿ZGQ
|
6月前
|
算法 Java 索引
【数据结构与算法】4、双向链表（学习 jdk 的 LinkedList 部分源码）
【数据结构与算法】4、双向链表（学习 jdk 的 LinkedList 部分源码）
张思睿ZGQ
67 0
众所周知
|
6月前
|
Java
java数据结构，如何使用ArrayList和LinkedList？
java数据结构，如何使用ArrayList和LinkedList？
众所周知
46 1
@猪大肠
|
存储 Java
Java集合学习：LinkedList源码详解
Java集合学习：LinkedList源码详解
@猪大肠
147 0
@猪大肠
|
存储 Java 容器
Java集合学习：ArrayList源码详解
Java集合学习：ArrayList源码详解
@猪大肠
228 0
a816120
|
存储
看一看LinkedList的源码？
看一看LinkedList的源码？
a816120
65 0
greycode
|
算法
【源码解析】你真的了解ArrayDeque嘛？
上篇文章说LinkedList也可以实现队列和栈的功能，但是我们一般要用队列功能的话推荐使用ArrayDeque,因为他底层是数组，而队列和栈都是只要操作头部或尾部，所以这样的话数组的性能就比链表快一点。 LinkedList和ArrayDeque都是通过实现了Deque这个接口来获得队列和栈的功能。而Deque这个接口通过继承Queue这个接口来取得队列功能，然后在这个基础进行扩展，实现了双端队列，由此可以获得栈的功能。为了空间能得到充分利用，ArrayDeque使用了循环队列；还有LinkedList可以插入null值，而ArrayDeque是不能插入null的。
greycode
133 0
爱编程的大李子
|
Java
＜Java八股文面试＞ArrayList源码 | Iterator源码 | LinkedList和ArrayList对比（上）
＜Java八股文面试＞ArrayList源码 | Iterator源码 | LinkedList和ArrayList对比
爱编程的大李子
173 0
＜Java八股文面试＞ArrayList源码 | Iterator源码 | LinkedList和ArrayList对比（上）