Java-链表LinkedList源码原理分析,并且通过LinkedList构建队列

高洛峰
发布: 2016-10-11 16:27:26
原创
2345人浏览过

在这里我们介绍一下最简单的链表linkedlist;

看一下add()方法:

public boolean add(E e) {
        linkLast(e);        return true;
    }
登录后复制
void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }
登录后复制

add原理就是:

1.首先获取链表最后一个节点。

2.把新节点插入到最后一个节点之后。

立即学习Java免费学习笔记(深入)”;

3.linkedList的last属性重新指向最后一个节点。

4.如果这个节点是第一个节点,之前没有节点,那么将linkedList的first的属性指向新节点;如果不是,则将上一个节点的next属性指向该节点。

 

使用LinkedList构建先进先出队列:

offer()方法入队:使用add()方法插入节点在最后。

酷表ChatExcel
酷表ChatExcel

北大团队开发的通过聊天来操作Excel表格的AI工具

酷表ChatExcel 48
查看详情 酷表ChatExcel
public boolean offer(E e) {
        return add(e);
    }
登录后复制

poll()方法出队:从链表表头开始移出队列

public E poll() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }
登录后复制

使用LinkedList构建后进先出队列:

push()方法入队:插入节点在first

public void addFirst(E e) {
        linkFirst(e);
    }

private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }
登录后复制

pop()方法出队:从链表表头开始移出队列

public E pop() {
        return removeFirst();
    }

public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }

private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        final E element = f.item;
        final Node<E> next = f.next;
        f.item = null;
        f.next = null; // help GC
        first = next;
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }
登录后复制

最后需要注意的是:LinkedList是线程不安全的,如果需要线程安全那么请使用synchronized加锁,或者使用vector,或者使用java.util.concurrent包。

如果需要线程遍历List的时候,避免出现ConcurrentModificationException异常,那么有3种解决方式。

1.遍历List的使用synchronized加锁;

2.使用java.util.concurrent包下面的CopyOnWriteArrayList,每次使用List时实际上都是使用的List副本。

3.使用Jdk8中foreach方法,不过该方法只接受lambda表达式

list.forEach(item -> {
                    System.out.println("遍历元素:" + item);
                    try {
                        Thread.sleep(1000);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                });
登录后复制
java速学教程(入门到精通)
java速学教程(入门到精通)

java怎么学习?java怎么入门?java在哪学?java怎么学才快?不用担心,这里为大家提供了java速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载
来源:php中文网
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
最新问题
开源免费商场系统广告
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责申明 意见反馈 讲师合作 广告合作 最新更新 English
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送
PHP中文网APP
随时随地碎片化学习

Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号