java集合之linkedList

硅谷探秘者 1720 0 0

1.linkedList的实现

    linkedlist的实现是基于数据结构:双向链表。模型图如

1.png


        对于linkedList没有像arrayList一样有扩容的概念。也不需要移动数据。所以对于新增和删除操作add和remove,LinkedList比较占优势。


2.双向链表的实现

参考:简单双向链表的增删改查


3.linkedList的继承关系

2.png

        从继承图中可以看出LinkList实现了List接口,实现了list接口中的所有方法,同时页实现了Queue接口,所以linkedList同时具备了对队列和栈操作的特点。


4.Linkedlist实现的方法

3(1).jpg


5.重要属性

4.png

LinkedList执行栈操作或队列操作就是对first节点和last节点的操作


6.Node节点

5.png

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");
    }
 
}


运行结果:

7.png

8.png


        遍历LinkedList时,使用removeFist()或removeLast()效率最高。但用它们遍历时,会删除原始数据;若单纯只读取,而不删除,应该使用第3种遍历方式。

        无论如何,千万不要通过随机访问去遍历LinkedList!


猜你喜欢
java基础 913 javaHashtable一、构造方法1.publicHashtable()publicHashtable(){this(11,0.75f);}无参构造,初始化一个容量为11,负载因子为
java基础 819 一、HashSet底层实现从HashSet的源码中可以发现,它的底层维护了一个HashMap,在newHashSet的时候,构造方法中其实是new了一个HashMap。privatetransientHashMapE,Objectmap;publicHashSet(){map=newHashMap();}publicHashSet(Collection?extendsEc){map=newHash
java基础 2267 ArrayList的实现是一个动态数组,从源码中也可以看出。这就决定了他的查找效率高,可以直接通过下标访问。但是对于删除和增加元素,需要大量的移动元素,所以插入和删除的效率就很低。ArrayList不是线程安全的,只能用在单线程环境下,多线程环境下可以考虑用Collections.synchronizedList(Listl)函数返回一个线程安全的ArrayList类。构造方法:ArrayList
java基础 1255 javaTreeMap实现原理TreeMap的实现其实说简单也简单说复杂也复杂,说简单是因为TreeMap底层实现完全依靠红黑树这个数据结构,相比与HashMap来说TreeMap不用考虑
java基础 715 1.HashMap的构造函数1.publicHashMap()publicHashMap(){this.loadFactor=DEFAULT_LOAD_FACTOR;//allotherfieldsdefaulted}构造一个空的HashMap,初始容量为16,负载因子为0.75,负载因子和它的作用将会在下方解释。2.publicHashMap(intinitialCapacity)publicH
java基础 1830 Java框架数据结构是以某种形式将数据组织在一起的,它不仅存储数据,还支持访问和处理数据的操作。Java提供了几个能有效地组织和操作数据的数据结构,这些数据结构通常称为Java框架。在平
算法基础 729 Java中遍历的方式以list为例,有三种遍历方式。ListStringlist=newArrayList(); list.add("2"); list.add("2"); list.add
java基础 822 java线程通讯生产者消费者模式生产者消费者模式是并发、多线程编程中经典的设计模式,生产者和消费者通过分离的执行工作解耦,简化了开发模式,生产者和消费者可以以不同的速度生产和消费数据。一个生产和消
归档
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
标签
算法基础 linux 前端 c++ 数据结构 框架 数据库 计算机基础 储备知识 java基础 ASM 其他 深入理解java虚拟机 nginx git 消息中间件 搜索 maven redis docker dubbo vue 导入导出 软件使用 idea插件 协议 无聊的知识 jenkins springboot mqtt协议 keepalived minio mysql ensp 网络基础 xxl-job rabbitmq haproxy
目录
没有一个冬天不可逾越,没有一个春天不会来临。最慢的步伐不是跬步,而是徘徊,最快的脚步不是冲刺,而是坚持。