[자료구조] ArrayList와 LinkedList

리스트(List)

리스트는 배열이 가지고 있는 인덱스 없이 순차적으로 저장하여 빈틈없는 데이터의 적재 라는 장점을 취한 자료구조로 중간에 빈 공간을 허용하지 않으며 저장공간의 크기가 가변적 이라는 특징을 가지고 있습니다. 리스트의 핵심은 원소들간 순서가 있는 데이터의 모임으로 배열과 달리 순서대로 접근해야 합니다. 

이 글에서는 가장 많이 쓰이는 ArrayList와 LinkedList에 대해 다루겠습니다.

 

ArrayList

ArrayList는 내부적으로 배열(Array)을 이용하는 리스트로 배열의 한계점인 정적인 크기를 극복하기 위해 만들어졌습니다. 따라서 선언시 별도의 크기를 지정해 줄 필요가 없습니다. 하지만 배열을 사용할 때 사용자가 격어야 할 복잡한 과정을 숨겨놓은 것일 뿐, 삽입/삭제시 배열의 요소들을 복사하여 새로운 배열로 옮기기에 시간소요가 발생합니다. ArrayList를 사용하는 사용자 입장에서만 크기가 가변적이게 느끼는 것입니다.

 

장점

• 크기가 동적으로 정해져 있지 않고 빈 공간을 허용하지 않기 때문에 메모리의 낭비가 없다.
• 인덱스를 사용하는 get 메서드가 지원되어 특정 위치에 있는 원소에 접근하는 시간복잡도는 O(1) 이다.
• 인덱스를 사용하는 set 메서드가 지원되어 특정 위치에 있는 원소를 수정하는 시간복잡도는 O(1) 이다.

 

단점

• 중간에 원소를 삽입/ 삭제하는 시간복잡도는 O(n) 이다.
• 저장공간을 확장/복사 하는 시간복잡도는 O(n) 이다. (add/remove 메서드가 수행될 때마다 저장공간 재 할당)

 

LinkedList

LinkedList는 ArrayList 의 한계점인 원소 삽입/삭제 할때의 시간복잡도 O(n)을 극복하기 위해 만들어졌습니다. LinkedList는 물리 공간과 논리 공간이 일치하지 않으며 메모리 공간이 연속적으로 구성되어있지 않습니다. 따라서 인덱스로의 접근이 불가능 하며 원소에 접근하기위해서는 앞에서부터 순차적으로 접근해야합니다.

 

장점

• 크기가 동적으로 정해져 있지 않고 빈 공간을 허용하지 않기 때문에 메모리의 낭비가 없다.
• 포인터를 통하여 다음 데이터의 위치를 가르켜고 있어 중간 삽입/삭제의 용이.(O(n) 보다는 적게 걸림)
• 새로운 원소가 삽입/삭제 될 때 저장공간을 재 할당 할 필요가 없다.

 

단점

• 인덱스를 사용하지 못하여 순서대로 접근해야되서 검색/수정 성능이 좋지 않다. (O(1)보다 많이 걸림)
• 포인터를 통해 다음 데이터를 가르키므로 포인터를 저장할 추가적인 추가적인 메모리 공간 발생.