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;
}
}
分享到:
相关推荐
Collections 是 Java 中提供的一个工具类,提供了对集合类的操作方法,如 sort()、binarySearch()、max() 等。Collections 类提供了对集合类的搜索、排序、线程安全等操作。 四、如何选择集合类 在选择集合类时,...
本课程“【IT十八掌徐培成】Java基础第10天-03.List-集合框架-ArrayList”深入讲解了Java中的ArrayList类,这是集合框架中的一个重要组成部分,特别适用于对元素有序且可变大小的需求。 ArrayList是Java.util包下的...
2. **Java集合框架**:Java集合框架是处理对象组的重要工具,包括List(如ArrayList和LinkedList)、Set(如HashSet和TreeSet)和Map(如HashMap和TreeMap)接口以及实现这些接口的类。 3. **异常处理**:Java通过...
为了使用线程安全的ArrayList,可以使用Collections工具类提供的synchronizedList方法,该方法会返回一个线程安全的List的包装器。需要注意的是,这只是一个包装器,如果需要在多个线程之间共享ArrayList实例,应该...
5. **数组和集合**:讲解数组的使用,以及Java集合框架,包括List、Set、Map接口及其实现类,如ArrayList、LinkedList、HashSet、HashMap等。 6. **字符串处理**:介绍String类的特性和常用方法,以及StringBuilder...
### Java集合排序及Java集合类详解 #### 一、集合框架概述 集合框架是Java编程语言的核心组件之一,用于组织和操作数据集。Java集合框架提供了多种数据结构,包括列表(List)、集(Set)和映射(Map),这些数据结构...
2. **集合操作**:在Java中,ArrayList、LinkedList、HashSet、HashMap等集合类广泛使用。工具类可能会提供一些便利的集合转换、过滤、排序等功能,例如`reverse(List<?> list)`反转列表,`isEmptyOrNull(Collection...
- Collections工具类提供了很多静态方法,如对List进行排序(sort())、查找最大或最小元素(max()和min())、二分搜索(binarySearch())等。 - ArrayList和LinkedList各有特点,ArrayList适合频繁的随机访问,而...
在Java编程语言中,集合框架是处理对象数组的重要工具,其中`List`接口是最常用的集合类型之一。本篇文章将深入探讨`List`集合的各种操作,包括增、删、改、查,以及`ArrayList`和`LinkedList`两种实现`List`接口的...
Java集合框架还包含了一些工具类,如Collections和Arrays,它们提供了各种实用方法,如排序、复制、反转和查找集合中的特定元素。此外,Set和List接口都有一个叫做CopyOnWriteArrayList和CopyOnWriteArraySet的特殊...
### 精通Java集合框架——List, Set, Map #### 概述 Java集合框架是一种高度抽象且灵活的数据组织工具,它通过一系列接口来定义不同类型的数据容器,并提供了丰富的操作这些容器的方法。本文将深入探讨Java集合...
- `List`:有序、允许重复元素的集合,例如ArrayList和LinkedList。 - `Set`:不允许重复元素的集合,如HashSet和TreeSet。 - `Queue`:用于队列操作的接口,如LinkedList(作为双端队列)和PriorityQueue。 2. ...
Java集合容器概述、集合框架、List、Set、Map接口、Iterator、ArrayList、LinkedList、Vector、HashSet、HashMap、Queue、BlockingQueue、ConcurrentHashMap等。 Java 集合容器概述 Java 集合容器是用于存储数据...
Java集合框架主要包括`Collection`、`Set`、`List`、`Queue`、`Deque`、`Map`等接口和它们的具体实现类如`ArrayList`、`LinkedList`、`Vector`、`Stack`、`HashSet`、`HashMap`等。下面将对这些核心概念和类进行深入...
在Java编程语言中,ArrayList和LinkedList是两种常用的集合类,它们都实现了List接口,用于存储和操作有序的数据序列。这两个类各有特点,适用于不同的场景。本文将深入探讨ArrayList和LinkedList的内部实现、性能...
3. **Collections**:Collections是Java提供的工具类,提供了对集合的各种操作,如排序(sort())、查找最大/最小元素(max()和min())以及二分查找(binarySearch())等。 此外,文件还涉及到了数据结构的基础知识...
标题提到的“仿java集合 list, 以及map工具类”,是指易语言中对Java集合框架的模拟实现。在Java中,List和Map是两种主要的数据结构。List是一种有序的集合,允许重复元素,可以按索引访问。常见的List实现有...
- `Collections.sort()`:适用于`List`接口的实现类,如`ArrayList`和`LinkedList`。它直接在原地对列表进行排序,无需额外的流处理。例如: ```java List<Person> people = ...; Collections.sort(people, ...