1.ArrayList
的数据结构和工作原理
与
Vector
一样,
ArrayList
的
基本数据结构也是一个可变(动态)数组,数组的元素可以是任意对象。
ArrayList
的构造器有两种:
public ArrayList()
默认构造器的数组的长度是
10
public ArrayList(int initialCapacity)
指定
ArrayList
的初始化大小很重要,
ArrayList
当添加元素的数量大于初始化(或上一次)数组的大小时,数组自动扩容成
oldSize*3/2+1,
新数组的元素是从老的数组
copy
而来的。
2.ArrayList
使用时需要注意的问题
1) ArrayList
使用时,最好能够预期需要存放元素的个数,这样可以避免数组长度频繁的改变而引起数据的
copy
带来的开销,同时会引起内存大小的增加。
2
)使用
ArrayList
需要知道
ArrayList
是非线程安全的。因此,在使用时,最好是考虑这个对象会不会因为多个线程访问该
ArrayList
对象,如果确认多个线程访问,则可以用
Vector
或者
CopyOnWriteArrayList
来代替
ArrayList
。
1
.
LinkedList
的数据结构和工作原理
LinkedList
的基本数据结构是双向循环链表。链表的优点是插入和删除快,而查找或者修改比较慢。因为插入操作不会像
ArrayList
那样基于数组的数据结构,当插入时,超过原数组尺寸时,会将原数组的尺寸变成原来的
3*size/2+1,
然后将原来数组的元素拷贝到新数组中,基于链表的操作只需将目标元素的尾部链接到原来链表的尾部就可以了。删除机制是同样的,基于数组的
ArrayList
,要删除元素,需要将该元素后面所有的元素向前
move
一位。
构造器:
private
transient
Entry<E>
header
=
new
Entry<E>(
null
,
null
,
null
);
//
初始花一个空的
header
链表,并将首尾相连成一个双向循环链表
public
LinkedList() {
header
.
next
=
header
.
previous
=
header
;
}
/**
*
核心方法之一:获取
index
位置的链表信息。此方法在
get
,
remove
,
add
,
set
都会用到
*
此处用到了二分查找来提高效率,如果
index
*
是在链表的前半段,则从头开始遍历,如果
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;
}
/**
*
核心方法之一:将新的
e
元素,
add
在指定
entry
的前面
*/
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;
}
/**
*
将指定元素放在
header
之前,实际上就是放在链表的尾部
*/
public
boolean
add
(E
e) {
addBefore(e,
header
);
return
true
;
}
/**
*
找到指定位置的元素,并将指定元素放在查找处的前面
*/
public
void
add
(
int
index, E element)
{
addBefore(element, (index==
size
?
header
: entry(index)));
}
2. LinkedList
的其它应用
LinkedList
的双向性,可以轻松做一个
Stack
和
Queue
:
public
class
LinkedListQueue
<E>
extends
LinkedList<E>{
//Like poll/remove
public
E dequeue(){
return
this
.removeFirst();
}
//Like offer/add
public
void
enqueue(E e){
this
.add(e);
}
//Like peek
public
E getHeader(){
return
this
.getFirst();
}
public
boolean
empty(){
return
this
.size()==0;
}
}
分享到:
相关推荐
在Java开发类库中,提供了很多工具类,我们即将学习最常见的工具类,比如对日期的操作,对集合的操作等。具体更多的工具类,请参考JavaDoc文档。 2. java.util.Date类 Date类包装了毫秒值,毫秒值表示自1970年1月1...
ArrayList 底层结构和源码分析 Vector 底层结构和源码剖析 LinkedList 底层结构 ArrayList 和 LinkedList 比较 Set 接口和常用方法 Map 接口和常用方法 总结-开发中如何选择集合实现类(记住) Collections工具类 泛型...
集合类4.1 集合的实现类4.1.1 ArrayList 4.1.2 LinkedList 4.1.3 Vecotor4.1.4 HashSet 4.1.5 LinkedHashSet 4.2 Conllections工具类5. 集合的遍历5.1 迭代器5.2 增强for循环(jdk1.5+)* 附加知识点1.数据结构1.1 栈...
4.List:ArrayList、LinkedList、Vector、Stack 5.Set:HashSet、TreeSet 6.Map:HashMap、Hashtable、Properties 7.Collections工具类 教学全程采用笔记+代码案例的形式讲解,通俗易懂!!!
15_集合-list-arrayList-linkedlist 16_集合-hashset-hashmap-迭代器-entryset$ d3 b$ ~5 b! @- Z* }- C 17_快捷键设置* L* C. y4 Z1 v0 p) [8 p3 A 18_IO& f, H- i' w( B; P% V; Q" z. L( n/ q 19_IO2 20_文件归档...
泛型集合12.3.4 泛型集合泛型的场景:定义泛型:12.3.5 Colletions工具类 12.3.4 泛型集合 概念:参数化类型、类型安全的集合,强制集合元素的类型必须一致; 特点: 编译时即可检查,而非运行时抛出异常; 访问时,...
并发类编程工具 CountDownLatch CyclicBarrier Semaphore Exchange 并发编程容器collections 并发Queue:BlockingQueue Map:ConcurrentHashMap、HashMap、HashTable 并发List Set:CopyOnWriteArrayList、...
12.5.2 使用集合工具类同步化集合类对象324 12.5.3 使用JDK5.0后提供的并发集合类324 12.6 用Timer类调度任务325 12.7 本章练习326 第13章 13.1 java.io.File类328 13.1.1 文件和目录是什么?328 13.1.2 Java对文件...
7.8 操作集合的工具类:Collections 283 7.8.1 排序操作 283 7.8.2 查找,替换操作 287 7.8.3 同步控制 288 7.8.4 设置不可变集合 288 7.9 烦琐的接口:Enumeration 289 7.10 本章小结 290 本章练习 290 第8...
232 11.7 习题 232 第12章 内部类(精彩视频:71分钟) 234 12.1 非静态内部类 234 12.1.1 创建非静态内部类 234 12.1.2 在外部类中访问内部类 235 12.1.3 在外部类外访问内部类 236 12.1.4 在内部类中访问外部类 ...
Collection 和 Collections区别 java.util.Collection 是一个集合接口(集合类的一个顶级接口)。 它提供了对集合对象进行基本...java.util.Collections 是一个包装类(工具类/帮助类)。 它包含有各种有关集合操作的
3.3.3 ArrayList和LinkedList的性能分析和适用场景 3.4 Iterator迭代器 迭代时删除指定元素 3.5 小结 第4课 Java的内存回收 4.1 Java引用的种类 4.1.1 对象在内存中状态 4.1.2 强引用 4.1.3 软引用 4.1.4 ...
表、栈和队列3.1 抽象数据类型3.2 表ADT3.2.1 表的简单数组实现3.2.2 简单链表3.3 JavaCollectionsAPI中的表3.3.1 Collection接口3.3.2 Iterator接口3.3.3 List接口、ArrayList类和LinkedList类3.3.4 例:remove...
{4.8}Collections集合工具类}{86}{section.4.8} {4.9}Comparable与Comparator}{86}{section.4.9} {4.9.1}Comparable}{86}{subsection.4.9.1} {4.9.2}Comparator}{87}{subsection.4.9.2} {4.10}包装类}{87}{...
表、栈和队列3.1 抽象数据类型3.2 表ADT3.2.1 表的简单数组实现3.2.2 简单链表3.3 JavaCollectionsAPI中的表3.3.1 Collection接口3.3.2 Iterator接口3.3.3 List接口、ArrayList类和LinkedList类3.3.4 例:remove...
第13章常用工具类391 13.1Runtime类的使用391 13.1.1内存管理392 13.1.2执行其他程序393 13.2System类的使用395 13.2.1利用currentTimeMillis()记录程序执行的时间395 13.2.2利用exit()退出虚拟机396 13.2.3...