java集合之linkedList
1.linkedList的实现
linkedlist的实现是基于数据结构:双向链表。模型图如
对于linkedList没有像arrayList一样有扩容的概念。也不需要移动数据。所以对于新增和删除操作add和remove,LinkedList比较占优势。
2.双向链表的实现
参考:简单双向链表的增删改查
3.linkedList的继承关系
从继承图中可以看出LinkList实现了List接口,实现了list接口中的所有方法,同时页实现了Queue接口,所以linkedList同时具备了对队列和栈操作的特点。
4.Linkedlist实现的方法
5.重要属性
LinkedList执行栈操作或队列操作就是对first节点和last节点的操作
6.Node节点
LinkedList实现的方法就不再一一叙述。
7.LinkedList遍历
1.通过迭代器遍历。即通过Iterator去遍历
for(Iterator iter = list.iterator(); iter.hasNext();)
iter.next();
2.通过快速随机访问遍历LinkedList
int size = list.size();
for (int i=0; i<size; i++) {
list.get(i);
}
3.通过另外一种for循环来遍历LinkedList
for (Integer integ:list)
;
4. 通过pollFirst()来遍历LinkedList
while(list.pollFirst() != null)
;
5.通过pollLast()来遍历LinkedList
while(list.pollLast() != null)
;
6. 通过removeFirst()来遍历LinkedList
try {
while(list.removeFirst() != null)
;
} catch (NoSuchElementException e) {
}
7.通过removeLast()来遍历LinkedList
try {
while(list.removeLast() != null)
;
} catch (NoSuchElementException e) {
}
8.测试:
package com.dzqc.yx;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.NoSuchElementException;
/*
* @desc 测试LinkedList的几种遍历方式和效率
*
* @author skywang
*/
public class BkApplication {
public static void main(String[] args) {
// 通过Iterator遍历LinkedList
iteratorLinkedListThruIterator(getLinkedList()) ;
// 通过快速随机访问遍历LinkedList
iteratorLinkedListThruForeach(getLinkedList()) ;
// 通过for循环的变种来访问遍历LinkedList
iteratorThroughFor2(getLinkedList()) ;
// 通过PollFirst()遍历LinkedList
iteratorThroughPollFirst(getLinkedList()) ;
// 通过PollLast()遍历LinkedList
iteratorThroughPollLast(getLinkedList()) ;
// 通过removeFirst()遍历LinkedList
iteratorThroughRemoveFirst(getLinkedList()) ;
// 通过removeLast()遍历LinkedList
iteratorThroughRemoveLast(getLinkedList()) ;
}
private static LinkedList getLinkedList() {
LinkedList llist = new LinkedList();
for (int i=0; i<100000; i++)
llist.addLast(i);
return llist;
}
/**
* 通过快迭代器遍历LinkedList
*/
private static void iteratorLinkedListThruIterator(LinkedList<Integer> list) {
if (list == null)
return ;
// 记录开始时间
long start = System.currentTimeMillis();
for(Iterator iter = list.iterator(); iter.hasNext();)
iter.next();
// 记录结束时间
long end = System.currentTimeMillis();
long interval = end - start;
System.out.println("iteratorLinkedListThruIterator:" + interval+" ms");
}
/**
* 通过快速随机访问遍历LinkedList
*/
private static void iteratorLinkedListThruForeach(LinkedList<Integer> list) {
if (list == null)
return ;
// 记录开始时间
long start = System.currentTimeMillis();
int size = list.size();
for (int i=0; i<size; i++) {
list.get(i);
}
// 记录结束时间
long end = System.currentTimeMillis();
long interval = end - start;
System.out.println("iteratorLinkedListThruForeach:" + interval+" ms");
}
/**
* 通过另外一种for循环来遍历LinkedList
*/
private static void iteratorThroughFor2(LinkedList<Integer> list) {
if (list == null)
return ;
// 记录开始时间
long start = System.currentTimeMillis();
for (Integer integ:list)
;
// 记录结束时间
long end = System.currentTimeMillis();
long interval = end - start;
System.out.println("iteratorThroughFor2:" + interval+" ms");
}
/**
* 通过pollFirst()来遍历LinkedList
*/
private static void iteratorThroughPollFirst(LinkedList<Integer> list) {
if (list == null)
return ;
// 记录开始时间
long start = System.currentTimeMillis();
while(list.pollFirst() != null)
;
// 记录结束时间
long end = System.currentTimeMillis();
long interval = end - start;
System.out.println("iteratorThroughPollFirst:" + interval+" ms");
}
/**
* 通过pollLast()来遍历LinkedList
*/
private static void iteratorThroughPollLast(LinkedList<Integer> list) {
if (list == null)
return ;
// 记录开始时间
long start = System.currentTimeMillis();
while(list.pollLast() != null)
;
// 记录结束时间
long end = System.currentTimeMillis();
long interval = end - start;
System.out.println("iteratorThroughPollLast:" + interval+" ms");
}
/**
* 通过removeFirst()来遍历LinkedList
*/
private static void iteratorThroughRemoveFirst(LinkedList<Integer> list) {
if (list == null)
return ;
// 记录开始时间
long start = System.currentTimeMillis();
try {
while(list.removeFirst() != null)
;
} catch (NoSuchElementException e) {
}
// 记录结束时间
long end = System.currentTimeMillis();
long interval = end - start;
System.out.println("iteratorThroughRemoveFirst:" + interval+" ms");
}
/**
* 通过removeLast()来遍历LinkedList
*/
private static void iteratorThroughRemoveLast(LinkedList<Integer> list) {
if (list == null)
return ;
// 记录开始时间
long start = System.currentTimeMillis();
try {
while(list.removeLast() != null)
;
} catch (NoSuchElementException e) {
}
// 记录结束时间
long end = System.currentTimeMillis();
long interval = end - start;
System.out.println("iteratorThroughRemoveLast:" + interval+" ms");
}
}
运行结果:
遍历LinkedList时,使用removeFist()或removeLast()效率最高。但用它们遍历时,会删除原始数据;若单纯只读取,而不删除,应该使用第3种遍历方式。
无论如何,千万不要通过随机访问去遍历LinkedList!
评论区
请写下您的评论...
猜你喜欢
blog
java集合之Hashtable
java基础
1319
java集合之Hashtable一、构造方法1.publicHashtable()publicHashtable(){this(11,0.75f);}无参构造,初始化一个容量为11,负载因子为
blog
java集合之ArrayList
java基础
2659
ArrayList的实现是一个动态数组,从源码中也可以看出。这就决定了他的查找效率高,可以直接通过下标访问。但是对于删除和增加元素,需要大量的移动元素,所以插入和删除的效率就很低。ArrayList不是线程安全的,只能用在单线程环境下,多线程环境下可以考虑用Collections.synchronizedList(Listl)函数返回一个线程安全的ArrayList类。构造方法:ArrayList
blog
java集合之HashSet
java基础
1265
一、HashSet底层实现从HashSet的源码中可以发现,它的底层维护了一个HashMap,在newHashSet的时候,构造方法中其实是new了一个HashMap。privatetransientHashMapE,Objectmap;publicHashSet(){map=newHashMap();}publicHashSet(Collection?extendsEc){map=newHash
blog
java集合之TreeMap实现原理
java基础
1760
java集合之TreeMap实现原理TreeMap集合的实现其实说简单也简单说复杂也复杂,说简单是因为TreeMap底层实现完全依靠红黑树这个数据结构,相比与HashMap来说TreeMap不用考虑
blog
java集合之HashMap理解和分析
java基础
1133
1.HashMap的构造函数1.publicHashMap()publicHashMap(){this.loadFactor=DEFAULT_LOAD_FACTOR;//allotherfieldsdefaulted}构造一个空的HashMap,初始容量为16,负载因子为0.75,负载因子和它的作用将会在下方解释。2.publicHashMap(intinitialCapacity)publicH
blog
java集合框架总结
java基础
2241
Java集合框架数据结构是以某种形式将数据组织在一起的集合,它不仅存储数据,还支持访问和处理数据的操作。Java提供了几个能有效地组织和操作数据的数据结构,这些数据结构通常称为Java集合框架。在平
算法基础
1185
Java中遍历集合的方式以list集合为例,有三种遍历方式。ListStringlist=newArrayList();
list.add("2");
list.add("2");
list.add
blog
并查集 算法分析
数据结构,算法基础
432
代表来表示属于这个集合.当set[i]==i是表明i是一个根节点。set[i]==k可以理解为i,k之间有一条连通的路线,被称为链接。
初始化让所有元素指向自己,表示属于不同的集合,此时集合中每个元素
最新发表
归档
2018-11
12
2018-12
33
2019-01
28
2019-02
28
2019-03
32
2019-04
27
2019-05
33
2019-06
6
2019-07
12
2019-08
12
2019-09
21
2019-10
8
2019-11
15
2019-12
25
2020-01
9
2020-02
5
2020-03
16
2020-04
4
2020-06
1
2020-07
7
2020-08
13
2020-09
9
2020-10
5
2020-12
3
2021-01
1
2021-02
5
2021-03
7
2021-04
4
2021-05
4
2021-06
1
2021-07
7
2021-08
2
2021-09
8
2021-10
9
2021-11
16
2021-12
14
2022-01
7
2022-05
1
2022-08
3
2022-09
2
2022-10
2
2022-12
5
2023-01
3
2023-02
1
2023-03
4
2023-04
2
2023-06
3
2023-07
4
2023-08
1
2023-10
1
2024-02
1
2024-03
1
2024-04
1
标签
算法基础
linux
前端
c++
数据结构
框架
数据库
计算机基础
储备知识
java基础
ASM
其他
深入理解java虚拟机
nginx
git
消息中间件
搜索
maven
redis
docker
dubbo
vue
导入导出
软件使用
idea插件
协议
无聊的知识
jenkins
springboot
mqtt协议
keepalived
minio
mysql
ensp
网络基础
xxl-job
rabbitmq
haproxy
srs
音视频
webrtc
javascript
目录
没有一个冬天不可逾越,没有一个春天不会来临。最慢的步伐不是跬步,而是徘徊,最快的脚步不是冲刺,而是坚持。