[자료구조] 배열, 동적 배열, LinkedList

여러가지 배열들에 대해 알아보자.

선형 구조

• 자료를 순차적으로 나열한 형태이다
• ex) 배열, LinkedList, stack / queue

비선형 구조

• 하나의 자료 뒤에 다수의 자료가 올 수 있는 형태이다
• ex) 트리, 그래프

✅ 1. 배열 (Array)

• 메모리에 연속된 공간을 확보해 저장한다
• 인덱스 기반으로 O(1) 으로 접근이 가능하다
• 원소의 정해진 크기를 변경하는건 불가능하다

C# 에서의 배열

int[] arr = new int[5];

✔ 배열의 장점

• 접근 속도가 다른 배열과 비교했을 때 가장 빠르다 -> O(1)
• 메모리가 연속되므로 접근이 빠르고 성능에 좋다

❗ 배열의 단점

• 크기 변경이 불가능하다. 확장하려면 새 배열을 만들어 복제 해야 한다 -> O(n)
• 중간 삽입/삭제가 비효율적이다.

사용 예시

• 데이터 개수가 고정되어 있을 때
• 빠른 접근 속도가 필요할 때
• ex) 고정되어있는 인벤토리 슬롯

---

✅ 2. 동적 배열 (C#의 List)

• 배열의 크기 고정 문제를 해결하기 위해 만들어진 구조
• C#에서는 직접 구현하지 않고 List를 사용한다
• 필요에 따라 크기를 늘려가며 데이터를 저장한다.
  일반적으로 더 큰 메모리 블록을 할당하고 기존 데이터를 복사하는 과정이 필요하다.
  따라서 크기변경 시간이 O(n)이다.

C# 에서의 동적 배열

List<int> list = new List<int>();
list.Add(10); // 자동으로 크기가 늘어나며 삽입
list.RemoveAt(1); // 인덱스 기반 삭제 가능

✔ 동적 배열의 장점

• 유동적인 크기조절, 빠른 인덱스 접근

❗ 동적 배열의 단점

• 중간 삽입/삭제가 비효율적이다
• 크기 확장시 비용이 크다. (배열 재할당 + 전체 복사)

---

✅ 3. 연결 리스트 ( LinkedList )

• 배열과 달리 메모리가 연속되지 않는다.
• Node 라 불리우는 각 요소가 데이터와 다음 노드의 주소를 갖고있다
• C#에서의 LinkedList는 양뱡향 연결 리스트다

C# 에서의 연결 리스트

LinkedList<int> linked = new LinkedList<int>();

linked.AddLast(10);
linked.AddLast(20);

var node = linked.Find(10);
liked.AddAfter(node, 15);

✔ 연결 리스트의 장점

• 중간 추가 / 삭제에 이점이 있으며 크기 변경에 대한 제한이 없다 -> O(1)
• 배열처럼 확장 비용이 없다
• 요소 개수가 자주 바뀌고 중간에 자주 삽입/삭제가 필요할 때 좋다

❗ 연결 리스트의 단점

• N번째 요소를 바로 찾을 수 없고, 접근이 느리다 -> O(n)
• 메모리가 연속되지 않아 CPU 캐시에 비친화적이다
• List보다 전체적으로 느리다

LinkedList에 대한 정리 링크

---

LinkedList에 대한 자세한 정리 링크 이다 !