接上文 - 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
分享到:
相关推荐
下面小编就为大家带来一篇java集合 collection-list-LinkedList详解。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
java中LinkedList集合类实现栈和队列.docjava中LinkedList集合类实现栈和队列.docjava中LinkedList集合类实现栈和队列.docjava中LinkedList集合类实现栈和队列.docjava中LinkedList集合类实现栈和队列.doc
掌握List集合、Set集合、Map集合的使用以及Iterator迭代器和foreach循环的使用 了解常用的集合类 熟悉泛型的使用
超全Java集合框架讲解 - 超全Java集合框架讲解 - 集合框架总览 - Iterator Iterable ListIterator - Map 和 Collection 接口 - Map 集合体系详解 - HashMap - LinkedHashMap - TreeMap - WeakHashMap - ...
我写的关于set集合和list集合相关性能测试,linkedList ArrayList HashSet 等类的增删改查性能测试
java集合类 Java中有哪些容器(集合类)? 线程安全和线程不安全的分别有哪些? Map接口有哪些实现类? 描述一下Map put的过程 如何得到一个线程安全的Map? HashMap有什么特点? ConcurrentHashMap是怎么分段分组...
详细描述了Java提供的集合类:HashMap/CurrentHashMap/ArrayList/LinkedList核心原理及版本升级差异。
链表用于存储元素序列,因此每个节点都包含对元素的引用,有时也包含对元素集合的引用。 节点的元素部分有时称为“货物”,因此您可以将节点视为轨道车,其中每节车厢都装有货物,并且车厢连接在一起。 让我们看看这...
Java的集合类总结,包括HashMap、HashSet、HashTable、LinkedHashMap、LinkedHashSet、ArrayList、LinkedList、ConcurrentHashMap的实现原理,很详实,面试的话可以认真看看
一般大家都知道ArrayList和LinkedList的大致区别: ... ArrayList和LinkedList是两个集合类,用于存储一系列的对象引用(references)。例如我们可以用ArrayList来存储一系列的String或者Integer。那
ava基础 基础知识 面向对象基础 Java基本数据类型 string和包装类 final关键字特性 Java类和包 抽象类和接口 代码块和代码执行顺序 Java自动拆箱装箱里隐藏的秘密 ...Java集合详解8:Java集合类细节精讲 JavaWeb
3)了解List接口及主要实现类(ArrayList、LinkedList、Vector) 4)了解Map接口及主要实现类(HashMap、TreeMap、HashTable) 二、实验内容及步骤 1、编写程序练习将以下5个Person类的对象放在一个HashSet中。 姓名...
集合框架主要是由接口,抽象类和实现类构成.接口:蓝色;实现类:红色Collection|_____Set(HashSet)| |_____SortedSet(TreeSet)|_____List(LinkedList,ArrayList) Collection:集合层次中的根接口,JDK没有提供这个接口...
Java面试题10.ArrayList 和LinkedList的区别 Java面试题11.HashMap和HashTable的区别 Java面试题12.实现一个拷贝文件的工具类要使用字节流还是字符串 Java面试题13.线程的的实现方式?怎么启动线程?怎么区分线程? ...
学习ArrayList与LinkedList类,理解封装数组和链表两种方式定义集合类。 可以使用迭代器Iterator遍历集合的元素。 [*]理解泛型概念,声明和使用带有范型的集合。 第11章 集合 4...
Java集合类是Java.util包中的重要内容,它提供了一套性能优良、使用方便的接口和类,用于处理对象的集合。这些类主要用于存储、检索、操作一组对象数据。 Java集合类主要包括两种类型的容器:Collection和Map。...
68、你所知道的集合类都有哪些?主要方法? 47 69、两个对象值相同(x.equals(y) == true),但却可有不同的hash code,这句话对不对? 48 70、TreeSet里面放对象,如果同时放入了父类和子类的实例对象,那比较时使用的...
7.1.1 Java集合体系概述;7.1.1 Java集合体系概述;7.1.1 Java集合体系概述;7.1.1 Java集合体系概述;7.1.1 Java集合体系概述;7.1.1 Java集合体系概述;7.1.2 学生实践练习;7.1.2 学生实践练习;7.2 List集合;7.2 List...
JAVA学生信息管理系统开源。SQL连接即可使用!
使用LinkedList类编写程序,用某种集合接口的实现类作存储,实现具有自定义排序功能的包含姓名、年龄、身高、职称等内容的人事信息输入和打印。