Java LinkedList类源码解析
LinkedList底层为双向链表同样继承了AbstractSequentialList<E>,跟ArrayList的数组相比读取效率低,不支持随机读取,碎片化空间利用率高,平均随机插入效率相对高。同时可以用来实现queue。属性有:
transient int size = 0;list大小
transient Node<E> first;头指针
transient Node<E> last;尾指针
private void linkFirst(E e)
void linkLast(E e)
将e添加到链表的头部和尾部,size与modCount加一
void linkBefore(E e, Node<E> succ)将e插入到succ结点之前
private E unlinkFirst(Node<E> f)
private E unlinkLast(Node<E> l)
移除头部或尾部结点,size减1,modCount加1,将移除结点的next prev item值都设为null以触发gc
E unlink(Node<E> x)移除结点x,需要再判断有无前驱和后驱结点,若没有则要改变头尾指针,同样将移除结点的next prev item值都设为null以触发gc
public E getFirst()
public E getLast()
返回first或last指向的结点,链表为空时抛错
public E removeFirst()
public E removeLast()
调用unlinkLast移除并返回头部或尾部的结点,链表为空时抛错
public void addFirst(E e)调用linkFirst(e),将元素插入到头部
public void addLast(E e)
public boolean add(E e)
两个方法都是调用linkLast(e),除了返回值外是等价的
public boolean remove(Object o)o==null时,通过unlink方法移除所有x==null的元素,否则移除o.equals(x)的元素,每有一个符合的元素就调用一次unlink所以modCount的增加值为移除元素的个数
public boolean addAll(int index, Collection<? extends E> c)将c中的集合插入到index位置。首先检查index是否符合链表长度范围,若c中没有元素则直接返回false,否则遍历c中的元素产生新的结点并链接到index指向位置,检查是否需要修改first和last的位置,最后修改size和modCount++
public void clear()遍历所有结点,将last prev item全部设为null,size为0,modCount++
public E set(int index, E element)检查index范围后设置为item=element,不会改变modCount
public void add(int index, E element)检查index范围,若index==size即插入再末尾,调用linkLast(element),否则调用linkBefore(element, node(index))因此会造成modCount++
public E remove(int index) 检查index范围,index >= 0 && index < size则调用unlink(node(index))移除元素,modCount++
Node<E> node(int index)返回index下标的结点,若index超过size的一半则从last开始向头寻找,否则从first开始向后寻找
public int indexOf(Object o)寻找与o相等的下标最小的链表元素,若没有则返回-1,比较逻辑依然根据o是否是null来区分
public int lastIndexOf(Object o)从尾部开始搜索第一个符合条件的元素下标,和上面一个方法类似
public E peek()返回first指向结点的item,若为空则返回null
public E element()也是返回first.item,区别是为空会抛错
public E poll()在peek()的基础上,若不为null会删除第一个元素
public boolean offer(E e)同add(e)
public boolean offerFirst(E e)同addFirst
public boolean offerLast(E e)同addLast
public E peekFirst()同peek()
public E peekLast()返回尾部元素,为空则返回null
public E pollFirst()同poll()
public E pollLast()返回尾部元素,为空则返回null,不为空移除尾部元素
public void push(E e)将e添加到头部
public E pop()移除头部元素
public boolean removeFirstOccurrence(Object o)同remove(o)
public boolean removeLastOccurrence(Object o)移除最后一个与o相等的元素
public Object[] toArray()新建一个数组,遍历链表将元素复制到数组中
private void writeObject(java.io.ObjectOutputStream s)
private void readObject(java.io.ObjectInputStream s)
序列化的方式和ArrayList相同,是通过对象输入输出流来完成,输入时调用linkLast将读取到的元素加入链表末尾
个人GitHub地址: https://github.com/GrayWind33低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
tomcat启动报错 java.util.zip.ZipException: invalid CEN header (bad signatu...
war包部署到tomcat里,启动时报错: Caused by: org.apache.catalina.LifecycleException: Failed to initialize component [org.apache.catalina.webresources.JarResourceSet@7e21e65f] at org.apache.catalina.util.LifecycleBase.init(LifecycleBase.java:106) at org.apache.catalina.util.LifecycleBase.start(LifecycleBase.java:136) at org.apache.catalina.webresources.StandardRoot.startInternal(StandardRoot.java:699) at org.apache.catalina.util.LifecycleBase.start(LifecycleBase.java:147) ... 14 more Caused by: java.lang.Ill...
- 下一篇
conda的安装和VSCode下的配置方法
conda的安装和配置方法 安装miniconda 1.1 说明 conda是一个开源的软件包管理工具和环境管理系统,可以轻松创建多个软件环境,并在多个环境之间轻松切换。例如,我们可以分别创建python3和python2的独立软件环境,并在需要该环境时轻松进行切换(根据工作目录)。 conda的配置工具有两个,miniconda(命令行工具,占用空间约400M),anaconda(GUI工具,占用空间约3G)。 想都不用想,肯定是用miniconda啦,毕竟配置的时间非常短,没什么大不了的。 1.2 下载安装包 下载官方miniconda安装包,在下载页面选择对应平台的安装包进行安装。 自带python环境,可以根据自己长期使用的版本进行选择,但是不建议在默认环境下安装软件包。 1.3 安装注意事项 下载好安装包后,安装时可以选择作为用户软件安装(储存到用户文件夹),或者做为系统软件安装(所有用户都可以使用) 到下面这一步时,勾选两个选项,其他按默认 这两个选项分别是,添加miniconda至环境变量PATH,注册miniconda所带的python为默认环境。 如果你的环境里已经有...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- SpringBoot2整合Thymeleaf,官方推荐html解决方案
- SpringBoot2整合Redis,开启缓存,提高访问速度
- CentOS7设置SWAP分区,小内存服务器的救世主
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- Eclipse初始化配置,告别卡顿、闪退、编译时间过长
- SpringBoot2全家桶,快速入门学习开发网站教程
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- CentOS7安装Docker,走上虚拟化容器引擎之路
- CentOS6,7,8上安装Nginx,支持https2.0的开启
- CentOS7编译安装Gcc9.2.0,解决mysql等软件编译问题