终于迎来了 LinkedList 类,实现的接口就有点多了 Serializable, Cloneable, Iterable<E>, Collection<E>, Deque<E>, List<E>, Queue<E>。LinkedList是一个实现了List接口和Deque接口的双端链表,有关索引的操作可能从链表头开始遍历到链表尾部,也可能从尾部遍历到链表头部,这取决于看索引更靠近哪一端。
下面这张图是从(https://blog.csdn.net/qq_19431333/article/details/54572876)复制来的
请注意,此实现不是线程安全的。如果多个线程同时访问链接列表,并且至少一个线程在结构上修改列表,则一般在外部用synchronized修饰。如果想使LinkedList变成线程安全的,可以使用如下方式:
List list = Collections.synchronizedList(new LinkedList(...));
该类有两个构造方法,其中有参数的那个接口接受 Collection<? extends E> 类型的
这个构造方法可以看看的 ,其实实现调用的是 addAll(int index, Collection<? extends E> c) 方法, LinkedList类的有两个重要的transient Node<E> first 和 transient Node<E> last 字段, Object[] a = c.toArray(); 先将c转化为 Object[],后续使用for循环遍历,然后就有一种写指针的感觉了,当初学习c语言写列表的感觉,不过在java里面用了Node这个类来处理。 其实Node这个静态内部类的实现也比较简单,但是java实现链表结构的关键,相当于当前对象,下一个指针,前一个指针。
因为实现了很多接口,然后在linkedList里面拥有很多方法,主要看看列表比较独有的吧,比如下面的在表头和表尾插入数据,先初始化一个Node<E> ,然后创建一个newNode,然后表头指向newNode,其中linkBefore,unlinkFirst,unlinkLast,unlink的实现也是类似的。
如果看懂了上面的方法,那么getfirst和getLast就很简单了,就是把表头和表尾返回一下
那么看remove表头和表尾的方法也是很简单的,其中调用的是unlink开头的方法,比如unlinkFirst,unlinkLast。
但是如果你remove的是一个 object,那么需要遍历了,不过这里找到一个相等的值,那么就return啦。
在clear方法中处理起来比较简单,就是把数据清楚掉,其中是帮助 GC回收各个节点
我们看看查询某个节点的方法,这边将 size 右移一位,判断index离哪一端比较近,然后遍历到相应节点返回,因为是链表结构,所以需要一个遍历,时间复杂度还是有的。
这边又有 peek 和 poll的方法,这些应该是队列里的吧,感觉有些方法有重复的。
来看看序列化接口实现的两个方法writeObject和readObject,使用s.defaultReadObject(),其中readObject后面会有一个linkLast方法
智商有限,时间仓促,就先写到这里吧 !
有什么讨论的内容,可以加我微信公众号: