发布于2021-06-12 14:52 阅读(982) 评论(0) 点赞(8) 收藏(3)
目录
在Java中应该都知道ArrayList和LinkedList,
一直以来的概念呢是
ArrayList在get(index)这个应该比LinkedList快;
LinkedList比ArrayList在add(index,element)快;
两者共同遍历呢,应该是一样快的,毕竟都要循环遍历一遍。
直到我写了一个测试类
- package com.lw;
-
- import java.util.ArrayList;
- import java.util.LinkedList;
- import java.util.List;
-
- import org.junit.Test;
-
- public class TestJDKList {
-
- List<Integer> linkedList = new LinkedList<>();
- List<Integer> arrayList = new ArrayList<>();
-
- int length = 1000000;
-
-
-
- @Test
- public void testLinkedInsert(){
-
- for (int i = 0; i < length; i++) {
- linkedList.add(i);
- }
-
- long currentMi2 = System.currentTimeMillis();
- linkedList.add(length/2,3);
- long endTime2 = System.currentTimeMillis();
- System.out.println("testLinkedInsert:" + (endTime2 - currentMi2)); // 9
- }
-
- @Test
- public void testArrayInsert(){
-
- for (int i = 0; i < length; i++) {
- arrayList.add(i);
- }
-
- long currentMi2 = System.currentTimeMillis();
- arrayList.add(length/2,3);
- long endTime2 = System.currentTimeMillis();
- System.out.println("testArrayInsert:" + (endTime2 - currentMi2)); // 1
- }
-
- @Test
- public void testLinkedGet(){
-
- for (int i = 0; i < length; i++) {
- linkedList.add(i);
- }
-
- long currentMi2 = System.currentTimeMillis();
- linkedList.get(length/2);
- long endTime2 = System.currentTimeMillis();
- System.out.println("testLinkedGet:" + (endTime2 - currentMi2)); // 5
- }
-
- @Test
- public void testArrayGet(){
-
- for (int i = 0; i < length; i++) {
- arrayList.add(i);
- }
-
- long currentMi2 = System.currentTimeMillis();
- arrayList.get(length/2);
- long endTime2 = System.currentTimeMillis();
- System.out.println("testArrayGet:" + (endTime2 - currentMi2)); // 0
- }
-
-
-
- @Test
- public void testLinkedIter(){
-
- for (int i = 0; i < length; i++) {
- linkedList.add(i);
- }
-
- long currentMi2 = System.currentTimeMillis();
- for (Integer i : linkedList) {
-
- };
- long endTime2 = System.currentTimeMillis();
- System.out.println("testLinkedIter:" + (endTime2 - currentMi2)); // 26
- }
-
- @Test
- public void testArrayIter(){
-
- for (int i = 0; i < length; i++) {
- arrayList.add(i);
- }
-
- long currentMi2 = System.currentTimeMillis();
- for (Integer i : arrayList) {
-
- };
- long endTime2 = System.currentTimeMillis();
- System.out.println("testArrayIter:" + (endTime2 - currentMi2)); // 11
- }
-
- @Test
- public void testLinkedAdd() {
-
-
- long currentMi2 = System.currentTimeMillis();
- for (int i = 0; i < length; i++) {
- linkedList.add(i);
- }
- long endTime2 = System.currentTimeMillis();
- System.out.println("testLinkedAdd:" + (endTime2 - currentMi2)); // 53
- }
-
- @Test
- public void testArrayAdd(){
- long currentMi1 = System.currentTimeMillis();
- for (int i = 0; i < length; i++) {
- arrayList.add(i);
- }
- long endTime1 = System.currentTimeMillis();
- System.out.println("testArrayAdd:" + (endTime1 - currentMi1)); // 35
-
- }
- }
运行了两遍结果如下:
testLinkedInsert:7
testArrayInsert:0
testLinkedAdd:218
testArrayAdd:23
testLinkedGet:4
testArrayGet:0
testLinkedIter:14
testArrayIter:11
----------------第二遍分割线---------------------------------
testLinkedInsert:12
testArrayInsert:0
testLinkedIter:13
testArrayIter:12
testLinkedGet:3
testArrayGet:0
testLinkedAdd:119
testArrayAdd:23
颠覆三观,ArrayList竟然无论怎样都比LinkedList快??
ArrayList的add源码,它是把数据放在一个数组中
transient Object[] elementData;
- public boolean add(E e) {
- ensureCapacityInternal(size + 1); // Increments modCount!!
- elementData[size++] = e;
- return true;
- }
而LinkedList源码,是把数据放在Node对象中,有个前后指针。
- 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++;
- }
- 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;
- }
- }
难道是前后指针这里花时间了么?
再看get方法,
ArrayList的get,因为是连续的内存,所以取数据很快。
- public E get(int index) {
- rangeCheck(index);
-
- return elementData(index);
- }
-
-
- E elementData(int index) {
- return (E) elementData[index];
- }
再看LinkedList的get,是通过指针遍历的,直到是这个index为止。
这里还有判断size,如果是size的前一半,则通过first节点往后去找,如果在后一半则通过last节点往前找,这样会更快,所以LinkedList的查找其实也不慢。
- public E get(int index) {
- checkElementIndex(index);
- return node(index).item;
- }
-
-
- 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;
- }
- }
ArrayList的add(index,element)
这里是可以扩容的,将index后半段拷贝到index+1,然后在index插入一个新的,但没想到这么快。
其实也能想到System.arraycopy是native,所以快也能理解
- public void add(int index, E element) {
- rangeCheckForAdd(index);
-
- ensureCapacityInternal(size + 1); // Increments modCount!!
- System.arraycopy(elementData, index, elementData, index + 1,
- size - index);
- elementData[index] = element;
- size++;
- }
然后是LinkedList的add(index,element)
无非是指针的指向变化而已,但没想到比上面的System.arraycopy还要慢,果然不愧为native方法。
- public void add(int index, E element) {
- checkPositionIndex(index);
-
- if (index == size)
- linkLast(element);
- else
- linkBefore(element, node(index));
- }
-
- void linkBefore(E e, Node<E> succ) {
- // assert succ != null;
- final Node<E> pred = succ.prev;
- final Node<E> newNode = new Node<>(pred, e, succ);
- succ.prev = newNode;
- if (pred == null)
- first = newNode;
- else
- pred.next = newNode;
- size++;
- modCount++;
- }
-
-
- 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++;
- }
所以项目中大部分用ArrayList也就是可以理解。
不过ArrayList是连续的内存空间,在内存空间很紧张情况下,LinkedList内存利用率更高。
原文链接:https://blog.csdn.net/lw18751836671/article/details/117710230
作者:我很伤感
链接:http://www.javaheidong.com/blog/article/222407/27763fefbc19261e2698/
来源:java黑洞网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
昵称:
评论内容:(最多支持255个字符)
---无人问津也好,技不如人也罢,你都要试着安静下来,去做自己该做的事,而不是让内心的烦躁、焦虑,坏掉你本来就不多的热情和定力
Copyright © 2018-2021 java黑洞网 All Rights Reserved 版权所有,并保留所有权利。京ICP备18063182号-2
投诉与举报,广告合作请联系vgs_info@163.com或QQ3083709327
免责声明:网站文章均由用户上传,仅供读者学习交流使用,禁止用做商业用途。若文章涉及色情,反动,侵权等违法信息,请向我们举报,一经核实我们会立即删除!