배열 & 리스트 & ArrayList, LinkedList

배열과 리스트는 아주 잘 사용되는 자료 구조 중 하나로 데이터의 집합을 저장하기 위한 구조이다.

 

배열

배열은 메모리 상에 연속적인 공간에 저장되며 최초로 할당받은 저장공간을 사용한다.

동일한 타입의 데이터를 연속적인 공간에 저장하기 때문에 인덱스를 이용해서 데이터가 저장된 공간으로 빠르게 이동할 수 있다.

메모리 상에 연속적인 공간에 할당되어 있기 때문에 배열의 크기를 변경하는 것은 불가능하다.

따라서 배열의 크기를 변경하고 싶을 때는 아예 크기가 큰 새로운 배열을 선언해야 한다.

 

크기가 큰 배열을 선언하고 싶을 때 메모리에 충분한 공간이 없다면 메모리 할당에 제약이 발생한다.

 

 

즉, 배열은 메모리 상 연속적인 공간에 저장되며 인덱스를 통한 접근이 가능하기 때문에 빠르게 접근 가능하며 간단하게 구현할 수 있다는 장점이 있다. 하지만 배열의 크기를 변경하는 것이 불가능하기 때문에 크기를 정확히 알 수 없을 경우에는 사용하기 어렵다는 단점이 있다.

 

 

리스트

리스트는 메모리 속 임의 위치에 저장되며 연속적이지 않다는 점이 있고 메모리에 저장 공간이 있는 한 저장 공간을 계속 할당받을 수 있다.

 

배열과 다르게 크기가 가변적이기 때문에 크기를 줄이고 늘리는데 제약이 없다. 따라서 데이터의 추가와 삭제가 빈번할 경우 사용하기 좋다.

 

또한, 리스트는 노드라고 하는 형태로 데이터를 저장하는데 노드는 다음 노드를 가리키고 있기 때문에 굳이 연속적인 공간에 데이터가 저장되어있지 않아도 다음 노드를 찾아갈 수 있다.

다만, 특정 인덱스의 노드를 찾고자 할 때 맨 첫번째 노드부터 특정 인덱스까지 이동하며 노드를 찾아가야하기 때문에 배열만큼 속도가 빠르지 않다.

 

 

그래서 언제 무엇을 써야하는가?

두 개의 자료구조는 애플리케이션의 요구 사항에 따라 선택해서 사용하면 되는데

 

배열의 경우 크기가 고정적인 데이터의 집합을 저장할 때 사용할 경우 좋다. 인덱스를 통해 빠르게 접근할 수 있기 때문이다.

리스트의 경우 데이터의 추가, 삭제가 빈번하며 데이터의 집합의 크기가 가늠이 되지 않을 경우에 사용하는 것이 좋다.

 

많은 양의 데이터를 순차적으로 접근할 일이 있다면 배열을, 데이터의 추가와 삭제가 빈번하다면 리스트를 사용해서 애플리케이션의 성능을 높이는 것이 좋겠다.

 

 

애플리케이션의 요구사항에 맞게 자료구조를 선택하는 것이 왜 그렇게 중요한 것인가 하면..

리스트는 데이터의 추가, 삭제에 용이하며 동적으로 메모리를 할당받을 수 있다는 장점이 있지만 조회하는 기능은 딱히 탁월하지 않다.

특정 인덱스의 데이터까지 이동하려면 맨 첫번째 노드부터 특정 인덱스의 노드가 나올 때까지 조회를 이어가야하기 때문이다.

 

배열은 인덱스를 통한 데이터 접근이 가능하기 때문에 조회 속도는 높지만 크기 변경이 불가하다.

 

 

 

빠른 데이터 접근이 필요할 때 리스트를 쓰고, 데이터 집합의 크기 변경이 잦은 기능에 배열을 쓰면 애플리케이션의 성능이 떨어질 수 밖에 없다. 따라서 용도에 맞게 잘 사용하는 것이 중요하다.

 

 

ArrayList vs LinkedList

 

ArrayList와 LinkedList는 Java의 List 인터페이스를 구현하는 대표 List클래스이다. 둘의 내부 구현 방식이 다르기 때문에 사용하는 용도도 다르다.

 

ArrayList

ArrayList는 기본적으로 배열을 사용한다. 다만 크기를 설정하지 않아도 되고, 동적으로 값을 추가하고 삭제할 수 있다.

배열을 사용하고 있기 때문에 인덱스를 이용해서 값을 한번에 가져올 수 있다.

 

ArrayList는 기본 설정되어 있는 할당 크기가 있는데, 이것보다 커지게 되면 더 큰 배열로 이동, 이동하며 동적으로 이루어지는 값 추가, 삭제에 대응한다.

 

LinkedList

LinkedList는 위에서 살펴본 리스트와 비슷하지만 조회를 위해 처음부터 특정 인덱스까지 이동하는 것뿐만 아니라 역방향으로도 이동이 가능한 양방향 리스트이다. 크기를 설정하지 않고 메모리 속 임의 위치에 할당되며 동적으로 값 추가, 삭제가 가능하지만 조회 속도가 느리다.

 

노드가 다음 노드를 가리키고 있는 형태이기 때문에

중간에 노드를 추가하기 위해서 이전 노드가 새로운 노드를, 새로운 노드의 다음 노드를 이전 노드의 노드를 가리키도록 설정하면 되고

삭제도 비슷하게 하면 되기 때문에 추가, 삭제가 용이하다.

 

그래서 언제 무엇을 써야하는가?

조회 시에는 ArrayList가 유리하고, 추가 및 삭제가 빈번할 경우 LinkedList가 유리하다.

 

크기가 고정적인 데이터의 집합의 조회가 빈번할 경우 ArrayList를 사용하는 것이 좋고

동적으로 데이터의 추가, 삭제 작업이 빈번할 경우 LinkedList를 사용하는 것이 좋다.

 

다만, 순차적인 추가, 삭제의 경우 ArrayList도 성능이 좋다.

 

 

그렇지만 LinkedList를 만든 사람도 LinkedList 거의 안 쓴다고 한다..