文档章节

ArrayList和LinkedList学习

战地春梦
 战地春梦
发布于 2016/07/15 11:12
字数 691
阅读 12
收藏 4
点赞 0
评论 0

#ArrayList和LinkedList学习 ##1.ArrayList

###1.1源码分析 //默认数组容量即长度为10 private static final int DEFAULT_CAPACITY = 10;

	//存储对象数组
	transient Object[] elementData; 
	
	//数组长度
	private int size;

	//最大数组长度
	private static final int MAX_ARRAY_SIZE = 	Integer.MAX_VALUE - 8;

	//为空的对象数组
	private static final Object[] 	DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

	//添加数据
	public boolean add(E e) {
	 	//检验数组长度
    	ensureCapacityInternal(size + 1);         			elementData[size++] = e;
    	return true;
	}
	
	private void ensureCapacityInternal(int minCapacity) 
	{
	//如果对象数组为空
    if (elementData == 	DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    //容量为默认容量和当前数组容量的最大值
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    //确保当前容量是否需要扩容
    ensureExplicitCapacity(minCapacity);
    
    }
    
    
     private void ensureExplicitCapacity(int minCapacity) {
    //操作数加一
    modCount++;
   //如果当前数组容量大于存储对象数组大小
    if (minCapacity - elementData.length > 0)
    	//扩展容量
        grow(minCapacity);
}
 

//扩容 
private void grow(int minCapacity) {
    
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
    	//确认新的数组长度
        newCapacity = hugeCapacity(minCapacity);
    //进行拷贝操作
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) 
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

// 根据下标获取
public E get(int index) {
	//检验下标是否超过数组长度
    rangeCheck(index);
    return elementData(index);
}

public E remove(int index) {
//检验下标是否超过数组长度
    rangeCheck(index);
//操作数加一
    modCount++;
    E oldValue = elementData(index);
    int numMoved = size - index - 1;
    if (numMoved > 0)
    	//数组拷贝
        System.arraycopy(elementData, index+1, elementData, index,numMoved);
    elementData[--size] = null; 
    return oldValue;
}

##2.LinkedList

###2.1源码分析

	//链表长度
	transient int size = 0;
	
	//添加数据
	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++;
    }
    
    //删除数据
    public E remove(int index) {
    //检验下标
    checkElementIndex(index);
    return unlink(node(index));
	}
    
    //根据下标获得节点
    Node<E> node(int index) {
	
	// >>:右移运算符,size >> 1,相当于size除以2的1次方
    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;
	}

##3.比较

当读取数据时,采用ArrayList更快,因为是根据下标访问,时间为O(1),而

LinkedList会先遍历链表,才能找到下标代表的节点,时间为O(m)。

当写入,删除数据时,采用LinkedList更快,因为他通过修改头尾指针指向的对象,即可

完成添加,或者删除。而ArrayList则需要进行数组的拷贝。

© 著作权归作者所有

共有 人打赏支持
战地春梦
粉丝 4
博文 33
码字总数 24598
作品 0
南充
LinkedList工作原理

1.学习LinkedList的必要性 在ArrayList工作原理中,我们了解到ArrayList和LinkedList是List接口的两个重要实现。并且ArrayList是一个动态数组的实现。因此ArrayList在队列中插入和删除元素方...

kukudeku
2016/09/03
107
0
java学习笔记--类ArrayList和LinkedList的实现

在集合Collection下的List中有两个实现使用的很频繁,一个是ArrayList,另一个是LinkedList,在学习中肯定都会有这样的疑问:什么时候适合使用ArrayList,什么时候用LinkedList?这时,我们就需...

UseBing
2017/08/09
0
0
day17 java 语言中的---list集合

day17 java 语言中的---List集合 一: list集合概述: 在day16中已经讲了一下具体的set集合,今天在这个基础上在说一点list集合。主要包含有“ArrayList集合”和“linkedlist集合”以及“vec...

孤独一夜
2017/10/22
0
0
集合(二):List接口。

一:List接口: 继承自Collection,如下: 1.ArrayList( 实现类): ArrayList 是一个数组队列,相当于 动态数组。与Java中的数组相比,它的容量能动态增长。它继承于AbstractList,实现了L...

牧羊人Berg
2016/05/25
100
0
JAVA容器-自问自答学LinkedList

前言 在前一篇文章我以面试问答的形式与大家一同学习了ArrayList,有兴趣但是没阅读过的同学可以翻看我的文章记录,有了ArrayList,自然少不了LinkedList了。 PS:由于我的居住地珠海前两天遭...

liangzzz
2017/08/28
0
0
JAVA容器-自问自答学LinkedList

前言 在前一篇文章我以面试问答的形式与大家一同学习了ArrayList,有兴趣但是没阅读过的同学可以翻看我的文章记录,有了ArrayList,自然少不了LinkedList了。 PS:由于我的居住地珠海前两天遭...

liangzzz
2017/08/28
0
0
java容器学习

java容器: 容器,顾名思义,就是用来存放东西的道具,但是在我们程序开发中容器的概念就是用来存在我们数据对象的引用。 往常的数组存储,由于数组开始的长度已经指定,开发过程中不能随意修...

四月李
2015/12/17
127
0
JDK容器学习之List: CopyOnWriteArrayList,ArrayList,LinkedList对比

列表 List, ArrayList, LinkedList, CopyOnWriteArrayList, Vector 简述 1. 列表划分为线程安全和线程非安全两类 线程安全: , , 线程非安全:, 2. 底层存储 数组: 双向链表: 通过三个添加...

小灰灰Blog
2017/10/21
0
0
Java 基础(四)集合源码解析 List

List 接口 前面我们学习了Iterator、Collection,为集合的学习打下了基础,现在我们来学习集合的第一大体系 List。 List 是一个接口,定义了一组元素是有序的、可重复的集合。 List 继承自 ...

diamond_lin
2017/09/26
0
0
Java学习之Iterator(迭代器)的一般用法

问题: 看老大的代码需要取list里面每个元素的时候,都是 Iterator it = list.iterator(); while (it.hasNext()) { personnelID= (String) it.next(); } 这样比我直接写for(int i=0;i<list.......

chuiyuan
2014/04/28
0
1

没有更多内容

加载失败,请刷新页面

加载更多

下一页

流利阅读笔记29-20180718待学习

高等教育未来成谜,前景到底在哪里? Ray 2018-07-18 1.今日导读 在这个信息爆炸的年代,获取知识是一件越来越容易的事情。人们曾经认为,如此的时代进步会给高等教育带来众多便利。但事实的...

aibinxiao
10分钟前
6
0
第15章FTP服务搭建与配置

15.1FTP介绍 FTP多用于Windows传文件到linux rz sz在文件超过4G,就无法使用了——>安装包yum install -y install lrzsz rz把 window 上的文件传输到 linux 上 sz 把 linux 上的文件传输到 ...

Linux学习笔记
17分钟前
0
0
OSChina 周三乱弹 —— 你被我从 osc 老婆们名单中踢出了

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @小鱼丁:分享五月天的单曲《后来的我们 (电影《后来的我们》片名曲)》: 《后来的我们 (电影《后来的我们》片名曲)》- 五月天 手机党少年们想...

小小编辑
22分钟前
6
1
Spring Boot Admin 2.0开箱体验

概述 在我之前的 《Spring Boot应用监控实战》 一文中,讲述了如何利用 Spring Boot Admin 1.5.X 版本来可视化地监控 Spring Boot 应用。说时迟,那时快,现在 Spring Boot Admin 都更新到 ...

CodeSheep
41分钟前
0
0
Python + Selenium + Chrome 使用代理 auth 的用户名密码授权

米扑代理,全球领导的代理品牌,专注代理行业近十年,提供开放、私密、独享代理,并可免费试用 米扑代理官网:https://proxy.mimvp.com 本文示例,是结合米扑代理的私密、独享、开放代理,专...

sunboy2050
今天
0
0
实现异步有哪些方法

有哪些方法可以实现异步呢? 方式一:java 线程池 示例: @Test public final void test_ThreadPool() throws InterruptedException { ScheduledThreadPoolExecutor scheduledThre......

黄威
今天
1
0
linux服务器修改mtu值优化cpu

一、jumbo frames 相关 1、什么是jumbo frames Jumbo frames 是指比标准Ethernet Frames长的frame,即比1518/1522 bit大的frames,Jumbo frame的大小是每个设备厂商规定的,不属于IEEE标准;...

六库科技
今天
0
0
牛客网刷题

1. 二维数组中的查找(难度:易) 题目描述 在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入...

大不了敲一辈子代码
今天
0
0
linux系统的任务计划、服务管理

linux任务计划cron 在linux下,有时候要在我们不在的时候执行一项命令,或启动一个脚本,可以使用任务计划cron功能。 任务计划要用crontab命令完成 选项: -u 指定某个用户,不加-u表示当前用...

黄昏残影
昨天
0
0
设计模式:单例模式

单例模式的定义是确保某个类在任何情况下都只有一个实例,并且需要提供一个全局的访问点供调用者访问该实例的一种模式。 实现以上模式基于以下必须遵守的两点: 1.构造方法私有化 2.提供一个...

人觉非常君
昨天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部