Array
배열이란 관련된 데이터들을 하나로 묶어 하나의 변수로 나타낸 선형 자료구조 중에 하나이다. 선형 자료구조 중 하나인 배열을 이용하면 하나의 변수에 여러 데이터들을 담을 수 있다. 또한, 메모리 상에서 순차적으로 나열되어 저장되는 순차 리스트에 해당된다. 순차적으로 저장되기 때문에 배열에서 인덱스를 사용하여 접근할 수 있다.
위에 예시와 같이 순차적으로 저장된 데이터를 참조하는데 인덱스를 사용하는 것을 볼 수 있다.
Array 특징
배열의 특징으로 첫 번째는 고정된 크기를 갖는다는 것이다. 만약에 배열의 크기를 5로 설정하였다고 가정한다고 했을 때 데이터가 3개만 들어있어도 똑같이 크기는 5만큼 차지한다. 만약 이런 상황이 일어난다면 메모리 낭비로 이어질 수 있다.
두 번째로는 물리적과 논리적의 저장 순서가 일치하다는 점이다. 이 말은 우리가 직접 넣은 값들이 메모리 상에서도 순차적으로 저장되어 있다는 말이다.
세 번째는 나중에 추가적으로 오버헤드가 일어나지 않는다. 우리는 배열을 선언할 때 미리 크기를 정해놓기 때문에 나중에 추가적으로 메모리를 사용하는 일은 없다.
오버헤드(Overhead)
어떤 처리를 하기 위해 들어가는 간접적인 처리 시간 · 메모리를 말한다.
네 번째는 Cache Hit Rate가 높다는 것이다.
시간 복잡도
삽입, 삭제
- O(N)
원소 접근
- O(1)
Cache Hit Rate
Cache Hit은 CPU가 참조하고자 하는 메모리가 캐시에 존재하는 상태를 말한다. 이 수치가 높을수록 좋은 성능을 가질 수 있다.
자세히 알아보기 전에 메모리에는 참조 지역성 원리라는 것이 있다. 이 원리는 동일한 값 또는 관계가 있는 메모리 주소가 자주 참조되는 특성이다. 이 지역 참조성에는 3가지가 있는데 그중에 배열은 공간 지역성이 높다. 공간 지역성은 참조된 메모리 주소와 인접한 주소가 다시 참조되는 특성이다.
배열은 메모리 상에서 연속적으로 값이 저장된다고 했었다. 그래서 배열은 공간 지역성이 매우 좋아 높은 Cache Hit Rate를 가질 수 있다.
List
리스트는 자료 구조 상에서는 배열 또한 리스트로 포함되지만 이것은 오로지 자료 구조 상에서는 그렇다. 하지만 프로그래밍을 할 때는 다르다. 언어 관점에서는 배열의 인덱스라는 특징을 버리고 메모리에 빈틈없지 적재하는 것으로 특징인 인터페이스이다.
이 말은 Linked List, ArrayList 등의 선형 자료 구조를 구현하기 위한 인터페이스이다. 하지만 배열과 다른 점이라고 하자면 배열은 순차 리스트에 해당되지만 리스트는 데이터가 순차적으로 저장되지 않아 연결 리스트라고 불린다.
Linked List 특징
첫번째는 메모리 낭비가 없다. 배열은 크기를 처음에 지정해 놓기 때문에 다 사용하지 않으면 낭비가 되지만 리스트는 가변적이기 때문에 메모리 낭비가 생기지 않는다.
두 번째는 메모리 상에서 순차적으로 값이 존재하지 않는다. 배열은 메모리에서 순차적으로 존재하지만 리스트는 순차적이 아닌 연결되어 있기 때문에 메모리 주소가 랜덤으로 존재한다.
세 번째는 두 번째에서 말한 특성으로 메모리 주소가 모두 랜덤으로 지정되기 때문에 Cache Hit Rate가 낮다.
시간 복잡도
삽입, 삭제
- O(N)
원소 접근
- O(N)
메모리에서 연속적이지 않은 값
이 말은 예시를 들자면 배열의 값은 Int는 4Byte이기 때문에 주소가
100 104 108 112이라고 가정하자면
리스트는 배열과 다르게
100 204 408 512와 같이 비연속적이고 순차적으로 존재하지 않는다.
ArrayList
자바 컬렉션에 속한 ArrayList는 Array로 이루어져있다. List의 특징과 Array의 특징을 섞어서 만든 자료 구조라고 할 수 있다.
쉽게 말하면 크기가 가변적인 배열이라고 할 수 있다. 내부적으로는 배열로 이루어져 있어 인덱스가 존재하며 순차 리스트이다.
ArrayList는 데이터를 추가할 때 중간에 추가하는 것과 맨 끝에 추가하는 것으로 나누어진다. 따로 더 많은 말이 있지만 간단하게 이야기하면 데이터를 끝에 추가할 때는 O(1)이고 중간에 추가하는 경우는 데이터를 한 칸씩 미뤄야 되기 때문에 O(N)의 시간 복잡도를 가진다.
그러면 왜 데이터를 중간과 끝으로 나눌까?
그 이유는 데이터를 끝에 넣는다고 한다면 ArrayList의 메모리 공간을 늘리고 원래 존재하던 메모리 공간이 아닌 새로운 공간을 잡아 기존의 ArrayList의 원소를 복사 후 값을 집어넣는다. 이러한 연산을 많이 사용하기 때문에 Array보다 느리다는 것이 단점이다. 그래서 ArrayList도 처음 선언할 때 크기를 정해놓고 사용하는 경우도 존재한다.
데이터를 삭제하는 연산을 사용할 경우 데이터를 앞으로 땡겨야되는 경우가 있기 때문에 O(N)의 시간 복잡도를 가진다.
정리
위에 표는 Array와 List를 정리해놓은 표이다. 위에 내용을 읽어보고 적절한 용도로 유용하게 사용하면 좋게 애플리케이션의 성능을 높일 수 있다. 또한, ArrayList는 실제 개체가 연속된 위치에 저장되지 않고 실제 개체의 참조는 인접한 위치에 저장한다는 말이 있다. 그래서 순차 리스트라고 보기 어려운 말이 있다. 유의해서 사용하면 좋을 것 같다.