公司的网站建设公司网站建设,今天上海新闻,池州做网站公司,物联网应用技术就业方向目录一. #x1f981; LinkedList介绍二. #x1f981; 结构以及对应方法分析2.1 结构组成2.1.1 节点类2.1.2 成员变量2.2 方法实现2.2.1 添加add(E e)方法2.2.2 头尾添加元素Ⅰ addFirst(E e)Ⅱ addLast(E e)2.2.3 查找get(int index)方法2.2.4 删除remove()方法三. #x…
目录一. LinkedList介绍二. 结构以及对应方法分析2.1 结构组成2.1.1 节点类2.1.2 成员变量2.2 方法实现2.2.1 添加add(E e)方法2.2.2 头尾添加元素Ⅰ addFirst(E e)Ⅱ addLast(E e)2.2.3 查找get(int index)方法2.2.4 删除remove()方法三. 总结一. LinkedList介绍
LinkedList 底层用双向链表实现的存储。特点查询效率低增删效率高线程不安全。 双向链表也叫双链表是链表的一种它的每个数据节点中都有两个指针分别指向前 一个节点和后一个节点。 所以从双向链表中的任意一个节点开始都可以很方便地找到所有节点。
今天来探索一下LinkedList的源码分析以便更熟悉Java容器的结构,了解其是如何存储元素的。 探索环境jdk 11 idea 2020
二. 结构以及对应方法分析
2.1 结构组成
由源码可知LinkedList 不仅继承了AbstractSequentialList还实现了ListDeque等接口。所以LinkedList除了可以当做链表来操作外它还可以当做栈、队列和双端队列来使用。
2.1.1 节点类
双向链表由节点类前后连接而成所以源码中肯定存在该Node类。我们从源码中得知其节点类组成 item存储当前节点元素的信息 next存储当前节点的下一个节点地址信息 prev存储当前节点的前一个节点地址信息 private static class NodeE {E item;NodeE next;NodeE prev;Node(NodeE prev, E element, NodeE next) {this.item element;this.next next;this.prev prev;}}2.1.2 成员变量 这里记录了LinkedList的节点数size头节点地址first尾节点last。 transient int size 0;/*** Pointer to first node.*/transient NodeE first;/*** Pointer to last node.*/transient NodeE last;
2.2 方法实现
2.2.1 添加add(E e)方法 从这里可知这个add() 方法调用了linkLast(e)方法返回一个布尔值。现在我们来看看这个linkLast(e)方法 /*** Links e as last element.*/void linkLast(E e) {final NodeE l last;final NodeE newNode new Node(l, e, null);last newNode;if (l null)first newNode;elsel.next newNode;size;modCount;}从这个方法来看add()方法的插入是尾插法将last这个成员变量赋值给l即l指向最当前节点,新new一个节点变量newNode(l,e,null),并且将其前驱节点指向l如果 l null,则第一个节点是newNode否则直接在当前节点l指向新节点newNode。modCount是指修改次数。 2.2.2 头尾添加元素
Ⅰ addFirst(E e)
我们可以看到这里直接调用了linkFirst(E e)方法。 /*** Links e as first element.*/private void linkFirst(E e) {final NodeE f first;final NodeE newNode new Node(null, e, f);first newNode;if (f null)last newNode;elsef.prev newNode;size;modCount;}这里是运用了头插法将节点插入链表头部依旧f和前面的l一样指向当前节点第一个节点然后new 一个新的Node(null,e,f),将新节点的后继节点指向当前节点。当前节点不为null的情况下将当前节点的前驱节点指向新节点这样一次插入完成。 Ⅱ addLast(E e)
尾插法同前面的add(E e)。
2.2.3 查找get(int index)方法 这里调用了两个方法一个是 checkElementIndex(index)该方法是用来检查用户输入的下标是否存在如果不合法的话则会抛出 **IndexOutOfBoundsException(outOfBoundsMsg(index))**异常具体实现如图 第二个方法是 该方法很明显是用来返回获取对应下标元素的值具体实现如下 /*** Returns the (non-null) Node at the specified element index.*/NodeE node(int index) {// assert isElementIndex(index);if (index (size 1)) {NodeE x first;for (int i 0; i index; i)x x.next;return x;} else {NodeE x last;for (int i size - 1; i index; i--)x x.prev;return x;}}这个方法运用了一个技巧如果index是小于一半LinkedList长度时则从头节点开始遍历查找相反如果index大于一半LinkedList长度时则从尾节点开始查找这也是双向链表的一个优点。 2.2.4 删除remove()方法 LinkedList的删除方法比较多我们就来探索一个常用的remove()由源码可知这里调用了removeFirst()方法: /*** Removes and returns the first element from this list.** return the first element from this list* throws NoSuchElementException if this list is empty*/public E removeFirst() {final NodeE f first;if (f null)throw new NoSuchElementException();return unlinkFirst(f);}这里定义了f——头节点如果头节点为空说明f为空则说该LinkedList没有任何元素则返回一个NoSuchElementException()错误。否则调用了unlinkFirst(f)方法。 /*** Unlinks non-null first node f.*/private E unlinkFirst(NodeE f) {// assert f first f ! null;final E element f.item;final NodeE next f.next;f.item null;f.next null; // help GCfirst next;if (next null)last null;elsenext.prev null;size--;modCount;return element;}这里先定义了一个next节点指向头节点的下一个节点然后赋值头节点的元素和next指针为null这里主要是减少GC垃圾回收的工作量提高效率然后让头节点的指针指向next节点这样next节点则成为新的一个头节点。就删除了头节点啦size–返回element。 三. 总结
今天介绍了LinkedList源码剥析。分析了常用方法的源码结构组成LinkedList的源码组成比较简单只要对双向链表这一数据结构熟悉的话阅读起源码还是非常轻松的希望您喜欢一键三连哦
