文档章节

Queue.LinkedList

脑丨残
 脑丨残
发布于 2017/05/22 21:06
字数 242
阅读 3
收藏 0
点赞 0
评论 0

LinkedList

  • 链表结构,线程不安全,无限容量
    //持有头尾节点
    transient Node<E> first;
    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;
private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
  • add 加入链表末端
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++;
    }
  • removegetset,都会定位链表元素,会完全遍历链表,这里证明了,链表数组查询效率较移动效率
Node<E> node(int index) {
        // assert isElementIndex(index);
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }
//断开节点
E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }
        x.item = null;
        size--;
        modCount++;
        return element;
    }

© 著作权归作者所有

共有 人打赏支持
脑丨残
粉丝 8
博文 60
码字总数 23267
作品 0
西安

暂无文章

pbgo: 基于Protobuf的迷你RPC/REST框架

https://www.oschina.net/p/pbgo

chai2010
30分钟前
0
0
rsync工具介绍、常用选项以及通过ssh同步

linux下的文件同步工具 rsync rsync是非常实用的一个同步工具,可以从a机器到b机器传输一个文件,也可以备份数据,系统默认没有这个工具,要使用命令 yum install -y rsync 安装。 rsync的命...

黄昏残影
46分钟前
0
0
OSChina 周四乱弹 —— 表妹要嫁人 舅妈叮嘱……

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @哈哈哈哈哈嗝:一定要听——The Pancakes的单曲《咁咁咁》 《咁咁咁》- The Pancakes 手机党少年们想听歌,请使劲儿戳(这里) @clouddyy :...

小小编辑
今天
194
4
流利阅读笔记30-20180719待学习

重磅:让人类得老年痴呆的竟是它? Lala 2018-07-19 1.今日导读 去年奥斯卡最佳动画长片《寻梦环游记》里有一句经典台词:“比死亡更可怕的,是遗忘”。在电影中,年迈的曾祖母会重复说一样的...

aibinxiao
今天
3
0
1.16 Linux机器相互登录

Linux机器之间以密码方式互相登录 运行命令#ssh [ip address],标准命令:#ssh [username]@ip, 如果没有写用户名,则默认为系统当前登录的用户 命令#w查看系统负载,可查看到连接到该主机的...

小丑鱼00
今天
0
0
about git flow

  昨天元芳做了git分支管理规范的分享,为了拓展大家关于git分支的认知,这里我特意再分享这两个关于git flow的链接,大家可以看一下。 Git 工作流程 Git分支管理策略   git flow本质上是...

qwfys
今天
2
0
Linux系统日志文件

/var/log/messages linux系统总日志 /etc/logrotate.conf 日志切割配置文件 参考https://my.oschina.net/u/2000675/blog/908189 dmesg命令 dmesg’命令显示linux内核的环形缓冲区信息,我们可...

chencheng-linux
今天
1
0
MacOS下给树莓派安装Raspbian系统

下载镜像 前往 树莓派官网 下载镜像。 点击 最新版Raspbian 下载最新版镜像。 下载后请,通过 访达 双击解压,或通过 unzip 命令解压。 检查下载的文件 ls -lh -rw-r--r-- 1 dingdayu s...

dingdayu
今天
1
0
spring boot使用通用mapper(tk.mapper) ,id自增和回显等问题

最近项目使用到tk.mapper设置id自增,数据库是mysql。在使用通用mapper主键生成过程中有一些问题,在总结一下。 1、UUID生成方式-字符串主键 在主键上增加注解 @Id @GeneratedValue...

北岩
今天
2
0
告警系统邮件引擎、运行告警系统

告警系统邮件引擎 cd mail vim mail.py #!/usr/bin/env python#-*- coding: UTF-8 -*-import os,sysreload(sys)sys.setdefaultencoding('utf8')import getoptimport smtplibfr......

Zhouliang6
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部