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

배열과 리스트는 데이터를 저장하고 관리하는 기본적인 자료 구조입니다.  두 자료 구조는 각각의 특성과 장단점이 있으며,  용도에 따라 적합한 선택이 필요합니다. 

 

배열 (Array)

특징

• 고정 크기: 배열은 생성 시 크기가 정해지며, 이후에는 크기를 변경할 수 없습니다.
• 인덱스 접근: 배열의 요소는 인덱스를 통해 O(1) 시간 복잡도로 접근할 수 있습니다.
• 동일한 데이터 타입: 배열의 모든 요소는 동일한 데이터 타입을 가져야 합니다. 

장점

• 빠른 접근 속도: 인덱스를 통해 요소에 바로 접근할 수 있어 매우 빠릅니다.
• 메모리 효율성: 요소들이 연속된 메모리 공간에 저장되어 있어 메모리 접근이 효율적입니다.
• 간단한 구조: 구조가 단순하여 오버헤드가 적습니다.

단점

• 고정 크기: 배열의 크기를 동적으로 변경할 수 없으므로, 크기를 잘못 설정하면 메모리 낭비 또는 부족 문제가 발생할 수 있습니다.
• 삽입과 삭제 비용: 중간에 요소를 삽입하거나 삭제할 때, 다른 요소들을 이동시켜야 하므로 O(n)의 시간이 소요됩니다.
• 단일 데이터 타입: 다양한 데이터 타입을 저장하기 어렵습니다.

 

배열의 오프셋(Offset)

배열의 오프셋은 배열의 시작 주소로부터 특정 요소까지의 거리를 의미합니다. 이 거리는 보통 바이트 단위로 측정됩니다. 오프셋을 사용하면 배열의 특정 요소에 접근할 수 있습니다.

 

임의의 배열 요소 A [i] 에 액세스 하려면 다음을 찾아야 합니다.

 

배열 요소 의 시작 위치 는 합계 로 계산할 수 있습니다.

 

배열의 시작 과 배열 요소 A[i] 의 시작 사이에 i 개의 배열 요소 가 있습니다 .

 

우리는 배열 의 데이터 유형을 알고 있으므로 각 배열 요소 의 크기 (= 바이트 수 ) 도 알고 있습니다 .

각 배열 요소 의 데이터 유형이 동일 하므로 (따라서 각 배열 요소가 동일한 바이트 수를 차지함 ) 배열 요소 A[i] 에 대한 오프셋은 다음과 같습니다.

offset to A[i] =  i × size(one array element)

 

요약하자면 , 배열 요소 A[i] ( 인덱스 i ) 의 시작 위치 (=주소)는 다음 과 같이 계산할 수 있습니다.

start address of array element A[i] =  base address of array
                                          + i × size(one array element)

---

 

리스트 (List)

특징

• 동적 크기: 리스트는 요소의 추가와 삭제에 따라 크기가 동적으로 변합니다.
• 인덱스 접근 또는 순차 접근: 구현 방식에 따라 다르지만, 일반적으로 배열 기반 리스트는 인덱스 접근이 가능하고, 연결 리스트는 순차 접근이 필요합니다.
• 다양한 데이터 타입: 리스트는 서로 다른 데이터 타입의 요소를 저장할 수 있습니다.

장점

• 유연성: 크기가 동적으로 변하므로, 요소의 추가와 삭제가 용이합니다.
• 다양한 데이터 타입: 서로 다른 타입의 데이터를 저장할 수 있어 유연한 데이터 구조를 구성할 수 있습니다.
• 삽입과 삭제 효율성 (연결 리스트): 연결 리스트는 삽입과 삭제가 O(1) 시간 복잡도로 가능합니다(노드 포인터를 재설정하는 경우).

단점

• 접근 속도: 연결 리스트는 특정 요소에 접근하기 위해 순차적으로 탐색해야 하므로, 접근 시간이 O(n)일 수 있습니다.
• 메모리 오버헤드: 연결 리스트의 경우, 각 요소가 추가적인 포인터를 저장해야 하므로 메모리 사용이 비효율적일 수 있습니다.
• 복잡성: 구현과 관리가 배열에 비해 복잡할 수 있습니다.

 

배열과 리스트의 차이점

1. 메모리 할당: 배열은 연속적인 메모리 공간에 할당되고, 리스트는 비연속적인 메모리 공간에 할당된다.
2. 크기: 배열은 크기가 고정되어 있으며, 리스트는 가변적이다.
3. 접근 방법: 배열은 인덱스를 통한 빠른 접근이 가능하지만, 리스트는 순차적으로 접근해야 한다.
4. 삽입과 삭제: 배열은 삽입과 삭제가 번거롭고 시간이 오래 걸리지만, 리스트는 삽입과 삭제가 빠르다.

배열(Array)을 사용할 상황 예시

1. 데이터의 크기가 고정되어 있고, 변경될 일이 없는 경우: 배열의 크기가 고정되어 있으므로, 변경되지 않는 크기의 데이터를 다룰 때 적합하다.
2. 빠른 인덱스 기반 접근이 필요한 경우: 배열은 연속적인 메모리 공간에 저장되어 있어 인덱스를 통한 접근이 빠르다. 따라서, 특정 위치의 데이터에 빠르게 접근해야 할 때 유용하다.

리스트(List)를 사용할 상황 예시

1. 데이터의 크기가 불확실하거나 가변적인 경우: 리스트의 크기는 가변적이기 때문에, 크기가 불확실하거나 자주 변경되는 데이터를 다룰 때 적합하다.
2. 데이터의 삽입과 삭제가 빈번한 경우: 리스트는 삽입과 삭제가 빠르기 때문에, 데이터를 자주 추가하거나 삭제해야 하는 경우에 유용하다.

 

요약하자면 배열은 정적이고 빠른 접근이 필요한 경우에 유용하며, 리스트는 동적이고 유연한 데이터 구조가 필요할 때 유리합니다.  선택은 사용자의 요구 사항에 따라 달라집니다.