배열(Array)과 리스트(List)

이번 글에서는 배열과 리스트, 그리고 둘의 장단점과 이를 통해 둘의 차이를 알아보도록 하자.

배열(Array)

---

먼저 Array에 대해서 알아보자.

Array는 여러 개의 데이터들을 효율적으로 저장/관리/사용하기위해 사용되는 자료형이다.

Array는 같은 자료형을 가진 데이터들을 묶어서 저장하는데, 이 각각의 데이터들을 배열 요소(Element)라고한다.

또한 이 각각의 Element들의 위치에 번호를 붙여서 그 위치에 Access하는 구조로 되어있는데, 이 번호를 Index라고 한다.

 

Array의 주요 특징은 메모리상에 데이터들이 `연속적`으로 저장되어있다는 점과 선언시에 크기를 지정해주어야한다는 점이다.

이를 그림으로 표현하면 아래와 같다.

위 그림은 int형의 크기 5개짜리 배열을 선언하였을 때를 표현한 것이다.

프로그래밍에서 int형은 4Byte의 크기를 갖는데, Array를 선언할 때 Element마다 4Byte씩 총 20Byte의 공간을 메모리에 확보한다.

 

이러한 Array의 특징으로인해 장/단점이 나뉘게되는데

Array와 같은 여러 개의 데이터들을 다루는 자료형에는 보통 다음과 같은 작업들이 가능할 것이다.

Insert(삽입), Delete(삭제), Read(읽기)

 

여기서 Array는 Read작업을 할 때 가장 효율적으로 동작한다.

그 이유에 대해서 알아볼텐데, 위에서 말했듯이 Array는 연속적인 공간상에 위치하고있다.

즉, Array의 시작 주소를 알면 해당 주소는 Array의 첫 번째 값이 있는 주소이고,

그 곳에서 몇 칸을 이동하면 Array의 몇 번째로 요소로 갈 수 있는지 바로 계산할 수 있다.

 

또한 우리가 사용하는 메모리는 RandomAccessMemory를 사용하고있다.

RandomAccessMemory에 대한 내용은 여기서 자세히 설명하진 않을텐데, 간단히 말하자면

메모리상의 어느 위치에 접근하더라도 속도가 동일한 메모리를 의미한다.

 

때문에 Array에서 시작 주소를 알고, 우리가 몇 번째 요소를 읽을지만 알고있다면(index를 통해)

모든 요소에 동일한 시간으로 접근하여 Element를 읽어올 수 있다는 뜻이다.

따라서 Array는 index를 통한 Read에 매우 효율적인 높은 성능을 보여준다.

 

반면, Read왜의 다른 세 가지 작업에는 조금 비효율적인 낮은 성능을 보여준다.

먼저 Insert에 대해서부터 살펴보자.

위에서 말했듯이 Array는 크기를 사전에 정해두고 선언한다.

 

때문에 Insert, 즉 새로운 데이터를 넣기 위해서는 새로운 Array를 생성하고,

이전에 있던 Array의 내용을 전부 복사해서 넣은다음에 마지막 위치에 Insert를 해주어야 한다.

이건 Array의 끝에 데이터를 넣는 상황이기 때문에 오히려 양반이다.

 

Array의 중간에 데이터를 넣는다고하면 어떨까?

위와 같이 Array를 전부 복사한 다음 데이터를 새로 넣을 위치를 기준으로 뒤에 있는 모든 Element들을 한 칸씩 뒤로 밀어주어야 한다.

 

만약 데이터를 Array맨 앞에 추가해야한다면?

상상만 해도 끔찍하다..

 

마찬가지로 Delete의 경우에도 중간에 있는 Element를 삭제했다고 생각해보자.

그러면 Array의 중간에서 사용하지도 않는 메모리 공간을 잡고있는데(null), 이는 메모리의 낭비이다.

때문에 비어있는 칸을 채우기 위해서 삭제한 Element위치 기준으로 뒤에 있는 모든 Element들을 앞으로 당겨주어야 한다.

 

이렇듯 Array는 데이터 Read에는 매우 탁월한 성능을 보여주지만, Insert, Delete등의 작업에는 안좋은 성능을 보여준다.

때문에 Array는 정해진 크기를 가지는 여러 개의 데이터 집합을 읽을 때 사용하는것이 좋다.

리스트(List)

---

그렇다면 List는 어떨까?

사실 우리가 흔히 말하는 List는 Linked List를 말하는것이다.

Linked List라는 것은 아래와 같은 그림으로 되어있다.

여기서 int는 int형 데이터를 말한다.

즉, Linked List라는건 각각의 Element가(List에서도 각 요소를 Element라고 한다.)

실제 데이터와, 다음 Element의 주소에 대한 값을 가지고 있는 형태이다.

 

Array와 List의 가장 큰 차이가 여기서 나오는데, List는 데이터가 메모리상에 연속적으로 위치해있지않다.

위와 같이 떨어진 데이터들을 각각 이어주고있는것이다.

또한 메모리 공간을 미리 확보할 필요가 없기때문에 List는 선언시에 크기를 지정하지 않는다.

 

 

그러면 여기서 Array에서 보았던 세 가지 동작들을 생각해보자.

Insert(삽입), Delete(제거), Read(읽기)

 

List에선 Array처럼 index와 시작 주소만으로 동일한 시간에 각 Element에 접근할 수가 없다.

위에서 말한대로 이전 Element가 다음 Element를 가리키고, 이를 타고 들어가면서 각 Element에 접근하는 구조이기 때문이다.

때문에 Read의 경우 List는 Array보다 상대적으로 안좋은 성능을 보여준다.

 

그럼 다음은 Insert에 대해서 생각해보자.

List에서 데이터를 추가하려면 어떻게 해야될까?

그림으로 한 번 살펴보자.

가장 먼저 메모리 공간 어딘가에 List에 새로 Insert할 데이터를 생성한다.

여기서 우리가 데이터를 Insert할 index는 2번, 기존에 2번을 가리키고있던 Element의 index를 1번이라고 하자.

다음으로 1번이 가리키던 주소를 새로 입력할 데이터가 있는 주소로 바꿔준다.

마지막으로 새로 추가된 Element(2번)가 가리키는 주소를 이전에 1번이 가리키던 주소로 변경해주면 끝이다.

 

위와 같은 동작으로 데이터 추가가 이루어지는데, 위에서 Array 전체를 복사해서 추가하고,

모든 데이터들을 뒤로 미는 등의 작업과 비교했을 때 매우 우수한 성능을 보여준다.

 

이는 Delete를 할 때도 마찬가지인데, 이 경우에는 중간에 있는 Element를 삭제하고,

해당 Element가 가리키던 주소를 삭제한 Element를 가리키던 Element에게 가리키도록 해주면 된다.

말로하니 조금 이상하게 된 것 같은데, 위의 Insert동작을 제대로 이해했다면 문제는 없을거라고 생각한다.

 

위와 같은 특징들 때문에 List의 경우는 데이터를 빈번하게 Insert, Delete해야하는 경우에 사용하면 좋을것이다.

Array와 List의 장단점

---

위와 같은 내용들을 통해 Array와 List의 장단점에 대해서 확인해보자.

Array의 장점

1. index와 RandomAccess를 통해 Reading동작이 빠르다.

2. 연속된 메모리 공간에 위치하기 때문에 메모리 관리가 용이하다.

Array의 단점

1. 배열 생성시 크기를 정해주어야 하며, 추후에 변경할 수 없다.

2. Insert/Delete작업 시 배열의 추가 생성, 각 Element의 이동 등 때문에 비효율적이다.

 

List의 장점

1. Insert/Delete동작에서 각 Element가 가리키는 주소만 변경하면 되기 때문에 효율적이다.

2. 크기가 고정적이지 않기 때문에 Array와 같은 불편함이 없다.

List의 단점

1. 각 Element가 다른 Element를 가리키는 형태이기 때문에 Reading작업에 비효율적이다.

2. 다른 Element의 주소를 저장하기 위해 추가적인 메모리 공간 사용이 필요하다.

 

이상으로 Array와 List, 그리고 둘의 장단점에 대해서 알아보았다.

글이 도움이 되셨으면 좋겠습니다.