首先java中的集合从存储数据上来说分为2种。一种是存放单个值的,另外一种是存放键值对的。
存放单个值的上级接口是Collection接口。同时jdk提供了一个对于集合操作的辅助类Collections。Collection暴露了一些简单的接口。
如
boolean add(E e);
boolean remove(Object o);
boolean addAll(Collection<? extends E> c);
boolean removeAll(Collection<?> c);
Object[] toArray();
Iterator<E> iterator();
boolean contains(Object o);
boolean isEmpty();
int size();
接着在看看基于双向链表结构的LinkedList类
特点:每个节点都知道前一个节点和后一个节点
优点:对于插入时只需要修改插入节点的引用和对应节点的引用即可,因此插入效率比基于数组的ArrayList高(ArrayList需要先进行插入元素的位置寻找,然后再进行数组元素的移动,最后插入元素(如果数组长度不够大还需要数组大小的扩展))。
缺点:查找效率较低,需要从header进行查找遍历,而ArrayList或是根据数组下标或是根据元素(以为根据元素的会使用hash算法所以效率相对较高)
下面看看LinkedList类的常用方法以及实现原理
public LinkedList() {
header.next = header.previous = header;
}
首先发现该类的默认的构造方法,是将内部定义的一个Entry<E> header,将前节点的引用和后节点的引用都指向自身。
1.public boolean add(E e)
内部的实现代码如下
public boolean add(E e) {
addBefore(e, header);
return true;
}
即添加时每次都是将第二个参数传入header。header就有点像织毛衣的针一样
再看看addBefore的代码的实现
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;
}
//解释:将新添加的节点的next指向header节点。将新添加元素的previous指向header的previous。然后再将新添加元素的previous的next指向新添加元素。再将新添加元素的next的previous指向新添加元素(实际上就是header的previous指向新添加元素)
最后让大小加一,返回新添加的entry对象
2.public boolean remove(Object o)方法
//再看看删除操作的实现原理
public boolean remove(Object o) {
if (o==null) {
for(Entry<E> e = header.next; e != header; e = e.next){
if (e.element==null) {
remove(e);
return true;
}
}
} else {
for(Entry<E> e = header.next; e != header; e =e.next){
if (o.equals(e.element)) {
remove(e);
return true;
}
}
}
return false;
}
//因为链表实际上是通过Entry链接到一起组成的链表,因此查找时需要从第一个Entry开始查找,即header的next。当找到指定的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;
}
即让当前节点的previous的next指向当前节点的next,当前节点的next的previous指向当前节点的previous
header节点的内容节点和previous和next均为空
常用方法
public void addLast(E e)
其实和add是一样的
再看看里面的clone方法
public Object clone() {
LinkedList<E> clone = null;
try {
clone = (LinkedList<E>) super.clone();
} catch (CloneNotSupportedException e) {
throw new InternalError();
}
// Put clone into "virgin" state
clone.header = new Entry<E>(null, null, null);
clone.header.next = clone.header.previous = clone.header;
clone.size = 0;
clone.modCount = 0;
// Initialize clone with our elements
for (Entry<E> e = header.next; e != header; e = e.next)
clone.add(e.element);
return clone;
}
为了实现深度克隆,该类实现了Cloneable接口。并重写了clone方法
之所以重写是为了让该对象支持深层次克隆
要想让对象完全支持深度克隆需要对象内部的复杂成员类型也支持深度克隆,否则修改克隆对象的对象成员变量会让原来的对象受到影响。如果原来元素不支持可以像上面重新方法一样,新创建成员变量,并将原来成员变量的值传入新创建的成员变量当中。
分享到:
相关推荐
Java API中提供了链表的Java实现—LinkedList下。LinkedList是通过节点的连接实现链表的数据结构,向linkedList中插入或删除元素的速度是特别快,而随机访问的速度相对较慢,这个是由于链表本身的性质造成的,在链表...
java中LinkedList集合类实现栈和队列.docjava中LinkedList集合类实现栈和队列.docjava中LinkedList集合类实现栈和队列.docjava中LinkedList集合类实现栈和队列.docjava中LinkedList集合类实现栈和队列.doc
基于双向链表实现的列表,支持在任意位置的插入和删除操作。
主要介绍了Java集合框架LinkedList详解及实例的相关资料,从定义,概述,用法进行介绍,需要的朋友可以参考下
主要介绍了简单了解java集合框架LinkedList使用方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
Java集合系列(LinkedHashMap+LinkedList+ArrayList)
主要为大家详细介绍了Java集合系列之LinkedList源码,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
主要给大家介绍了关于Java中集合LinkedList的原理与使用方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面来一起学习学习吧
Java ArrayList Vector LinkedList map区别 各种集合的区别 写得非常详细
下面小编就为大家带来一篇java集合 collection-list-LinkedList详解。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
详细描述了Java提供的集合类:HashMap/CurrentHashMap/ArrayList/LinkedList核心原理及版本升级差异。
3)了解List接口及主要实现类(ArrayList、LinkedList、Vector) 4)了解Map接口及主要实现类(HashMap、TreeMap、HashTable) 二、实验内容及步骤 1、编写程序练习将以下5个Person类的对象放在一个HashSet中。 姓名...
我写的关于set集合和list集合相关性能测试,linkedList ArrayList HashSet 等类的增删改查性能测试
掌握List集合、Set集合、Map集合的使用以及Iterator迭代器和foreach循环的使用 了解常用的集合类 熟悉泛型的使用
使用LinkedList类编写程序,用某种集合接口的实现类作存储,实现具有自定义排序功能的包含姓名、年龄、身高、职称等内容的人事信息输入和打印。
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集合多线程安全 线程安全与不安全集合 线程不安全集合: ArrayList LinkedList HashMap HashSet TreeMap TreeSet StringBulider 线程安全集合: Vector HashTable Properties 集合线程安全...
14、JAVA集合框架之list接口、LinkedList类、ArrayList类、Vector类 15、JAVA集合框架之Set接口、HashSet类、TreeSet类 16、JAVA集合框架之Map接口、HashMap类、Trelap类、Hashtable类 17、JAVA异常Exception 18...
Java集合详解2:Queue和LinkedList Java集合详解3:Iterator,fail-fast机制与比较器 Java集合详解4:HashMap和HashTable Java集合详解5:深入理解LinkedHashMap和LRU缓存 Java集合详解6:TreeMap和红黑树 Java集合...
以下是一些 Java 集合方面的面试题: Java 中集合框架的主要接口是什么? ArrayList 和 LinkedList 有什么区别? HashSet 和 TreeSet 有什么区别? HashMap 和 TreeMap 有什么区别? 什么是迭代器?如何使用它来遍历...