List ( ArrayList & LinkedList )

*목차

배열의 단점
ArrayList
 - 장점
 - 단점
LinkedList
 - 장점
 - 단점
Doubly LinkedList
ArrayList & LinkedList 성능 비교
추가, 조회, 삭제 성능 비교

 

*배열의 단점

 

1) 배열의 크기가 고정되어 있다. 그 말은 적게 사용하든 많이 사용하든 사용량에 관계없이 고정된 메모리가 할당 된다는 것이다.

 

2) 새로운 요소를 넣는 과정이 굉장히 힘들다. 새로운 위치가 할당되어 기존 값들의 위치가 움직이고 새로운 값이 들어가야 하기 떄문이다. 제거 또한 마찬가지로 제거된 공간을 채우기 위해 많은 값들이 이동해야 하기 때문에 무겁다.

 

ArrayList

 

https://www.geeksforgeeks.org/linked-list-vs-array/

 

 

  ArrayList는 내부적으로 배열을 구현한다. 항상 초기 size를 설정해야만 하는 배열과 달리 초기의 일정한 size가 정해져있으며, size를 초과 할 경우 더 큰 size의 배열이 생성되고 기존의 값들이 복사된다. 즉, 초기 size를 정해줄 수 있지만, 굳이 정하지 않아도 자동적으로 설정된다.

 

*장점

조회 : 배열은 Index를 다루기 때문에 원하는 해당 Index의 값을 바로 반환할 수 있다.

 

*단점

추가 : 임의의 위치에 ArrayList의 요소가 추가되면 더 큰 크기의 배열이 heap 메모리에 생성되고 현재의 값을 새로운 메모리에 옮긴 다음에 새로운 요소를 추가하고 이전 메모리를 삭제한다.

 

삭제 : 임의의 위치의 ArrayList의 요소가 삭제되면 해당 공간을 채우기 위해 모든 값들이 한칸씩 앞으로 이동해야 하는 작업이 필요하다.

 

 

LinkedList

 

https://www.geeksforgeeks.org/linked-list-vs-array/

 LinkedList는 Head라는 포인터가 맨 처음 노드를 가리킨다. 값이 추가될 때마다 꼬리에 물리는 방식이 아니라 Head가 가리키는 위치로 이동한다. 즉 위의 그림은 D, C, B, A의 순서대로 요소가 추가된 것이다.

 

 

*장점

추가 : 임의의 위치에 LinkedList의 요소가 추가되면 단지 heap 메모리에 공간을 만들고 연결관계만 수정하면 된다. 

삭제 : 임의의 위치의 LinkedList의 요소가 제거되면 해당 위치의 이전 노드를 다음 노드에 연결하면 된다. (해당 위치를 알기 위해 Head 위치부터 검색해야 하는 비용이 있지만 삭제 자체는 굉장히 빠르다.)

*단점

조회 : 항상 Head 위치부터 끝까지 하나씩 확인하면서 가기 때문에 오랜 시간이 걸린다.

 

1. 랜덤 접근이 허용되지 않는다. 첫번째 노드(head)로부터 순서대로 요소에 접근하기 때문이다. 그래서 linked list로는 이진탐색(binary search)을 효과적으로 할 수 없다. 왜냐하면 일반 배열에서는 이진탐색에서 중간값을 찾는 시간이 O(1)이지만 linked list의 경우 처음부터 찾아야 하기 때문에 O(n)의 시간이 걸린다.

2. 리스트의 각각의 요소마다 추가적인 메모리 공간이 필요하다.

3. 일반 배열은 연속적인 위치에 있으나 linked list의 경우에는 그렇지 않아 cache 적용이 어렵다.

 

Doubly-linked list

https://www.geeksforgeeks.org/doubly-linked-list

  기존의 LinkedList에서 발전된 형태로 Node는 next만 가지는 것이 아니라 이전 노드를 참조할 수 있는 previous도 가진다. 따라서 LinkedList와 달리 맨 앞의 Head에서 조회를 시작하지 않고 유동적으로 뒤에서부터 앞으로 조회가 가능하다. 하지만 pointer를 2개 써야하고 그에 따른 메모리 할당이 늘어나는 것은 단점이다.

 

 

https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html

Java Collections에서는 LinkedList()가 단일로 구현되지 않고 Doubly-linked list로 구현된다. List와 Deque를 상속해서 구현하므로 addFirst(),  addLast(), getFirst(), getLast() 등 맨 앞의 요소와 맨 뒤의 요소를 조작하는 기능을 가지고 있다.

 

ArrayList & LinkedList 성능 비교

	ArrayList	LinkedList
추가(임의의 위치)	느리다 O(n)	빠르다 O(1)
제거(임의의 위치)	느리다 O(n)	빠르다 O(1)
조회(임의의 위치)	빠르다 O(1)	느리다 O(n)

*추가, 제거는 임의의 위치를 찾는 시간은 고려하지 않고 그 이후부터만 시간을 계산한다.

 

 

추가, 조회, 삭제 성능 비교

import java.util.*;

public class Main {
	public static void main(String[] args) {
		ArrayList<Integer> arrayList = new ArrayList<Integer>();
		LinkedList<Integer> linkedList = new LinkedList<Integer>();
		 
		// ArrayList add
		long startTime = System.nanoTime();
		 
		for (int i = 0; i < 100000; i++) {
			arrayList.add(i);
		}
		long endTime = System.nanoTime();
		long duration = endTime - startTime;
		System.out.println("ArrayList add:  " + duration);
		 
		// LinkedList add
		startTime = System.nanoTime();
		 
		for (int i = 0; i < 100000; i++) {
			linkedList.add(i);
		}
		endTime = System.nanoTime();
		duration = endTime - startTime;
		System.out.println("LinkedList add: " + duration);
		 
		// ArrayList get
		startTime = System.nanoTime();
		 
		for (int i = 0; i < 10000; i++) {
			arrayList.get(i);
		}
		endTime = System.nanoTime();
		duration = endTime - startTime;
		System.out.println("ArrayList get:  " + duration);
		 
		// LinkedList get
		startTime = System.nanoTime();
		 
		for (int i = 0; i < 10000; i++) {
			linkedList.get(i);
		}
		endTime = System.nanoTime();
		duration = endTime - startTime;
		System.out.println("LinkedList get: " + duration);
		 
		 
		 
		// ArrayList remove
		startTime = System.nanoTime();
		 
		for (int i = 9999; i >=0; i--) {
			arrayList.remove(i);
		}
		endTime = System.nanoTime();
		duration = endTime - startTime;
		System.out.println("ArrayList remove:  " + duration);
		 
		 
		 
		// LinkedList remove
		startTime = System.nanoTime();
		 
		for (int i = 9999; i >=0; i--) {
			linkedList.remove(i);
		}
		endTime = System.nanoTime();
		duration = endTime - startTime;
		System.out.println("LinkedList remove: " + duration);
	}

}

 

 

 

https://medium.com/@govinda_raj/arraylist-vs-linkedlist-f8c5099153b5

 

출처 : https://www.geeksforgeeks.org/linked-list-vs-array/