LinKedList源码分析
2021/5/22 20:26:11
本文主要是介绍LinKedList源码分析,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
LinKedList源码分析
属性分析
// 集合大小 transient int size = 0; /** * Pointer to first node. * Invariant: (first == null && last == null) || * (first.prev == null && first.item != null) 指向第一个节点的指针。 *不变式:(第一个== null &&最后一个== null)||(first.prev == null && first.item!= null) */ transient Node<E> first; /** * Pointer to last node. * Invariant: (first == null && last == null) || * (last.next == null && last.item != null) / ** *指向最后一个节点的指针。 *不变式:(第一个== null &&最后一个== null)||(last.next == null && last.item!= null)* / */ transient Node<E> last; protected transient int modCount = 0; // 响应快速失败,状态记录参数 private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }
方法分析
add
/** * Appends the specified element to the end of this list. * * <p>This method is equivalent to {@link #addLast}. * * @param e element to be appended to this list * @return {@code true} (as specified by {@link Collection#add}) 将指定的元素追加到此列表的末尾。 * * <p>此方法等效于{@link #addLast}。 * * @要附加到此列表的参数元 素* @返回{@code true}(由{@link Collection#add}指定 */ public boolean add(E e) { linkLast(e); return true; } /** * Links e as last element. 将e链接为最后一个元素。 */ void linkLast(E e) { // 取到最后一个元素 final Node<E> l = last; // 新建一个节点 final Node<E> newNode = new Node<>(l, e, null); // 最后一个节点指向等于新节点 last = newNode; // 判断刚才取得的节点是否为空(第一次添加) if (l == null) // 第一次添加节点,新节点为首部节点 first = newNode; else // 不是第一次添加,将当前节点添加到最后一个节点后面 l.next = newNode; // 集合大小加1 size++; // 状态记录参数 modCount++; }
get
/** * Returns the element at the specified position in this list. * * @param index index of the element to return * @return the element at the specified position in this list * @throws IndexOutOfBoundsException {@inheritDoc} *返回此列表中指定位置的元素。 * @param 要返回的元素的索引索引 * @返回 此列表中指定位置的元素* @throws IndexOutOfBoundsException {@inheritDoc} */ public E get(int index) { // 检查下标 checkElementIndex(index); // 拿取元素 return node(index).item; } /** * 返回指定元素索引处的(非空)节点 */ Node<E> node(int index) { // 调用前先验证下标是否越界 // assert isElementIndex(index); // (index < size/2的一次方 位移符号优先级低于运算符?(括起来): if (index < (size >> 1)) { // 一刀切成两份,索引小于中间值,则从首节点开始遍历 Node<E> x = first; // 拿到当前节点,因为调用next 循环比下标数减1,正好使用下标作为判断的闭区间。 for (int i = 0; i < index; i++) x = x.next; return x; } else { // 索引大于等于中间值,则从尾节点开始遍历, 奇数尾节点多一个 Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } } // 检查元素索引是否越界 private void checkElementIndex(int index) { if (!isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } /** * 判断参数是否为现有元素的索引。 */ private boolean isElementIndex(int index) { // index 0 size 1 return index >= 0 && index < size; }
remove
/** * Removes the element at the specified position in this list. Shifts any * subsequent elements to the left (subtracts one from their indices). * Returns the element that was removed from the list. * * @param index the index of the element to be removed * @return the element previously at the specified position * @throws IndexOutOfBoundsException {@inheritDoc} 删除此列表中指定位置的元素。将任何后续元素向左移动(从其索引中减去一个)。 返回从列表中删除的元素。 @param index要删除的元素的索引 @返回 先前在指定位置的元素* @throws IndexOutOfBoundsException {@inheritDoc} */ public E remove(int index) { // 检查下标是否越界 checkElementIndex(index); // 先调用node方法找到指定的节点, return unlink(node(index)); } /** * 取消链接非空节点x。 */ E unlink(Node<E> x) { // assert x != null; // 先保存被删除节点的值,提供返回 final E element = x.item; // 拿到被删除节点的后一个节点 final Node<E> next = x.next; // 拿到被删除节点的前一个节点 final Node<E> prev = x.prev; // 判断被删除的节点,是否为首节点 if (prev == null) { // 是首节点,指向改为被删除节点的下一个节点 first = next; } else { // 不是首节点,将被删除节点的前一个节点的下一个节点的引用,改为被删除的节点的下一个节点引用。 prev.next = next; // 将被删除的节点前一个节点置空,至此前一个节点的引用调整完毕 x.prev = null; } // 判断是被删除的节点,否为尾节点 if (next == null) { // 是尾节点,将最尾节点的引用,改为被删除的节点的前一个节点的引用 last = prev; } else { // 不是尾节点,将被删除的后一个节点的前一个节点的引用,改为被删除节点的前一个节点 next.prev = prev; // 将被删除的节点后一个节点置空,至此后一个节点的引用调整完毕 x.next = null; } // 将节点的值置空,至此全部引用置空 x.item = null; // 集合数量减1 size--; // 状态记录参数加1 modCount++; // 返回被删除的节点的值 return element; } 2.重载的删除方法 /** * Removes the first occurrence of the specified element from this list, * if it is present. If this list does not contain the element, it is * unchanged. More formally, removes the element with the lowest index * {@code i} such that * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt> * (if such an element exists). Returns {@code true} if this list * contained the specified element (or equivalently, if this list * changed as a result of the call). * * @param o element to be removed from this list, if present * @return {@code true} if this list contained the specified element 从此列表中删除第一次出现的指定元素,如果存在*,则将其删除。如果此列表不包含该元素,则*不变。更正式地,删除具有最低索引* {@code i}的元素,使* <tt>(o == null?get(i)== null:o.equals(get(i)))</ tt> *(如果存在这样的元素)。如果此列表*包含指定的元素(或者等效地,如果此列表*由于调用而更改),则返回{@code true}。 * * @param o要从此列表中删除的元素(如果存在)* @return {@code true}如果此列表包含指定的元素 */ public boolean remove(Object o) { // 判断值是否为Null,值为null节点不会为null if (o == null) { // 从首节点开始遍历,只删除一个等于null的元素,返回true for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { // 从首节点开始遍历,删除一个调用equals的值,取消其在整体链表中的链接返回true for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } // 没有找到返回False return false; }
contains
/** * Returns {@code true} if this list contains the specified element. * More formally, returns {@code true} if and only if this list contains * at least one element {@code e} such that * <tt>(o==null ? e==null : o.equals(e))</tt>. * * @param o element whose presence in this list is to be tested * @return {@code true} if this list contains the specified element 如果此列表包含指定的元素,则返回{@code true}。 *更正式地讲,当且仅当此列表包含*至少一个元素{@code e}时,才返回{@code true},使得 * <tt>(o == null?e == null:o.equals(e) )</ tt>。 * * @param o要在此列表中进行测试的元素* @return {@code true}(如果此列表包含指定的元素) */ public boolean contains(Object o) { // 调用indexOf进行下标查询, 返回-1表示不存在。 return indexOf(o) != -1; }
indexOf
/** * Returns the index of the first occurrence of the specified element * in this list, or -1 if this list does not contain the element. * More formally, returns the lowest index {@code i} such that * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, * or -1 if there is no such index. * * @param o element to search for * @return the index of the first occurrence of the specified element in * this list, or -1 if this list does not contain the element 返回指定元素在此列表中首次出现的索引*,如果此列表不包含该元素,则返回-1。 *更正式地,返回最低索引{@code i},以便 * <tt>(o == null?get(i)== null:o.equals(get(i)))</ tt>, *或如果没有这样的索引,则为-1。 * * @param o要搜索的元素* @返回此列表中指定元素的首次出现的索引;如果此列表不包含该元素,则返回-1 */ public int indexOf(Object o) { // 保存循环过的次数,也就是 链表所谓的下标(索引) int index = 0; // 判断需要查询的数据是否为空,LinKedList允许存放重复的Null值 if (o == null) { // 从首节点开始遍历 返回对应的下标 for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) return index; // 循环过的次数加1 index++; } } else { // for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; // 循环过的次数加1 index++; } } // 返回-1 不存在 return -1; }
size
/** * Returns the number of elements in this list. * * @return the number of elements in this list */ public int size() { // 直接返回内部属性 return size; }
clear
/** * Removes all of the elements from this list. * The list will be empty after this call returns. 从此列表中删除所有元素。 *此调用返回后,列表将为空 */ public void clear() { // Clearing all of the links between nodes is "unnecessary", but: // - helps a generational GC if the discarded nodes inhabit // more than one generation // - is sure to free memory even if there is a reachable Iterator //清除节点之间的所有链接都是“不必要的”,但是: //-如果丢弃的节点驻留在多个代中,则有助于一代代GC //-即使存在可达的迭代器,也要确保释放内存 // 从首节点开始遍历清理 for (Node<E> x = first; x != null; ) { // 先拿取到当前节点的下一个节点的引用 Node<E> next = x.next; // 清空当前节点 x.item = null; x.next = null; x.prev = null; // 重新赋值当前节点为清空的下一个节点,继续遍历 x = next; } // 首尾节点全部置空 first = last = null; // 集合大小置空 size = 0; // 状态记录参数 +1 modCount++; }
toArray
/** * Returns an array containing all of the elements in this list * in proper sequence (from first to last element). * * <p>The returned array will be "safe" in that no references to it are * maintained by this list. (In other words, this method must allocate * a new array). The caller is thus free to modify the returned array. * * <p>This method acts as bridge between array-based and collection-based * APIs. * * @return an array containing all of the elements in this list * in proper sequence 以正确的顺序(从第一个到最后一个元素)返回包含此列表*中所有元素的数组。 * * <p>返回的数组将是“安全的”,因为此列表不保留对其的引用。 (换句话说,此方法必须分配*一个新数组)。因此,调用者可以自由修改返回的数组。 * * <p>此方法充当基于数组的API和基于集合的API之间的桥梁。 * * @以正确的顺序返回包含此列表中所有元素的数组* */ public Object[] toArray() { // 创建一个可以接收链表中所有数据的数组 Object[] result = new Object[size]; // 数组下标 int i = 0; // 从首节点快开始遍历赋值 for (Node<E> x = first; x != null; x = x.next) result[i++] = x.item; return result; } // 当且仅当传入的参数T[] a能保存下链表的所有数据时,才会对其进行赋值。 public <T> T[] toArray(T[] a) { // 当传入的数组长度小于链表中的所有数据的数量(就是无法全部保存的情况) if (a.length < size) a = (T[])java.lang.reflect.Array.new Instance( a.getClass().getComponentType(), size); // T[] a数组能保存链表所有数据的情况 int i = 0; // 循环遍历对传入的数组赋值 Object[] result = a; for (Node<E> x = first; x != null; x = x.next) result[i++] = x.item; if (a.length > size) a[size] = null; return a; }
addAll
总结
1.链表式数据结构,双向链表,保存了首尾节点,add方法,向链表末尾加入元素。,可以用来做一个后进先出的栈,里面有pop,push。pollLast,pollFirst等方法
2.get(index)方法采用链表切断,再判断index靠近尾节点还是首节点,进行循环到指定节点返回。
3.remove(index) 方法先调用get(index)方法实现,找出对应的节点,再将需要删除的节点,前后引用调整好,返回删除节点的值,最后将删除的节点的所有的属性置为null,remove(Object)讲道理要比remove(index)方法慢一倍(极端情况),因为remove(Object)方法没有切断链表,需要从首节点开始遍历删除。
4.contains(Object) 底层调用 indexOf(Object)从首节点遍历查询出第一个相等的元素索引,没有查询到返回-1.也就是不存在。
4.toArray方法手动创建一个数组,循环赋值,值类型的话改变数组对象对链表数据没影响,引用类型改变此数组的数据,链表中的数据也会随之改变。toArray (T[])最好是用返回值。传入的 t[] 当且仅当 t[] >= size(链表中元素数量) 时才会对 传入的 t[]数组进行赋值,返回值则无论哪种情况都是赋值好的全部底层数据。(还可以就是t[]数组的大小用链表的size来设置,这样t[]初始化就没问题)
这篇关于LinKedList源码分析的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28微服务架构中API版本控制的实践
- 2024-09-28AI给的和自己写的Python代码,都无法改变输入框的内容,替换也不行
- 2024-09-27Sentinel配置限流资料:新手入门教程
- 2024-09-27Sentinel配置限流资料详解
- 2024-09-27Sentinel限流资料:新手入门教程
- 2024-09-26Sentinel限流资料入门详解
- 2024-09-26Springboot框架资料:初学者入门教程
- 2024-09-26Springboot框架资料详解:新手入门教程
- 2024-09-26Springboot企业级开发资料:新手入门指南
- 2024-09-26SpringBoot企业级开发资料新手指南