C# - 배열, 동적 배열, 연결 리스트 비교

선형 구조

자료를 순차적으로 나열한 형태

ex) 배열, 연결 리스트, 스택 / 큐

---

비선형 구조

하나의 자료 뒤에 다수의 자료가 올 수 있는 형태

ex ) 트리, 그래프

---

배열(Array)

고정된 크기의 메모리 블록에 원소들을 순차적으로 저장, 이 원소들은 정해진 크기를 절대 변경할 수 없다

연속된 메모리 공간에 저장되기 때문에 인덱스를 통해 O(1)시간에 RandomAccess가 가능하다.

장점 : 메모리 접근이 빠르고 예측 가능하다.

단점 : 크기 변경이 어렵고 중간에 삽입/삭제가 비효율적이다.

---

동적 배열(Dynamic Array)

배열의 크기를 동적으로 변경할 수 있다. 처음에는 작은 크기로 시작하여 필요에 따라 크기를 늘려가면서 데이터를 저장한다. 그렇기 때문에 일반적으로 더 큰 메모리 블록을 할당하고 기존 데이터를 복사하는 과정이 필요하다. 그러므로 크기변경 시간이 O(N)이다.

동적 배열 할당 정책

실제로 사용할 요소의 갯수 보다 많이 여유분을 두고 (대략 1.5배~2배) 크기를 결정 이를 통해 배열의 크기를 동적으로 조절함으로써 데이터의 추가/삭제를 효율적으로 처리하고 이사 횟수를 최소화 할 수 있다.

이사 횟수를 최소

장점 : 유동적인 크기 조절이 가능하며 임의 접근이 가능하다.

단점 : 크기 변경시에 복사 비용이 들며 중간 삽입/삭제가 여전히 비효율적이다.

---

연결 리스트(LinkedList)

노드라 불리는 개별 요소들이 연결되어 있는 구조이다. 각 노드는 데이터와 다음 노드를 가리키는 포인터로 구성되어 있다. 메모리 공간이 연속되지 않아 중간에 노드를 추가/삭제하는데 비교적 유연하다. 하지만 임의 접근이 불가능하여 N번째 노드에 접근하기 위해서는 처음부터 순차적으로 접근해야 한다.

장점 : 중간 추가/ 삭제에 이점이 있으며 크기 변경에 대한 제한이 없다.

단점 : N번째 요소를 바로 찾을 수가 없고 (임의 접근 Random Access 불가) 메모리 오버헤드가 발생할 수 있다.