Array List 와 LinkedList 가 누가 더 빠 른 지 에 대해 서 말씀 드 리 겠 습 니 다.

1.Array List 와 LinkedList 는 누가 빠 릅 니까?
자바 에 서 는 Array List 와 LinkedList 를 모두 알 고 있 을 것 이다.
지금까지 의 콘 셉 트 는 요.
Array List 는 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
삼 관 을 뒤 집 으 면 Array List 가 어떻게 든 LinkedList 보다 빠르다??
3.순환 추가
Array List 의 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;
        }
    }

혹시 앞 뒤 지침 인 데 여기 시간 이 걸 렸 나 요?
4.지 정 된 위치 Get
get 방법 을 보면,
Array List 의 get 은 연속 메모리 이기 때문에 데 이 터 를 빨리 가 져 옵 니 다.

public E get(int index) {
        rangeCheck(index);
 
        return elementData(index);
    }
 
 
E elementData(int index) {
        return (E) elementData[index];
    }

링크 드 리스트 의 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;
        }
    }

5.지 정 된 위치 추가
ArrayList 의 add(index,element)
여 기 는 확장 할 수 있 습 니 다.index 후반 부 를 index+1 로 복사 한 다음 index 에 새 것 을 삽입 할 수 있 습 니 다.그런데 이렇게 빠 를 줄 은 몰 랐 습 니 다.
사실 System.array copy 가 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++;
    }

그리고 링크 드 리스트 의 add(index,element)
지침 의 지향 변화 일 뿐 이지 만 위의 System.array copy 보다 더 느 릴 줄 은 몰 랐 습 니 다.역시 네 이 티 브 방법 답 습 니 다.

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++;
    }

그래서 프로젝트 의 대부분 은 Array List 로 이해 할 수 있 습 니 다.
그러나 Array List 는 연속 적 인 메모리 공간 으로 메모리 공간 이 긴 장 된 상황 에서 LinkedList 메모리 이 용 률 이 높다.
Array List 와 LinkedList 가 누가 더 빠 른 지 에 대한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 Array List 와 LinkedList 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 도 많은 응원 부탁드립니다!