请选择 进入手机版 | 继续访问电脑版
搜索
房产
装修
汽车
婚嫁
健康
理财
旅游
美食
跳蚤
二手房
租房
招聘
二手车
教育
茶座
我要买房
买东西
装修家居
交友
职场
生活
网购
亲子
情感
龙城车友
找美食
谈婚论嫁
美女
兴趣
八卦
宠物
手机

LinkedList实现原理(JDK1.8)

[复制链接]
查看: 66|回复: 0

1万

主题

2万

帖子

4万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
48017
发表于 2019-12-4 02:04 | 显示全部楼层 |阅读模式
LinkedList实现道理(JDK1.8)

LinkedList底层采取双向链表,假如对链表这类结构比力熟悉的话,那LinkedList的实现道理看明白就相当轻易。
LinkedList实现原理(JDK1.8)  游戏 1669484-20191203234600861-814903376

链表经过“指针”将一组零星的内存块串联起来操纵,每一个元素(节点)经过指针指向它的下一个元素,末端一个节点的下一个指向为null,而双向链表就是除头节点的每一个元素都有指针同时再指向它的上一个元素。链表不同于数组,由于其地址的不持续,且元素占用巨细的不肯定,所以没法按照地址间接取值,获得元素时必要遍历拜候,而双向链表相比于单向链表,必定水平上占用了额外的内存,但支持了双向遍历,加速了元素讨取。
LinkedList实现原理(JDK1.8)  游戏 1669484-20191203234601236-929388533
  1. public class LinkedList extends AbstractSequentialList    implements List, Deque, Cloneable, java.io.Serializable
复制代码
LinkedList继续于AbstractSequentialList笼统类,AbstractSequentialList又继续于AbstractList,终极实现了List的接口,所以LinkedList支持List聚集的一些常规操纵,但同时LinkedList又实现了Queue接口,所以LinkedList也支持行列的一些操纵,例如peek、pop等。
1.成员变量
  1.     transient int size = 0;    /**     * Pointer to first node.     * Invariant: (first == null && last == null) ||     *            (first.prev == null && first.item != null)     */    transient Node first;    /**     * Pointer to last node.     * Invariant: (first == null && last == null) ||     *            (last.next == null && last.item != null)     */    transient Node last;
复制代码
LinkedList的垂危成员变量就3个,巨细size、头结点first、尾节点last,这也合适双向链表的特点,按照头大要尾部节点便可以遍历全部链表。至于节点典范,则是内部类Node。
  1.     private static class Node {        // 节点数据        E item;        // 下一节点        Node next;        // 上一节点        Node prev;        Node(Node prev, E element, Node next) {            this.item = element;            this.next = next;            this.prev = prev;        }    }
复制代码
Node类就简简单单三个属性,也即双向链表节点必须的3个要素,当前节点数据item,下一节点next和上一节点prev。
2.机关方式
  1.     public LinkedList() {    }    public LinkedList(Collection c) {        Objects.requireNonNull(c);        boolean modified = false;        // 操纵迭代器        Iterator it = iterator();        while (it.hasNext()) {            if (c.contains(it.next())) {                it.remove();                modified = true;            }        }        return modified;    }
复制代码
removeAll的实现道理实在就是迭代删除,迭代器的获得方式iterator()在AbstractCollection类中只是个笼统方式,AbstractList类有实在现,但AbstractSequentialList类中覆写该方式。
  1.     public Iterator iterator() {        return listIterator();    }
复制代码
iterator方式会挪用listIterator(),这个方式实现在AbstractList类中,他挪用了listIterator(int index)方式,但LinkedList重写了该方式,所以兜兜转转终极照旧回到了LinkedList中。
  1.     public ListIterator listIterator(int index) {        checkPositionIndex(index);        return new ListItr(index);    }
复制代码
这里ListItr工具是LinkedList的内部类。
  1.     private class ListItr implements ListIterator {        private Node lastReturned;        private Node next;        private int nextIndex;        // 等待计数器        private int expectedModCount = modCount;
复制代码
ListItr在初始化的时候,会将操纵计数器modCount赋值给expectedModCount,而以后的每次remove方式,城市校验expectedModCount与modCount能否相当,否则会抛出很是。
ListItr的remove方式,每次挪用后,都将expectedModCount自增,已到达和unlink中modCount++的同步,从而使得modCount == expectedModCount 不停建立,这也是为什么我们循环删除LinkedList元素时必要操纵其迭代器的remove方式。
  1.         public void remove() {            // 校验modCount            checkForComodification();            if (lastReturned == null)                throw new IllegalStateException();            Node lastNext = lastReturned.next;            // unlink删除节点逻辑,该方式中有modCount++;            unlink(lastReturned);            if (next == lastReturned)                next = lastNext;            else                nextIndex--;            lastReturned = null;            // expectedModCount自增            expectedModCount++;        }        final void checkForComodification() {            // expectedModCount与modCount必须相当            if (modCount != expectedModCount)                throw new ConcurrentModificationException();        }
复制代码
免责声明:假如加害了您的权益,请联系站长,我们会实时删除侵权内容,感谢合作!

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Copyright © 2006-2014 妈妈网-中国妈妈第一,是怀孕、育儿、健康等知识交流传播首选平台 版权所有 法律顾问:高律师 客服电话:0791-88289918
技术支持:迪恩网络科技公司  Powered by Discuz! X3.2
快速回复 返回顶部 返回列表