[JAVA] LinkedList에 대하여 (ArrayList와의 차이)

 

 

LinkedList에 대해 알아보기 전에, 왜 LinkedList가 생기게 되었는지에 대해 알아보자.

 

 

 

 

 

 

배열의 단점

자바의 배열은 다음과 같은 단점을 가지고 있다.

 

 

크기를 변경할 수 없다.

크기를 변경할 수 없으므로 크기를 확장해야 할 경우 새로운 배열을 생성하여 복사해야한다.

실행속도를 향상시키기 위해서 배열의 크기를 크게 생성할 경우 메모리가 낭비된다.

 

 

 

 

비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다.

차례대로 데이터를 추가하고 마지막의 데이터를 삭제하는 경우에는 굉장히 빠르나, 배열의 중간에서 값을 제거하고 추가할 때는 굉장히 시간이 오래 걸린다.

 

배열을 이러한 단점을 가지고 있고, 배열을 통해 List를 구현한 ArrayList도 위와같은 문제점들을 가지고 있다.

 

이러한 문제점을 보안하기 위해서 고안된 자료구조 바로 LinkedList이다.

배열은 모든 데이터가 연속적으로 존재한다. 그러나 LinkedList는 불연속적으로 존재하는 데이터를 서로 연결한 형태로 구성되었다.

 

 

 

 

 

 

 

 

 

LinkedList

LinkedList는 위에서 언급했다시피, ArrayList의 단점인 배열의 중간에 존재하는 원소의 삽입과 삭제에 대한 빠른 연산을 위해 태어났다.

그렇기에 장점으로는 당연히 원소의 삽입과 삭제가 빠르다는 것이다.

 

 

 

 

ArrayList VS LinkedList

배열의 경우, n번째 인덱스의 값을 조회하기 위해서는 다음의 간단한 수식 하나를 통해 해결할 수 있다.

인덱스가 n인 데이터의 주소 = 배열의 주소 + n * 데이터 타입의 크기

배열은 각 요소들이 연속적으로 메모리상에 존재하기 때문에 배열의 주소와, 데이터 크기의 타입만 알고 있다면, n번째 위치의 값을 가져오는 것은 굉장히 Easy하다.

 

그러나 LinkedList의 경우에는 그 원소들이 불연속적으로 존재하기 때문에 처음부터 n번째 데이터까지 차례대로 따라가야 원하는 값을 얻을 수 있다.

LinkedList는 데이터를 조회할 때 그 속도가 굉장히 느리다!

 

 

 

 

 

 

 

 

 

정리

컬렉션	읽기(접근시간)	추가 / 삭제	비고
ArrayList	빠르다	느리다 (단 데이터를 순차적으로 추가하고, 삭제하는 경우에는 빠르다.)	비효율적인 메모리사용
LinkedList	느리다	빠르다	데이터가 많을수록 접근성이 떨어짐

 

 

 

 

 

 

 

 

📔 Reference

[JAVA의 정석 기초편 - 남궁성]