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

전체 코드

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algorithm
{
    class Board
    {
        public int[] _data = new int[25];
        public List<int> _data2 = new List<int>();
        public LinkedList<int> _data3 = new LinkedList<int>();
        public void Initialize()
        {

        }
    }
}

🔹 자료구조 개념 정리

자료구조(Data Structure)란 데이터를 효율적으로 저장하고 관리하는 방법을 의미합니다.
자료구조는 크게 선형(Linear)과 비선형(Non-Linear)으로 나뉩니다.

• 선형 구조

  • 배열 (Array)
  • 동적 배열 (List<T>)
  • 연결 리스트 (LinkedList<T>)
  • 스택 (Stack)
  • 큐 (Queue)

• 비선형 구조

  • 트리 (Tree)
  • 그래프 (Graph)

---

🟢 1. 배열 (Array)

public int[] _data = new int[25];

✅ 배열의 특징

• 크기 고정: 배열을 생성할 때 크기를 정해야 하며, 이후 변경할 수 없습니다.
• 연속된 메모리 할당: 배열은 메모리에서 연속적인 공간을 차지합니다.
• 빠른 접근: O(1) 시간 복잡도로 특정 인덱스에 접근할 수 있습니다.
• 데이터 삽입/삭제 불편: 새로운 데이터를 삽입하거나 삭제하면 모든 요소를 이동해야 하므로 성능 저하(O(N)).

✅ 배열의 장점

• O(1) 속도로 임의 접근이 가능 (Random Access)
• 연속된 메모리를 사용하여 캐시 효율성이 좋음

❌ 배열의 단점

• 크기 변경이 불가능 (고정 크기)
• 중간에 데이터를 삽입/삭제하려면 모든 데이터를 이동해야 함 (O(N))

---

🔵 2. 동적 배열 (List)

public List<int> _data2 = new List<int>();

✅ 동적 배열의 특징

• 크기 자동 조정: 데이터가 추가되면 내부적으로 새로운 배열을 할당하여 크기를 늘립니다.
• 연속된 메모리 할당: 일반 배열처럼 연속적인 메모리를 사용하지만, 필요할 때 크기를 확장할 수 있습니다.
• 자동 재할당 비용: 크기가 초과될 때마다 새로운 공간을 확보하고 기존 데이터를 복사해야 합니다.

✅ 동적 배열의 장점

• 유동적으로 크기 조절 가능
• 배열처럼 O(1) 속도로 인덱스를 통한 접근 가능
• 중간 삽입/삭제가 불편하지만, 마지막에 추가하는 경우에는 빠름(O(1))

❌ 동적 배열의 단점

• 크기가 초과될 때 새로운 배열을 할당하고 데이터 복사하는 과정(이사 비용)이 발생
• 중간에 데이터를 삽입하거나 삭제하면 기존 데이터를 이동해야 하므로 성능 저하 (O(N))

✅ 메모리 할당 방식 (할당 정책)

동적 배열은 크기를 확장할 때 1.5배~2배 증가하는 방식으로 크기를 조정합니다.
예를 들어, List<T>의 크기가 가득 차면 다음과 같이 확장됩니다:

• 초기 크기: 4
• 데이터 추가 → 크기 8
• 데이터 추가 → 크기 16
• 데이터 추가 → 크기 32
• ...

이러한 방식으로 이사 비용을 줄이고 할당 횟수를 최소화할 수 있습니다.

---

🟠 3. 연결 리스트 (LinkedList)

public LinkedList<int> _data3 = new LinkedList<int>();

✅ 연결 리스트의 특징

• 연속된 메모리를 사용하지 않음: 각 노드가 별도의 메모리 공간을 가지며, 이전 노드와 다음 노드를 가리키는 포인터(참조)를 통해 연결됩니다.
• 임의 접근(Random Access) 불가능: 특정 요소를 찾으려면 처음부터 탐색해야 합니다 (O(N)).
• 중간 삽입/삭제가 빠름: 포인터만 변경하면 되므로, 중간에 데이터를 추가하거나 삭제하는 경우 배열보다 성능이 좋음 (O(1)).

✅ 연결 리스트의 장점

• 크기 제한이 없으며, 필요할 때마다 노드를 동적으로 추가할 수 있음
• 중간 삽입/삭제가 빠름 (O(1))

❌ 연결 리스트의 단점

• 특정 인덱스로 접근하는 속도가 느림 (O(N))
• 추가적인 메모리 사용 (포인터 저장을 위한 메모리 필요)

---

🔥 자료구조 비교표

자료구조	크기 변경	메모리 연속성	접근 속도	삽입/삭제 속도
배열 (Array)	❌ 불가능	✅ 연속적	✅ O(1)	❌ O(N) (중간 삽입/삭제)
동적 배열 (List)	✅ 가능	✅ 연속적	✅ O(1)	❌ O(N) (중간 삽입/삭제)
연결 리스트 (LinkedList)	✅ 가능	❌ 비연속적	❌ O(N)	✅ O(1) (중간 삽입/삭제)

---