文档章节

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 动态代理
战地春梦
粉丝 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
Vector、ArrayList、LinkedList 有什么区别?

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

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

没有更多内容

加载失败,请刷新页面

加载更多

Accept和Content-type的意思

Accept意思是我希望接收到的数据类型 Content-type意思是我发出去的数据类型

大灰狼wow
29分钟前
1
0
Java每天10道面试题,跟我走,offer有!(五)

41.Iterator、ListIterator 和 Enumeration的区别?   迭代器是一种设计模式, 它是一个对象, 它可以遍历并选择序列中的对象, 而开发人员不需要了解 该序列的底层结构。 迭代器通常被称为...

Java干货分享
29分钟前
2
0
meta 解决页面浏览器兼容性

使用最高级的ie内核,如果支持谷歌内核,使用谷歌内核 <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1" /> 这 样写可以达到的效果是如果安装了GCF,则使用GCF来渲染页面,如...

之渊
31分钟前
2
0
极验验证demo(django+vue)

在使用之前,曾经试过用阿里云的人机验证,不过在签名部分比较复杂,下载sdk后需要自己写很多,折腾了一下,还是放弃。而腾讯云的人机验证python版本有demo,直接填写keyhe1secret就可以使用...

xiaoge2016
32分钟前
1
0
浅谈js回调

js回调极为简洁,无需声明,直接通过参数传入方法实体,调用方法实体的时候,可以直接调用方法名或者方法名加参数即可,以下看例子 socket.initWebSocket(this, userName, userId, (isSucce...

Carbenson
37分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部