接上文 - java 集合类-ArrayList
LinkedList的底层实现方法:双向链表。
LinkedList用静态内部类Entry来表示一个节点,定义一个 header节点。
Entry内部定义了 前驱节点和后驱节点 以及存储数据。
LinkedList 源码:
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Queue<E>, Cloneable, java.io.Serializable
{
private transient Entry<E> header = new Entry<E>(null, null, null);
private transient int size = 0;
/**
* Constructs an empty list.
*/
public LinkedList() {
header.next = header.previous = header;
}
内部类 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;
}
}
LinkedList add方法源码 :
public boolean add(E o) {
addBefore(o, header);
return true;
}
//将新添的数据增加到链表模型中,参考下图。
private Entry<E> addBefore(E o, Entry<E> e) {
Entry<E> newEntry = new Entry<E>(o, e, e.previous);
newEntry.previous.next = newEntry;
newEntry.next.previous = newEntry;
size++;
modCount++;
return newEntry;
}
增加后双向链表的数据模型如下:
LinkedList get方法源码:
public E get(int index) {
return entry(index).element;
}
//找到对应的Entry对象。
private Entry<E> entry(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+size);
Entry<E> e = header;
//index 与 size/2 进行比较 确定前驱查找或是后驱查找
//具体查找可参考上图模型。
//如若 size > 10, index=1 ,
//则查找对象相当于 Entry e = header.next.next;
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;
}
LinkedList 删除方法源码:
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;
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;
}
private E remove(Entry<E> e) {
if (e == header)
throw new NoSuchElementException();
E result = e.element;
//关联删除节点左右两边的节点
//如上图:若删除第一个节点,则将header与第二个节点相互关联上即可。
e.previous.next = e.next;
e.next.previous = e.previous;
e.next = e.previous = null;
e.element = null;
size--;
modCount++;
return result;
}
- 大小: 18.6 KB
分享到:
相关推荐
总之,`LinkedList`是Java集合框架中一个重要的列表实现,适用于需要高效执行链式操作的场景。理解其工作原理和特性对于优化Java程序的性能至关重要。在实际编程中,开发者应根据具体需求选择合适的集合类型。
Java集合类——List接口 Java中的集合类是用来存放对象的,相当于一个容器,里面包容着一组对象。Java API提供的集合类位于java.util包内。Java中的集合类可以分为两类,一类是数组,另一类是集合。数组也是容器,...
ArrayList和LinkedList是Java集合框架中两种重要的动态数组实现,它们都是List接口的实现类,但它们在存储和操作数据方面有着显著的区别。本文件"arraylist-linkedlist-test.zip"主要探讨了在执行添加和删除元素操作...
总的来说,理解并熟练运用Java集合框架中的Map接口及其实现,对于JSP应用开发来说至关重要。正确选择和使用这些类可以帮助我们编写出高效、可维护的代码。在实际项目中,应根据具体需求和场景来决定使用哪种集合类型...
本文将深入探讨Java集合类的汇总,包括List、Set和Map这三大核心接口及其实现类。 首先,让我们从List接口开始。List是一种有序的集合,允许有重复元素,并且支持通过索引来访问元素。ArrayList和LinkedList是List...
Java 集合类 List-Set-Map 的区别和联系 Java 集合类 List、Set 和 Map 是 Java 语言中最基本的集合类,它们之间存在着紧密的联系和区别。在本文中,我们将对 Java 集合类 List、Set 和 Map 的区别和联系进行详细的...
理解并熟练运用Java集合体系中的List、Set、Map接口及其实现类,对于日常开发和面试来说至关重要,因为它们是许多Java框架和库的基础。在实际项目中,根据需求选择合适的集合类型可以提高代码的效率和可维护性。在...
在Java编程语言中,LinkedList集合类是一个非常重要的数据结构,它可以用来实现栈和队列这两种特殊的数据结构。LinkedList是一个双链表,每个节点包含数据元素和两个引用,分别指向前后节点,这使得在列表中进行插入...
Java 集合类详解 Java 集合类是 Java 语言中的一种基本数据结构,用于存储和操作大量数据。集合类可以分为三大类:Collection、List 和 Set。 Collection 是集合框架中的根接口,提供了基本的集合操作,如 add、...
### 精通Java集合框架——List, Set, Map #### 概述 Java集合框架是一种高度抽象且灵活的数据组织工具,它通过一系列接口来定义不同类型的数据容器,并提供了丰富的操作这些容器的方法。本文将深入探讨Java集合...
在Java编程语言中,`ArrayList`、`LinkedList`、`Vector`和`Map`是四种常用的集合类,它们各自有着不同的特性和用途。本篇文章将深入探讨这些数据结构及其使用场景。 首先,我们来了解`ArrayList`。`ArrayList`是`...
LinkedList是Java集合框架中的一个重要的类,它是List接口的实现,同时继承了AbstractSequentialList,并实现了Deque接口。LinkedList是一种双链表结构,它的主要特点是元素存储在节点中,每个节点包含元素以及指向...
`Collection`接口是Java集合框架的核心接口之一,它是所有集合类的根接口。该接口定义了一组对象的通用操作,并且是`Set`和`List`接口的父接口。 **Collection接口的主要特点**: - 可以存放不同类型的数据。 - 子...
在 Java 中,ArrayList 和 LinkedList 是两种常用的集合类,它们各自具有不同的特性和适用场景,主要体现在数据结构、访问效率和操作性能上。 1. 数据结构: - ArrayList 实现了一个动态数组,它内部是一个 Object...
### Java集合排序及Java集合类详解 #### 一、集合框架概述 集合框架是Java编程语言的核心组件之一,用于组织和操作数据集。Java集合框架提供了多种数据结构,包括列表(List)、集(Set)和映射(Map),这些数据结构...
Java集合可以分为两大类:Collection和Map。 Java集合的类型 Java集合有多种类型,常见的有ArrayList、LinkedList、HashSet、TreeSet、HashMap、TreeMap等。 * ArrayList:是一个基于数组的列表实现,支持随机...
因此,如果在多线程环境中使用`LinkedList`,应考虑使用`Collections.synchronizedList(List<T> list)`来同步列表,或者使用`ConcurrentLinkedQueue`等线程安全的集合类。 `LinkedList`的性能特点需要注意:虽然...
### Java集合类性能分析 #### 一、Java集合框架概览 Java集合框架是一个非常重要的概念,它提供了处理数据集合的标准方法。集合框架的核心部分主要包括集合接口、抽象类以及具体的实现类。 - **集合接口**:Java...
### Java集合类学习笔记知识点详解 #### 一、集合框架概述 ##### 1.1.1 容器简介 在Java编程中,容器是用于存储和管理对象集合的重要工具。当我们处理大量的对象时,比如存储多个员工的信息,仅仅依赖于基本的...
### Java集合类详解总结 在Java编程中,集合框架(Collection Framework)是处理一组对象的强大工具,它提供了标准的数据结构来存储和操作这些对象。Java集合框架主要包括`Collection`、`Set`、`List`、`Queue`、`...