Array와 List의 차이는?

배열(Array)과 리스트(List)는 모두 선형 자료구조입니다. 선형 자료구조란 원소들을 순서대로 나열한 집합을 뜻합니다.

지금 부터 각각에 대해서 특징과 차이가 무엇인지 살펴보도록 하겠습니다!

 

 

 

---

배열 (Array)

배열이란 같은 성질을 같은 항목들의 집합을 뜻합니다. 아래 그림과 같이 모든 요소들이 정수(int)를 자료형으로

갖고 있는 것을 확인할 수 있습니다. 중간에 문자열이나 다른 성질을 갖는 요소들이 들어올 수 없습니다.

또한 메모리 상에 연속적으로 데이터가 저장됩니다. 순차적으로 저장된 데이터를 참조하는데 Index가 사용됩니다.

이러한 배열에는 몇가지 특징들이 있습니다. 차례대로 살펴보도록 하겠습니다.

 

• 배열은 고정된 크기를 같습니다. 배열을 사용하기 전에 크기를 미리 지정을 하고 사용하기 때문이죠. 이는 비어 있는 공간이 있을 수 있다는 뜻이고 메모리가 낭비 될 수 있는 위험이 있음을 의미합니다. 

 

• 배열은 논리적인 저장순서와 물리적 저장 순서가 일치합니다. 이 말은 메모리의 특정 공간에 배열의 요소들이위치하게 되는데, 배열이 0번 인덱스 부터 끝 인덱스 까지 차례대로 위치하는 것처럼 메모리에서도 해당 요소들이 차례대로 위치해 있는 것을 의미합니다.

 

• 배열은 캐시 적중 확률이 높습니다. 배열은 메모리 특정 한곳에 모여 연속적으로 저장된다고 했습니다. 메모리에서배열의 특정 인덱스 데이터를 가져올 때, 참조 지역성의 원리에 따라 인접한 데이터들도 함께 가져오게 됩니다. 만약 해당 배열의 다른 인덱스의 데이터가 필요할 때, 메모리에 직접 접근하지 않고 캐시에 있는 데이터를 가져오면 되기때문에 캐시 적중률이 높아지게 됩니다.

 

• 배열은 추가적으로 소모되는 메모리 양이 없습니다. 처음부터 크기를 지정하고 쓰기 때문이죠. 

 

배열에 특정 요소를 삽입과 삭제를 할 경우 O(N)의 시간 복잡도를 갖게 됩니다. 그 이유는 메모리상에 데이터가 연속적으

로 저장되어 있기 때문에 중간에 해당 요소를 끼워 넣으려면 해당 요소 이후에 있는 데이터를 모두 뒤로 미뤄야 하기 때문입니다.

 

 

위 그림과 같은 배열이 있을 때 'K' 요소를 해당 배열의 W와 C 사이에 끼워 넣으려면 

C와 Z와 Y는 뒤로 한칸씩 이동해야 합니다. 만약 K를 배열의 제일 처음 위치에 삽입하게 된다면 배열의 갯수 만큼 뒤로

이동해줘야 할 것입니다. 시간 복잡도는 가장 최악의 경우에 걸리는 시간을 계산하는 것이기 때문에

배열의 삽입과 삭제 시간 복잡도는 따라서 O(N)이 되는 것입니다.

 

단! 배열의 맨 뒤에 삽입과 삭제를 할 경우에는 데이터들의 이동 횟수가 없으므로 O(1)의 시간복잡도를 가지게 됩니다.

 

 

반면에 원소에 접근할 때는 O(1)의 상수 시간복잡도를 가집니다. 배열은 메모리에 순차적으로 저장된다고 했습니다.

배열의 요소에 접근할 때는 메모리 주소를 알면 되는데, 배열의 첫째 요소를 기준으로 인덱스 만큼 계산하면

단 한번의 연산만으로 손쉽게 메모리에 접근할 수 있기 때문입니다.

 

예로들자면, 배열의 기본 주소인 첫 번째 요소의 메모리 주소가 100일 경우, 인덱스가 3인 요소가 저장된 메모리에

접근해야 된다고 가정해봅시다. 그리고 해당 배열은 int로 이루어져 있습니다.

 

메모리 주소는 다음과 같이 계산됩니다. 

인덱스가 3인 메모리 주소 = 100(첫번째 인덱스 주소) + 3(찾으려는 인덱스) * 4(int의 byte단위) = 112

 

다음과 같이 한번의 연산만으로 인덱스가 3인 메모리 주소 112를 파악할 수 있습니다. 따라서 배열의 특정 원소에

접근하는 시간 복잡도는 O(1)이 됩니다.

 

 

 

 

 

---

리스트(List)

 

리스트는 배열과 같이 인덱스를 사용하지 않습니다. 배열은 인덱스를 통하여 데이터를 매우 빨리 가져올 수 있었습니다.

하지만 데이터에 대한 인덱스 값을 고정되어야 하는 단점이 있습니다. 이는, 삽입과 삭제 과정에서 시간복잡도가 O(n)을

갖는 근본적인 원인이 됩니다.

 

특정 인덱스의 데이터를 삭제한다면, 인덱스는 제외하고 해당 데이터만 삭제됩니다. 즉 공간 안에 있는 데이터만 없어지고 인덱스를 포함한 공간은 그대로 남아 있음을 뜻합니다. 이것을 해결 하기 위해 뒤에 나열 된 데이터를 앞으로 하나씩 끌고와야 했습니다. 다시 말하자면, 배열은 엘리먼트가 삭제되면 빈 공간이 남게됩니다.

 

또한 배열은 초기에 크기를 설정하게 됩니다. 적절하게 크기를 설정하지 않으면, 해당 공간은 비어있는 상태가 유지되므로

메모리 낭비가 초래 될 수 있습니다.

 

이와 같이 리스트는 배열이 지닌 인덱스라는 장점을 버리고빈틈 없는 데이터 적재를 위한 자료구조라고 볼 수 있습니다.

 

리스트는 노드들을 연결하여 만듭니다. 노드는 기본적으로 헤드와 테일의 형태로 이루어져 있습니다. 각 노드의 테일에는

다음 노드의 주소 정보를 저장하고 있습니다. 

 

노드를 통하여 리스트는 순서를 지니게 되고, 빈 공간을 허용하지 않게 됩니다.

또한 데이터들이 순서대로 구성되어 있긴 하지만, 배열과 다르게 메모리 상에 연속적으로 위치해 있지는 않습니다.

 

따라서 캐시를 할 경우 참조 지역성의 효과를 보기 힘듭니다. 각각의 요소들이 메모리에 뭉쳐있지 않고 퍼져 있기 때문이죠

자연스럽게 캐시 적중률도 배열보다 떨이집니다.

 

또한 배열과 다르게 리스트는 크기가 가변적입니다. 

 

리스트는 맨 앞과 맨 뒤의 요소에 삽입과 삭제를 할 시에는 O(1)이라는 시간복잡도를 지닙니다. 왜냐하면, 제일 앞에 또는 뒤에 있는 테일 정보에 해당 노드를 등록해주기만 하면 되기 때문이죠.

 

하지만 중간에 데이터를 삽입할 경우에는 O(n)의 시간복잡도를 지니게 됩니다. 중간에 있는 요소를 찾기 까지 탐색을 해야되는데 노드끼리 연결되어 있기 때문에 배열과 같이 단 한번의 연산만으로 해당 위치를 찾기가 불가능합니다. 

 

이는 다시 말해, 리스트는 탐색할 시에 O(n) 의 시간복잡도를 가지게 되는것을 뜻합니다. 노드의 링크를 타고

순차적으로 탐색해야 되기 때문입니다.

 

 

 

---

 

 

이상으로 배열과 리스트에 대해 살펴보았습니다.

 

글 읽어주셔서 감사합니다.

 

 

---

참고 블로그

https://m.blog.naver.com/raylee00/221944085465

연결리스트(Linked List)와 배열(Array), 그리고 시간복잡도의 차이에 대해

https://bigsong.tistory.com/31

[자료구조] 배열과 리스트(Array & List)