LinkedList和ArrayList不同,是双向链表,每个元素持有对上一个和下一个元素的引用,便于插入(add(index))和删除操作,查找操作(get(index))需要遍历每个元素,故适用于频繁添加和删除元素,查找元素较少的场合。
LinkedList中的数据结构用例和HashMap中一样,存放的是模拟实体Entry对象。
定义头部指针
private transient Entry<E> header = new Entry<E>(null, null, null);
头部指针header相当于LinkedList中的初始坐标,header的next指向第一个Entry元素。有了header,才能访问第一个Entry对象。
实体Entry类
private static class Entry<E> { E element; Entry<E> next; Entry<E> previous; Entry(E element, Entry<E> next, Entry<E> previous) { this.element = element; this.next = next; this.previous = previous; } }
Entry类有next和previous指针,指向后一个和前一个Entry元素,通过这两个指针,LinkedList才得以实现双向链表。
LinkedList构造函数
public LinkedList() { header.next = header.previous = header; }
初始化LinkedList时,是个空列表,里面没有Entry元素存在,header的next和previous指针都指向了header自身。
查询链表第一个元素
public E getFirst() { if (size==0) throw new NoSuchElementException(); return header.next.element; }
链表的第一个元素是头部指针header的next指向的元素。
查询链表最后一个元素
public E getLast() { if (size==0) throw new NoSuchElementException(); return header.previous.element; }
链表的最后一个元素是头部指针header的previous指向的元素,由此可见双向链表是一个循环结构,最后一个元素的next指针指向了头部指针header。
向链表添加元素
public boolean add(E e) { addBefore(e, header); return true; }
添加元素时,是将新的元素添加到链表的尾部。
private Entry<E> addBefore(E e, Entry<E> entry) { Entry<E> newEntry = new Entry<E>(e, entry, entry.previous); newEntry.previous.next = newEntry; newEntry.next.previous = newEntry; size++; modCount++; return newEntry; }
分为两种场景:
添加第一个元素Entry时:
方法体第一行代码:Entry的element指向自身,next指向了头部指针header,previous指针指向了header.previous,因为header的previous和next都指向header,所以,Entry的previous指向了header。
第二行和第三行代码:header的next和previous都指向了Entry元素。
就是first元素与header的next与previous指针相互指向。
添加第二个元素到N个Entry元素时:
方法体第一行代码:Entry的element还是指向自身,next还是指向了头部指针header,previous指向了header.previous元素,就是链表中添加的第一个元素。这样第二个元素与第一个元素的关系就建立起来了。
第二行代码:第一个元素的next指针指向Entry。
第三行代码:头部指针header的previous指针指向Entry。
可以看出,每个新增加的Entry元素,header都会成为这个Entry的next指向,header的previous也会指向这个新添加的元素,这个新添加的元素就在链尾,所以,header的previous指向的是链尾的元素。
这样就行HashMap中的链表添加元素相反,HashMap中的链表添加元素,是从链头开始添加,链头的元素后移,LinkedList添加元素,是添加到链尾。
查找链表中指定位置的元素
public E get(int index) { return entry(index).element; }
private Entry<E> entry(int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size); Entry<E> e = header; if (index < (size >> 1)) { for (int i = 0; i <= index; i++) e = e.next; } else { for (int i = size; i > index; i--) e = e.previous; } return e; }
查找时,先把索引值index与链表的size值的一半进行比较,如果大于size/2,就从last处开始向前遍历,向前遍历size/2-index次就可找到index处的元素。
如果index小于size/2,就从first处开始向后遍历,向后遍历index次就可找到index处的元素。
采用先让index与size/2比较的算法,缩小了查找的范围,发挥了双向链表的优势,提高了查找index的效率(相对于单向链表)。
查找的前提,都是先把头部指针header赋予一个临时变量开始的,所以头部指针应该是LinkedList数据结构的主脉。
移除链表中指定位置的元素
public E remove(int index) { return remove(entry(index)); }
remove()采用了分而治之的思想,先调用entry(index)找到要移除的元素,再调用remove(E)方法把Entry元素移除。
private E remove(Entry<E> e) { if (e == header) throw new NoSuchElementException(); E result = e.element; e.previous.next = e.next; e.next.previous = e.previous; e.next = e.previous = null; e.element = null; size--; modCount++; return result; }
移除元素时,Entry把preivious元素的next指针指向了Entry本身的next指向的元素,把next元素的previous指针指向了本身指向的previous元素。然后把next、previous、element都设置为null。
这样Entry前后两个元素就建立起了关联关系,双向链表又维护了完整。
从中可以看出,这个Entry被移除掉,性能的开销只是在查找index位置的Entry元素上,所以移除的效率很高(相对于移动数组元素而言)。
查询元素在链表中的位置
public int indexOf(Object o) { int index = 0; if (o==null) { for (Entry e = header.next; e != header; e = e.next) { if (e.element==null) return index; index++; } } else { for (Entry e = header.next; e != header; e = e.next) { if (o.equals(e.element)) return index; index++; } } return -1; }
这个方法是设置一个int型的index计数变量,然后从前向后遍历链表中的元素,每遍历一次index的值+1,当遍历的元素与传入的对象值相同时,返回index值。
总结:
双向链表的内部结构是引用指针双向指向的结构,这种结构的特点是插入数据快,删除数据也快,查找数据慢,因为要遍历所有元素。所以适用于查找少,而增加和删除、修改数据多的场景。
相关推荐
LinkedList源码解析 LinkedList是Java中的一种链表实现,它的底层是一个环形双向链表。在 LinkedList 中,节点之间通过引用相互连接,形成一个链表结构。LinkedList 提供了多种方法来操作链表,包括添加、删除、...
《LinkedList源码解析》 LinkedList是Java集合框架中的一员,它是AbstractSequentialList的子类,同时也实现了List、Deque和Cloneable、Serializable接口。LinkedList作为双向链表,支持快速的添加、删除元素,尤其...
《ArrayList与LinkedList源码解析》 在Java编程中,ArrayList和LinkedList是两种常见的动态数组,它们都是Java集合框架的一部分,提供了对元素存储和操作的功能。本篇将深入探讨ArrayList和LinkedList的内部实现...
### LinkedList部分源码解析 #### 一、简介 `LinkedList`是Java集合框架的一个重要组成部分,它基于双向链表实现,既支持`List`接口也实现了`Deque`接口,因此可以作为列表、栈或者队列使用。双向链表的每个节点...
接下来,我们将通过JDK 7.0的源码,深入探讨LinkedList的底层实现原理。 首先,LinkedList实现了List接口,因此它是一个有序列表。它还实现了Deque接口,这意味着LinkedList支持双端队列的操作。除了这些接口之外,...
"Java基于JDK 1.8的LinkedList源码详析" LinkedList是Java中一个非常重要的数据结构,基于双向链表实现,适用于增删频繁且查询不频繁的场景。今天我们将深入分析LinkedList的源码,了解其内部实现机制和特点。 1. ...
《Jdk1.6 Collections Framework源码解析(2)-LinkedList》 LinkedList是Java集合框架中的一个重要的类,它是List接口的实现,同时继承了AbstractSequentialList,并实现了Deque接口。LinkedList是一种双链表结构,...
Java源码解析LinkedList Java源码解析LinkedList是Java集合框架中的一种重要数据结构。它是一种双向链表,具有高效的插入和删除操作。今天,我们将深入探讨LinkedList的源码,了解它的内部实现机制。 首先,让我们...
Java集合系列之LinkedList源码分析 概述: 本文详细介绍了Java集合系列之LinkedList的源码分析,主要介绍了LinkedList的底层实现、成员变量、构造器、增删改查方法等。LinkedList是一种基于双向链表的数据结构,...
java所有集合类底层源码解析汇总,包括ArrayList、HashMap、HashSet、LinkedList、TreeMap、HashSet、ConcurrentHashMap等集合框架的底层实现源码大白话解读。
Java源码解析——看优秀源码最能使人进步 Java源码解析是一种深入了解JDK源码的方式,适合那些想深入了解JDK源码的人。通过对JDK源码的解析,可以让开发者更好地理解Java语言的底层逻辑,从而写出更加高效、稳定的...
`LinkedList` 源码解析 `LinkedList`内部维护了一个双向链表,每个节点(`Node`)包含三个字段:`element`(存储元素),`next`(指向下一个节点),`previous`(指向前一个节点)。这些字段使得在链表的头尾进行...
Java项目学习库与SpringBoot源码解析是一套深入学习Java编程和SpringBoot框架的资源集合。这个库旨在帮助开发者从初级到高级逐步掌握Java技术栈,并深入理解SpringBoot的核心机制。下面将对Java和SpringBoot的相关...
再者,为了实现动态加载和分页显示,源码中可能会用到Java的集合框架,如ArrayList、LinkedList、HashMap等,以及流(Stream) API进行数据处理。同时,考虑到性能和用户体验,可能还会涉及到缓存技术,如Redis,用来...
能学到什么:ArrayList的源码分析,自动扩容和自动缩容的源码分析,相关参数的深度解析,从是什么,为什么,怎么做三个角度进行讲解,用通俗易懂的白话进行介绍,LinkedList和Vector以及ArrayList的区别以及使用场景...
LinkedList 适用于频繁的插入和删除操作,因为它的插入和删除操作时间复杂度为 O(1),而 ArrayList 的这些操作需要移动元素,时间复杂度为 O(n)。然而,ArrayList 在查询元素时效率更高,因为可以通过索引直接访问,...
Java源码分析Iterable Java源码分析Iterable是Java编程语言中一个基础组件的源码分析,Iterable是一个接口,它允许对象被迭代,例如foreach循环中的数组或集合。了解Iterable的源码,可以帮助开发者更好地理解Java...
LinkedList-master这个文件名可能是该代码实现的源码仓库或项目文件夹,里面可能包含了完整的LinkedList实现以及相关的测试用例和文档。通过查看这个压缩包,开发者可以深入理解LinkedList的实现细节,并将其应用于...
本文将深入探讨LinkedList的工作原理,以及如何通过源码来理解其内部操作。 首先,LinkedList的核心在于它的节点类Node,每个节点包含三个字段:一个指向前一个节点的引用,一个存储元素的值,以及一个指向后一个...