java中LinkedList源码分析
2020-01-07 16:02:33来源:博客园 阅读 ()
java中LinkedList源码分析
Posted on 2020-01-07 22:04 思思博士 阅读(...) 评论(...) 编辑 收藏ArrayList是动态数组,其实本质就是对数组的操作。
那么LinkedList实现原理和ArrayList是完全不一样的。
现在就来分析一下ArrayList和LinkeList的优劣吧
LinkedList是一个双向链表,每个元素都是一个Node对象,
这个node对象里面有三个成员:
E item;指向实际的元素
Node<E> next;指向下一个节点
Node<E> prev;指向前一个结点
利用idea编辑器查看LinkedList的结构,发现只有三个成员变量。
而所有的public方法操作的都是这个三个变量。
下面逐个分析方法。
主要就是调用了linkLast方法。
步骤如下:
第一步:l指向尾节点,
第二步:创建新的节点newNode;因为是在链表的最后添加元素,所以新节点的next元素为null.
第三步:尾节点指向新的节点
第四步:如果l(之前的尾节点)为空,新节点当作第一个节点
第五步:如果l(之前的尾节点)不为空,则之前的尾节点的next变量指向新节点。
链表大小size++;
修改的次数modCount++;
List<String> list=new LinkedList<>(); list.add("a"); list.add("b");
与ArrayList不同,LinkedList内存是按需分配的,不需要提前分配内存空间,因为操作的不是数组。
get方法
checkElementIndex(index);主要用于检查参数是否符合规范,没什么好说的。
主要看node(index)方法。
index<(size>>1)表示index小于size/2;
如果index索引位于前半部分,从头开始根据next向后遍历;
一直找到index-1索引处
如果在后半部分从last处开始根据prev向前遍历。一直循环到index处。
ArrayList中数组是连续存放的,可以根据索引直接定位元素,而LinkedList中,必须从头或尾顺着链接查找,所以论查询效率LinkedList没有ArrayList效率高;但是在链表前或尾添加和删除的效率倒是比ArrayList要高。
LinkedList还提供了remove,add(int index,E element),indexOf(Object o)等等这些方法,基本上都是差不多的原理操作的。
原文链接:https://www.cnblogs.com/guoyansi19900907/p/12163985.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 国外程序员整理的Java资源大全(全部是干货) 2020-06-12
- 2020年深圳中国平安各部门Java中级面试真题合集(附答案) 2020-06-11
- 2020年java就业前景 2020-06-11
- 04.Java基础语法 2020-06-11
- Java--反射(框架设计的灵魂)案例 2020-06-11
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash