文档章节

ArrayList和LinkedList学习

战地春梦
 战地春梦
发布于 2016/07/15 11:12
字数 691
阅读 13
收藏 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则需要进行数组的拷贝。

© 著作权归作者所有

共有 人打赏支持
上一篇: Java 注解
下一篇: Java 动态代理
战地春梦
粉丝 5
博文 33
码字总数 24598
作品 0
南充
私信 提问
LinkedList工作原理

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

kukudeku
2016/09/03
107
0
Java集合类之List源码学习笔记

Java集合类主要分为List,Set,Map三大类。ArrayList和LinkedList是则List接口的俩个实现。他们都可以作为顺序存放元素的容器,并且元素可以重复,可以为null值。当有元素重复时,如果按元素而...

单线程程序员
2018/12/06
0
0
Vector、ArrayList、LinkedList 有什么区别?

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

兴国First
2018/08/26
0
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

没有更多内容

加载失败,请刷新页面

加载更多

c++ 定义新的异常

#include <iostream> #include <exception> using namespace std; struct MyException : public exception { const char * what () const throw () { return "C++ Exception"; } }; int main......

天王盖地虎626
今天
3
0
PDMan-2.1.1 发布:用心开源,免费的国产数据库建模工具(春节前最后一个版本)

一、软件介绍 PDMan 是一款开源免费的数据库模型建模工具,是PowerDesigner之外另一种更好的选择。支持Windows,Mac,Linux等操作系统,具有上手容易,使用简单的特点。 2018年获得码云GVP (Gi...

O龙猫O
今天
15
0
OSChina 周二乱弹 —— 以后我偷小鱼干养你

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @庞巴哥 :只有这节奏瞬间变得轻松。。。。。。。。。分享Talking Eyes的单曲《In the sun (Extended Version)》: 《In the sun (Extended Ve...

小小编辑
今天
313
7
多表查询

第1章 多表关系实战 1.1 实战1:省和市  方案1:多张表,一对多  方案2:一张表,自关联一对多 1.2 实战2:用户和角色 (比如演员和扮演人物)  多对多关系 1.3 实战3:角色和权限 (比如...

stars永恒
今天
9
0
求推广,德邦快递坑人!!!!

完全没想好怎么来吐槽自己这次苦逼的德邦物流过程了,只好来记一个流水账。 从寄快递开始: 2019年1月15日从 德邦物流 微信小app上下单,截图如下: 可笑的是什么,我预约的是17号上门收件,...

o0无忧亦无怖
昨天
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部