LinkedList的源码

2024-09-08 12:32
文章标签 源码 linkedlist

本文主要是介绍LinkedList的源码,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

package java.util;public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{// 链表的表头,表头不包含任何数据。Entry是个链表类数据结构。private transient Entry<E> header = new Entry<E>(null, null, null);// LinkedList中元素个数private transient int size = 0;// 默认构造函数:创建一个空的链表public LinkedList() {header.next = header.previous = header;}// 包含“集合”的构造函数:创建一个包含“集合”的LinkedListpublic LinkedList(Collection<? extends E> c) {this();addAll(c);}// 获取LinkedList的第一个元素public E getFirst() {if (size==0)throw new NoSuchElementException();// 链表的表头header中不包含数据。// 这里返回header所指下一个节点所包含的数据。return header.next.element;}// 获取LinkedList的最后一个元素public E getLast()  {if (size==0)throw new NoSuchElementException();// 由于LinkedList是双向链表;而表头header不包含数据。// 因而,这里返回表头header的前一个节点所包含的数据。return header.previous.element;}// 删除LinkedList的第一个元素public E removeFirst() {return remove(header.next);}// 删除LinkedList的最后一个元素public E removeLast() {return remove(header.previous);}// 将元素添加到LinkedList的起始位置public void addFirst(E e) {addBefore(e, header.next);}// 将元素添加到LinkedList的结束位置public void addLast(E e) {addBefore(e, header);}// 判断LinkedList是否包含元素(o)public boolean contains(Object o) {return indexOf(o) != -1;}// 返回LinkedList的大小public int size() {return size;}// 将元素(E)添加到LinkedList中public boolean add(E e) {// 将节点(节点数据是e)添加到表头(header)之前。// 即,将节点添加到双向链表的末端。addBefore(e, header);return true;}// 从LinkedList中删除元素(o)// 从链表开始查找,如存在元素(o)则删除该元素并返回true;// 否则,返回false。public boolean remove(Object o) {if (o==null) {// 若o为null的删除情况for (Entry<E> e = header.next; e != header; e = e.next) {if (e.element==null) {remove(e);return true;}}} else {// 若o不为null的删除情况for (Entry<E> e = header.next; e != header; e = e.next) {if (o.equals(e.element)) {remove(e);return true;}}}return false;}// 将“集合(c)”添加到LinkedList中。// 实际上,是从双向链表的末尾开始,将“集合(c)”添加到双向链表中。public boolean addAll(Collection<? extends E> c) {return addAll(size, c);}// 从双向链表的index开始,将“集合(c)”添加到双向链表中。public boolean addAll(int index, Collection<? extends E> c) {if (index < 0 || index > size)throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);Object[] a = c.toArray();// 获取集合的长度int numNew = a.length;if (numNew==0)return false;modCount++;// 设置“当前要插入节点的后一个节点”Entry<E> successor = (index==size ? header : entry(index));// 设置“当前要插入节点的前一个节点”Entry<E> predecessor = successor.previous;// 将集合(c)全部插入双向链表中for (int i=0; i<numNew; i++) {Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);predecessor.next = e;predecessor = e;}successor.previous = predecessor;// 调整LinkedList的实际大小size += numNew;return true;}// 清空双向链表public void clear() {Entry<E> e = header.next;// 从表头开始,逐个向后遍历;对遍历到的节点执行一下操作:// (01) 设置前一个节点为null // (02) 设置当前节点的内容为null // (03) 设置后一个节点为“新的当前节点”while (e != header) {Entry<E> next = e.next;e.next = e.previous = null;e.element = null;e = next;}header.next = header.previous = header;// 设置大小为0size = 0;modCount++;}// 返回LinkedList指定位置的元素public E get(int index) {return entry(index).element;}// 设置index位置对应的节点的值为elementpublic E set(int index, E element) {Entry<E> e = entry(index);E oldVal = e.element;e.element = element;return oldVal;}// 在index前添加节点,且节点的值为elementpublic void add(int index, E element) {addBefore(element, (index==size ? header : entry(index)));}// 删除index位置的节点public E remove(int index) {return remove(entry(index));}// 获取双向链表中指定位置的节点private Entry<E> entry(int index) {if (index < 0 || index >= size)throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);Entry<E> e = header;// 获取index处的节点。// 若index < 双向链表长度的1/2,则从前先后查找;// 否则,从后向前查找。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;}// 从前向后查找,返回“值为对象(o)的节点对应的索引”// 不存在就返回-1public 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;}// 从后向前查找,返回“值为对象(o)的节点对应的索引”// 不存在就返回-1public int lastIndexOf(Object o) {int index = size;if (o==null) {for (Entry e = header.previous; e != header; e = e.previous) {index--;if (e.element==null)return index;}} else {for (Entry e = header.previous; e != header; e = e.previous) {index--;if (o.equals(e.element))return index;}}return -1;}// 返回第一个节点// 若LinkedList的大小为0,则返回nullpublic E peek() {if (size==0)return null;return getFirst();}// 返回第一个节点// 若LinkedList的大小为0,则抛出异常public E element() {return getFirst();}// 删除并返回第一个节点// 若LinkedList的大小为0,则返回nullpublic E poll() {if (size==0)return null;return removeFirst();}// 将e添加双向链表末尾public boolean offer(E e) {return add(e);}// 将e添加双向链表开头public boolean offerFirst(E e) {addFirst(e);return true;}// 将e添加双向链表末尾public boolean offerLast(E e) {addLast(e);return true;}// 返回第一个节点// 若LinkedList的大小为0,则返回nullpublic E peekFirst() {if (size==0)return null;return getFirst();}// 返回最后一个节点// 若LinkedList的大小为0,则返回nullpublic E peekLast() {if (size==0)return null;return getLast();}// 删除并返回第一个节点// 若LinkedList的大小为0,则返回nullpublic E pollFirst() {if (size==0)return null;return removeFirst();}// 删除并返回最后一个节点// 若LinkedList的大小为0,则返回nullpublic E pollLast() {if (size==0)return null;return removeLast();}// 将e插入到双向链表开头public void push(E e) {addFirst(e);}// 删除并返回第一个节点public E pop() {return removeFirst();}// 从LinkedList开始向后查找,删除第一个值为元素(o)的节点// 从链表开始查找,如存在节点的值为元素(o)的节点,则删除该节点public boolean removeFirstOccurrence(Object o) {return remove(o);}// 从LinkedList末尾向前查找,删除第一个值为元素(o)的节点// 从链表开始查找,如存在节点的值为元素(o)的节点,则删除该节点public boolean removeLastOccurrence(Object o) {if (o==null) {for (Entry<E> e = header.previous; e != header; e = e.previous) {if (e.element==null) {remove(e);return true;}}} else {for (Entry<E> e = header.previous; e != header; e = e.previous) {if (o.equals(e.element)) {remove(e);return true;}}}return false;}// 返回“index到末尾的全部节点”对应的ListIterator对象(List迭代器)public ListIterator<E> listIterator(int index) {return new ListItr(index);}// List迭代器private class ListItr implements ListIterator<E> {// 上一次返回的节点private Entry<E> lastReturned = header;// 下一个节点private Entry<E> next;// 下一个节点对应的索引值private int nextIndex;// 期望的改变计数。用来实现fail-fast机制。private int expectedModCount = modCount;// 构造函数。// 从index位置开始进行迭代ListItr(int index) {// index的有效性处理if (index < 0 || index > size)throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size);// 若 “index 小于 ‘双向链表长度的一半’”,则从第一个元素开始往后查找;// 否则,从最后一个元素往前查找。if (index < (size >> 1)) {next = header.next;for (nextIndex=0; nextIndex<index; nextIndex++)next = next.next;} else {next = header;for (nextIndex=size; nextIndex>index; nextIndex--)next = next.previous;}}// 是否存在下一个元素public boolean hasNext() {// 通过元素索引是否等于“双向链表大小”来判断是否达到最后。return nextIndex != size;}// 获取下一个元素public E next() {checkForComodification();if (nextIndex == size)throw new NoSuchElementException();lastReturned = next;// next指向链表的下一个元素next = next.next;nextIndex++;return lastReturned.element;}// 是否存在上一个元素public boolean hasPrevious() {// 通过元素索引是否等于0,来判断是否达到开头。return nextIndex != 0;}// 获取上一个元素public E previous() {if (nextIndex == 0)throw new NoSuchElementException();// next指向链表的上一个元素lastReturned = next = next.previous;nextIndex--;checkForComodification();return lastReturned.element;}// 获取下一个元素的索引public int nextIndex() {return nextIndex;}// 获取上一个元素的索引public int previousIndex() {return nextIndex-1;}// 删除当前元素。// 删除双向链表中的当前节点public void remove() {checkForComodification();Entry<E> lastNext = lastReturned.next;try {LinkedList.this.remove(lastReturned);} catch (NoSuchElementException e) {throw new IllegalStateException();}if (next==lastReturned)next = lastNext;elsenextIndex--;lastReturned = header;expectedModCount++;}// 设置当前节点为epublic void set(E e) {if (lastReturned == header)throw new IllegalStateException();checkForComodification();lastReturned.element = e;}// 将e添加到当前节点的前面public void add(E e) {checkForComodification();lastReturned = header;addBefore(e, next);nextIndex++;expectedModCount++;}// 判断 “modCount和expectedModCount是否相等”,依次来实现fail-fast机制。final void checkForComodification() {if (modCount != expectedModCount)throw new ConcurrentModificationException();}}// 双向链表的节点所对应的数据结构。// 包含3部分:上一节点,下一节点,当前节点值。private static class Entry<E> {// 当前节点所包含的值E element;// 下一个节点Entry<E> next;// 上一个节点Entry<E> previous;/*** 链表节点的构造函数。* 参数说明:*   element  —— 节点所包含的数据*   next      —— 下一个节点*   previous —— 上一个节点*/Entry(E element, Entry<E> next, Entry<E> previous) {this.element = element;this.next = next;this.previous = previous;}}// 将节点(节点数据是e)添加到entry节点之前。private Entry<E> addBefore(E e, Entry<E> entry) {// 新建节点newEntry,将newEntry插入到节点e之前;并且设置newEntry的数据是eEntry<E> newEntry = new Entry<E>(e, entry, entry.previous);newEntry.previous.next = newEntry;newEntry.next.previous = newEntry;// 修改LinkedList大小size++;// 修改LinkedList的修改统计数:用来实现fail-fast机制。modCount++;return newEntry;}// 将节点从链表中删除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;}// 反向迭代器public Iterator<E> descendingIterator() {return new DescendingIterator();}// 反向迭代器实现类。private class DescendingIterator implements Iterator {final ListItr itr = new ListItr(size());// 反向迭代器是否下一个元素。// 实际上是判断双向链表的当前节点是否达到开头public boolean hasNext() {return itr.hasPrevious();}// 反向迭代器获取下一个元素。// 实际上是获取双向链表的前一个节点public E next() {return itr.previous();}// 删除当前节点public void remove() {itr.remove();}}// 返回LinkedList的Object[]数组public Object[] toArray() {// 新建Object[]数组Object[] result = new Object[size];int i = 0;// 将链表中所有节点的数据都添加到Object[]数组中for (Entry<E> e = header.next; e != header; e = e.next)result[i++] = e.element;return result;}// 返回LinkedList的模板数组。所谓模板数组,即可以将T设为任意的数据类型public <T> T[] toArray(T[] a) {// 若数组a的大小 < LinkedList的元素个数(意味着数组a不能容纳LinkedList中全部元素)// 则新建一个T[]数组,T[]的大小为LinkedList大小,并将该T[]赋值给a。if (a.length < size)a = (T[])java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);// 将链表中所有节点的数据都添加到数组a中int i = 0;Object[] result = a;for (Entry<E> e = header.next; e != header; e = e.next)result[i++] = e.element;if (a.length > size)a[size] = null;return a;}// 克隆函数。返回LinkedList的克隆对象。public Object clone() {LinkedList<E> clone = null;// 克隆一个LinkedList克隆对象try {clone = (LinkedList<E>) super.clone();} catch (CloneNotSupportedException e) {throw new InternalError();}// 新建LinkedList表头节点clone.header = new Entry<E>(null, null, null);clone.header.next = clone.header.previous = clone.header;clone.size = 0;clone.modCount = 0;// 将链表中所有节点的数据都添加到克隆对象中for (Entry<E> e = header.next; e != header; e = e.next)clone.add(e.element);return clone;}// java.io.Serializable的写入函数// 将LinkedList的“容量,所有的元素值”都写入到输出流中private void writeObject(java.io.ObjectOutputStream s)throws java.io.IOException {// Write out any hidden serialization magics.defaultWriteObject();// 写入“容量”s.writeInt(size);// 将链表中所有节点的数据都写入到输出流中for (Entry e = header.next; e != header; e = e.next)s.writeObject(e.element);}// java.io.Serializable的读取函数:根据写入方式反向读出// 先将LinkedList的“容量”读出,然后将“所有的元素值”读出private void readObject(java.io.ObjectInputStream s)throws java.io.IOException, ClassNotFoundException {// Read in any hidden serialization magics.defaultReadObject();// 从输入流中读取“容量”int size = s.readInt();// 新建链表表头节点header = new Entry<E>(null, null, null);header.next = header.previous = header;// 从输入流中将“所有的元素值”并逐个添加到链表中for (int i=0; i<size; i++)addBefore((E)s.readObject(), header);}}

这篇关于LinkedList的源码的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1148113

相关文章

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来,一站式有声阅读平台听书系统 🌟&nbsp;开篇:遇见未来,从“智听”开始 在这个快节奏的时代,你是否渴望在忙碌的间隙,找到一片属于自己的宁静角落?是否梦想着能随时随地,沉浸在知识的海洋,或是故事的奇幻世界里?今天,就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统,它正悄悄改变着我们的阅读方式,让未来触手可及! 📚&nbsp;第一站:海量资源,应有尽有 走进“智听

Java ArrayList扩容机制 (源码解读)

结论:初始长度为10,若所需长度小于1.5倍原长度,则按照1.5倍扩容。若不够用则按照所需长度扩容。 一. 明确类内部重要变量含义         1:数组默认长度         2:这是一个共享的空数组实例,用于明确创建长度为0时的ArrayList ,比如通过 new ArrayList<>(0),ArrayList 内部的数组 elementData 会指向这个 EMPTY_EL

如何在Visual Studio中调试.NET源码

今天偶然在看别人代码时,发现在他的代码里使用了Any判断List<T>是否为空。 我一般的做法是先判断是否为null,再判断Count。 看了一下Count的源码如下: 1 [__DynamicallyInvokable]2 public int Count3 {4 [__DynamicallyInvokable]5 get

工厂ERP管理系统实现源码(JAVA)

工厂进销存管理系统是一个集采购管理、仓库管理、生产管理和销售管理于一体的综合解决方案。该系统旨在帮助企业优化流程、提高效率、降低成本,并实时掌握各环节的运营状况。 在采购管理方面,系统能够处理采购订单、供应商管理和采购入库等流程,确保采购过程的透明和高效。仓库管理方面,实现库存的精准管理,包括入库、出库、盘点等操作,确保库存数据的准确性和实时性。 生产管理模块则涵盖了生产计划制定、物料需求计划、

Spring 源码解读:自定义实现Bean定义的注册与解析

引言 在Spring框架中,Bean的注册与解析是整个依赖注入流程的核心步骤。通过Bean定义,Spring容器知道如何创建、配置和管理每个Bean实例。本篇文章将通过实现一个简化版的Bean定义注册与解析机制,帮助你理解Spring框架背后的设计逻辑。我们还将对比Spring中的BeanDefinition和BeanDefinitionRegistry,以全面掌握Bean注册和解析的核心原理。

音视频入门基础:WAV专题(10)——FFmpeg源码中计算WAV音频文件每个packet的pts、dts的实现

一、引言 从文章《音视频入门基础:WAV专题(6)——通过FFprobe显示WAV音频文件每个数据包的信息》中我们可以知道,通过FFprobe命令可以打印WAV音频文件每个packet(也称为数据包或多媒体包)的信息,这些信息包含该packet的pts、dts: 打印出来的“pts”实际是AVPacket结构体中的成员变量pts,是以AVStream->time_base为单位的显

kubelet组件的启动流程源码分析

概述 摘要: 本文将总结kubelet的作用以及原理,在有一定基础认识的前提下,通过阅读kubelet源码,对kubelet组件的启动流程进行分析。 正文 kubelet的作用 这里对kubelet的作用做一个简单总结。 节点管理 节点的注册 节点状态更新 容器管理(pod生命周期管理) 监听apiserver的容器事件 容器的创建、删除(CRI) 容器的网络的创建与删除

red5-server源码

red5-server源码:https://github.com/Red5/red5-server

TL-Tomcat中长连接的底层源码原理实现

长连接:浏览器告诉tomcat不要将请求关掉。  如果不是长连接,tomcat响应后会告诉浏览器把这个连接关掉。    tomcat中有一个缓冲区  如果发送大批量数据后 又不处理  那么会堆积缓冲区 后面的请求会越来越慢。

Windows环境利用VS2022编译 libvpx 源码教程

libvpx libvpx 是一个开源的视频编码库,由 WebM 项目开发和维护,专门用于 VP8 和 VP9 视频编码格式的编解码处理。它支持高质量的视频压缩,广泛应用于视频会议、在线教育、视频直播服务等多种场景中。libvpx 的特点包括跨平台兼容性、硬件加速支持以及灵活的接口设计,使其可以轻松集成到各种应用程序中。 libvpx 的安装和配置过程相对简单,用户可以从官方网站下载源代码