当前位置:   article > 正文

《知识点022:Java中LinkedList.get()获取元素》

《知识点022:Java中LinkedList.get()获取元素》

 一、LinkedList类介绍

LinkedList类是双向列表,列表中的每个节点都包含了对前一个和后一个元素的引用.,它和ArrayList一样实现了List接口,但是她执行插入和删除操作时比ArrayList更加高效,因为她是基于链表的,但同时也决定了她在随机访问方面要比ArrayList弱一点。

1.1:结构原理

LinkedList底层的数据结构是基于双向循环链表的,且头结点中不存放数据,如下:

既然是双向链表,那么必定存在一种数据结构——我们可以称之为节点,节点实例保存业务数据,前一个节点的位置信息和后一个节点位置信息,如下图所示:


 

1.2:构造方法

  1. public LinkedList() {//生成空的链表
  2. header.next = header.previous = header;
  3. }
  4. public LinkedList(Collection<? extends E> c) {//复制构造函数
  5. this();
  6. addAll(c);
  7. }

第一个构造方法不接受参数,将header实例的previous和next全部指向header实例(注意,这个是一个双向循环链表,如果不是循环链表,空链表的情况应该是header节点的前一节点和后一节点均为null),这样整个链表其实就只有header一个节点,用于表示一个空的链表。执行完构造函数后,header实例自身形成一个闭环,如下图所示:

第二个构造方法接收一个Collection参数c,调用第一个构造方法构造一个空的链表,之后通过addAll将c中的元素全部添加到链表中。

二、LinkedList.get()获取元素

Get(int)方法的实现在remove(int)中已经涉及过了。首先判断位置信息是否合法(大于等于0,小于当前LinkedList实例的Size),然后遍历到具体位置,获得节点的业务数据(element)并返回。

2.1:方法

get(int index):返回此列表中指定位置处的元素。
getFirst():返回此列表的第一个元素。
getLast():返回此列表的最后一个元素。
indexOf(Object o):返回此列表中首次出现的指定元素的索引,如果此列表中不包含该元素,则返回 -1。
lastIndexOf(Object o):返回此列表中最后出现的指定元素的索引,如果此列表中不包含该元素,则返回 -1。

2.2:源码分析

注意细节:位运算与直接做除法的区别。先将index与长度size的一半比较,如果index<size/2,就只从位置0往后遍历到位置index处,而如果index>size/2,就只从位置size往前遍历到位置index处。这样可以减少一部分不必要的遍历
 

  1. // 获取双向链表中指定位置的节点
  2. private Entry < E > entry(int index) {
  3. if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
  4. Entry < E > e = header;
  5. // 获取index处的节点。
  6. // 若index < 双向链表长度的1/2,则从前先后查找;
  7. // 否则,从后向前查找。
  8. if (index < (size >> 1)) {
  9. for (int i = 0; i <= index; i++) e = e.next;
  10. } else {
  11. for (int i = size; i > index; i--) e = e.previous;
  12. }
  13. return e;
  14. }

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/盐析白兔/article/detail/935450
推荐阅读
相关标签
  

闽ICP备14008679号