文档章节

ArrayList和LinkedList学习

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

#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
Vector、ArrayList、LinkedList 有什么区别?

版权声明:本文供交流学习,能够帮助到你是我最大的荣幸! https://blog.csdn.net/u014231523/article/details/82086185 这个问题主要是考察集合框架的问题,主要考察三者之间的设计区别,以...

兴国First
08/26
0
0
集合(二):List接口。

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

牧羊人Berg
2016/05/25
100
0

没有更多内容

加载失败,请刷新页面

加载更多

使用rancher界面化管理docker并部署springCloud项目的其中一个服务

一、先来个简单的 1.安装docker 2.安装eureka——运行docker命令安装 3.安装eureka——运行dokcer镜像安装 (1)构建eureka的镜像,网易云的docker镜像比较全一些,也可以去https://hub.docke...

monroeCode
30分钟前
3
0
理论与实践:如何从Hadoop迁移到MaxCompute

摘要:MaxCompute大数据计算服务,能提供快速、完全托管的PB级数据仓库解决方案,能够使用户经济且高效地分析处理海量数据。而用户往往之前使用了Hadoop实现大数据计算任务,在选择了阿里云大...

阿里云云栖社区
30分钟前
2
0
mysql: utf8 && utf8mb4

https://mathiasbynens.be/notes/mysql-utf8mb4 临时收藏

阿dai
42分钟前
2
0
面试宝典系列-nginx限流

Nginx自身有的请求限制模块ngx_http_limit_req_module、流量限制模块ngx_stream_limit_conn_module基于令牌桶算法,可以方便的控制令牌速率,自定义调节限流,实现基本的限流控制。 如何Ngi...

suyain
43分钟前
3
0
下拉框选择数据过滤?

需求:下拉框数据新增一条数据,已选择的不能再重新被选择 数据:存放表格数据的数组 scoreTable 下拉框数据 catorgaryArr 定义一个已经选择了的id数组 catorgaryIds 实现: arr 使用来保存每...

西园里的猫
47分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部