24.08.29 Unity_C# - 자료구조의 종류, 배열과 List, ArrayList, Dictionary 차이

자료구조

자료구조는 데이터를 효율적으로 저장하고 관리하기 위한 방법이며, 선형 자료구조와 비선형 자료구조로 분류합니다.

 

선형 자료구조는 데이터가 일렬로 연결되어 있는 형태를 말합니다.

비선형 자료구조는 데이터가 여러 개의 경로를 통해 서로 연결되어 있는 구조를 말합니다.

 

선형 자료구조

1. 배열(Array)

배열은 고정된 크기의 연속적인 메모리 공간에 데이터를 저장하는 구조입니다. 배열의 각 요소는 인덱스를 통해 접근할 수 있어 데이터 검색이 매우 빠르지만 크기가 고정되어 있어 데이터의 추가나 삭제가 비효율적이며, 크기 변경이 어렵고 메모리 낭비가 발생할 수 있습니다.

 

2. 연결 리스트(Linked List)

연결 리스트는 각 노드가 데이터와 다음 노드를 가리키는 포인터로 구성되어 있습니다. 연결 리스트는 메모리를 비연속적으로 사용하여 데이터의 추가나 삭제 유연성이 높고, 메모리 사용이 효율적입니다. 그러나 특정 인덱스의 데이터에 접근하기 위해서는 처음부터 순회해야 하므로 접근 시간이 길 수 있습니다.

 

3. 스택(Stack)

스택은 후입선출(LIFO) 원리를 따르는 선형 자료구조입니다. 데이터의 삽입과 삭제가 한쪽 끝에서만 이루어지기 때문에 처리 순서가 명확합니다. 하지만 한 번에 하나의 요소만 접근할 수 있어 다양한 데이터 처리에는 제한적일 수 있습니다.

 

4. 큐(Queue)

큐는 선입선출(FIFO) 원리를 따르는 선형 자료구조입니다. 한쪽 끝에서는 삽입이, 반대쪽 끝에서는 삭제가 이루어집니다. 데이터 처리 순서가 명확하여 동적인 메모리 관리가 가능하지만, 특정 요소에 대한 빠른 접근은 제한적입니다.

 

비선형 자료구조

1. 트리(Tree)

트리는 계층적 구조를 가지는 비선형 자료구조로, 각 노드가 여러 자식 노드를 가질 수 있습니다. 트리는 데이터의 계층적 관계를 표현하기에 적합하며 검색, 삽입, 삭제 등의 연산을 효율적으로 수행할 수 있게 합니다. 다만, 트리의 구조가 복잡해질수록 관리가 어려워질 수 있습니다.

 

2. 그래프(Graph)

그래프는 노드와 그 노드들을 연결하는 간선으로 구성됩니다. 그래프는 복잡한 네트워크 관계를 모델링하기에 적합하며, 다양한 알고리즘에 활용됩니다. 그러나 구조가 복잡하여 이해하기 어려울 수 있고, 데이터 간의 충돌이나 복잡한 관계를 관리해야 할 때 어려움이 있습니다.

 

3. 해시 테이블(Hash Table)

해시 테이블은 키 - 값 쌍으로 데이터를 저장하는 자료구조로, 해시 함수를 사용하여 빠른 데이터 검색이 가능합니다.

 

---

배열

- 고정된 크기의 요소들을 저장할 수 있는 컬렉션

- 배열의 크기는 생성 시점에 결정, 변경 불가능

- 인덱스를 사용하여 요소에 직접 접근 가능

- 다차원 배열도 지원

int[] myArray = new int[3];
myArray[0] = 10;
myArray[1] = 20;
myArray[2] = 30;

int value = myArray[0]; // value = 10

 

리스트

- 동적으로 크기가 조정될 수 있는 컬렉션

- 요소의 추가, 삭제, 수정 등이 자유로움

- 인덱스를 사용하여 요소에 직접 접근 가능

- Generic으로 구현되어 타입 안정성 보장

using System.Collections.Generic;

List<int> myList = new List<int>();
myList.Add(10);
myList.Add(20);
myList.Add(30);

int value = myList[0];  // value = 10

 

ArrayList

- 동적으로 크기가 조정될 수 있는 컬렉션

- 요소의 추가, 삭제, 수정 등이 자유로움

- 인덱스를 사용하여 요소에 직접 접근 가능

- 어떤 타입의 데이터든지 저장할 수 있지만 비제네릭 형태로, 이로 인해 타입 안정성이 떨어지고 박싱,언박싱으로 인한 성능 저하가 있을 수 있음

using System.Collections;

ArrayList myArrayList = new ArrayList();
myArrayList.Add(10);
myArrayList.Add(20);
myArrayList.Add("A");

int value = (int)myArrayList[0];  // value = 10

 

*List는 Generic에 있는 인터페이스, ArrayList는 Collections에 있는 인터페이스

 

Dictionary

- 키와 값의 쌍으로 데이터를 저장

- 각 키는 유일해야 하며, 키를 사용하여 값을 검색하거나 저장

- 키와 값은 제너릭 형식으로 정의되어 있어 각각의 데이터 형식을 지정할 수 있음

- 내부적으로 해시 테이블을 사용하여 데이터를 저장

using System.Collections.Generic;

Dictionary<string,int> myDictionary = new Dictionary<string,int>();
myDictionary.Add("key1", 10);
myDictionary.Add("key2", 20);
int value = myDictionary["key1"];  // value = 10

 

Dictionary 구현 방법

딕셔너리는 내부적으로 해시 테이블을 사용하여 구현됩니다.

해시 테이블은 해시 함수를 사용하여 각 키를 해시 코드로 변환하고, 이 해시 코드를 기반으로 데이터를 저장합니다.

이로 인해 데이터의 추가, 삭제, 검색 작업을 비교적 빠르게 수행할 수 있습니다. 

Dictionary 검색 속도

딕셔너리의 검색 속도가 빠른 이유는 해시 테이블 구조 덕분입니다.

해시 함수를 통해 계산된 해시 코드를 사용하여 직접 데이터의 위치를 찾아가므로, 데이터의 양에 관계없이 일정한 속도로 탐색이 가능합니다.

평균 O(1)의 시간 복잡도, 하지만 해시 충돌이 발생하는 경우에는 시간이 더 걸릴 수 있습니다.

 

*해시 충돌은 해시 함수가 서로 다른 두 개 이상의 입력값에 대해 동일한 해시 값을 생성하는 상황

처리 방법 - 체이닝 방법 : 동일한 해시 값을 가진 여러 데이터를 연결 리스트로 연결하여 해시 테이블의 각 위치에 저장

 

 

참고

https://ctrlvgames.tistory.com/24