자료구조
자료 구조란?
자료 구조는 데이터를 어떻게 저장할 것인가이다.
이것은 데이터를 단순히 저장하는 것뿐만 아니라 데이터간의 연결성, 데이터열람에 대한 알고리즘 등 데이터를 다루는 것에 대한 총 망라라고 볼 수 있다.
데이터의 관리는 어떤 서비스냐에 따라 데이터를 다루는 방법이 다양하다. 어떤 것들이 있는지, 그것들은 어떻게 다룰 것인지 확인해보도록 하자.
Big-O
데이터 연산에 대한 성능을 예측 및 측정하는 수학적 기법
- 공간 복잡도; 해당 프로그램이 실행시 얼마나 많은 메모리를 필요로 하는지에 대한 척도.
- 시간 복잡도; 자료에 대한 동작을 얼마나 빠르게 하는지에 대한 척도.
- O(1); 1회의 호출로 데이터를 호출. ex) 배열 인덱스
- O(N); 1개의 Loop를 활용하여 데이터를 검색. ex) 배열 순회
- O(N^M); 다중 배열에 대해 N중 Loop문을 이용하여 데이터를 검색. ex) 2차, 3차 배열
- O(log N); 탐색 대상을 줄여가며 찾아가는 방법.
동작
- 삽입; 구조에 데이터를 추가.
- 검색; 구조 전체를 대상으로 목표물 찾기.
- 삭제; 구조내 데이터를 제거.
- 읽기; 특정 위치 요소에 접근.
List 와 LinkedList
List
동적 배열로 배열의 크기를 자유롭게 조정할 수 있다.
이미 선언한 크기를 단순히 크게 키우는 것이 아니라(Resize), 데이터를 붙이거나, 빼거나 하며 크기가 조절될 수 있다는 것이다.
크기가 자유롭지만 크기가 변동되면 메모리를 2배 크기로 재할당되기 때문에 유의해야 한다.
코드 예시
List<int> list = new List<int>();
// List 에 맨 뒤에 데이터 추가
list.Add(1);
list.Add(2);
list.Add(3);
list.Add(4);
PrintList(list); // 출력: 1 2 3 4
// List 에 특정 위치에 데이터 추가
list.Insert(1, 5);
list.Insert(3, 6);
PrintList(list); // 출력: 1 5 2 6 3 4
// List 에 특정 위치의 데이터 삭제
list.RemoveAt(0);
// List 에 특정 데이터 삭제
list.Remove(6);
PrintList(list); // 출력: 5 2 3 4
// List 내 특정 데이터 확인 여부
Console.WriteLine($"list.Contains(3) = {list.Contains(3)}"); // 출력: list.Contains(3) = True
Console.WriteLine($"list.Contains(10) = {list.Contains(10)}"); // 출력: list.Contains(10) = False
// List 내 아이템 개수
Console.WriteLine(list.Count); // 출력: 4참고
List 의 크기를 미리 정하지 않고 계속 "Add"할 경우, 기본 관리 Capasity는 4이다.
처음 할당하면 0이지만 Add하는 순간 4개가 할당된다.
// List`1.cs
private void EnsureCapacity(int min)
{
if (this._items.Length >= min)
return;
int num = this._items.Length == 0 ? 4 : this._items.Length * 2; // 기본 사이징 4.
if ((uint) num > 2146435071U)
num = 2146435071;
if (num < min)
num = min;
this.Capacity = num;
}LinkedList
LinkedList 는 List 처럼 보이지만 실제로 메모리 공간상 배열등처럼 연속적이게 있지 않게 된다.
따라서 배열이나 List처럼 단순히 Index로 접근할 수 없다
List 와 LinkdedList 의 가장 큰 차이점은 데이터를 삽입 하는데에 대한 시간 복잡도가 다르다는 것이다.
List 는 데이터 삽입을 위해서는 삽입 위치 뒤의 아이템을 뒤로 밀어야 하기 때문에 O(N)의 시간 복잡도를 갖는다.
반면에 LinkedList 는 참조값만 변경되기 때문에 O(1)의 시간 복잡도를 갖게 된다.
LinkedList종류
- 단일 연결리스트: 앞 item 은 뒤 item 의 위치를 모른다.
- 원형 연결리스트: 맨 뒤는 맨 앞의 위치를 안다.
- 이중 연결리스트: 서로간의 위치를 안다. ; C#에서는 이것으로 되어 있다.
- 원형 이중 연결리스트: 맨 뒤와 맨 앞은 서로가 위치를 안다.
순차와 연결 자료구조의 차이점
간단히 순차자료구조는 배열, 연결자료구조는 노드로 볼 수 있다.
코드 예시
LinkedList<int> linkedList = new LinkedList<int>();
LinkedListNode<int> node;
linkedList.AddFirst(1); // [1]
linkedList.AddFirst(2); // [2] [1]
linkedList.AddLast(3); // [2] [1] [3]
node = linkedList.AddLast(4); // [2] [1] [3] [4]
linkedList.AddBefore(node, 5); // [2] [1] [3] [5] [4]
node = linkedList.Find(1); // Node 의 값을 이용한 검색 ; O(N)
node = linkedList.AddAfter(node, 6); // [2] [1] [6] [3] [5] [4]
Console.WriteLine(node.Previous.Value); // 출력: 1
Console.WriteLine(node.Next.Value); // 출력: 3
// linkedList[1]; // 접근할 수 없다! Statck 과 Queue
Stack 과 Queue는 선형적 데이터 구조에 순서가 추가된 구조 이다.
Stack
Stack은 간단히 후입선출구조라고 이야기 할 수 있다.
먼저 들어간 데이터는 가장 나중에 나오고, 가장 나중에 들어간 데이터가 가장 먼저 나오게 된다.
코드 예시
Stack<int> stack = new Stack<int>();
for (int i = 0; i < 10; i++)
{
stack.Push(i * 2);
}
// stack => 0, 2, 4, 6, 8, 10, 12, 14, 16, 18
Console.WriteLine(stack.Peek()); // 18 (Just view at last item)
foreach (var item in stack)
{
Console.Write($"{item} "); // 18 16 14 12 10 8 6 4 2 0
} // Just view the all items.
Console.WriteLine();
while (stack.Count > 0)
{
Console.WriteLine($"{stack.Pop()} => Remain: {stack.Count}");
}
// 출력:
// 18 => Remain: 9
// 16 => Remain: 8
// 14 => Remain: 7
// 12 => Remain: 6
// 10 => Remain: 5
// 8 => Remain: 4
// 6 => Remain: 3
// 4 => Remain: 2
// 2 => Remain: 1
// 0 => Remain: 0Queue
Queue는 선입선출구조이다.
먼저 들어간 데이터가 먼저 나오게 된다.
일반적인 대기열이라 볼 수 있다.
코드 예시
Queue<int> queue = new Queue<int>();
for (int i = 0; i < 10; i++)
{
queue.Enqueue(i * 2);
}
// queue => 0 2 4 6 8 10 12 14 16 18
Console.WriteLine(queue.Peek()); // 0 (Just view at first item)
foreach (var item in queue)
{
Console.Write($"{item} "); // 0 2 4 6 8 10 12 14 16 18
} // Just view the all items.
Console.WriteLine();
while (queue.Count > 0)
{
Console.WriteLine($"{queue.Dequeue()} => Remain: {queue.Count}");
}
// 출력:
// 0 => Remain: 9
// 2 => Remain: 8
// 4 => Remain: 7
// 6 => Remain: 6
// 8 => Remain: 5
// 10 => Remain: 4
// 12 => Remain: 3
// 14 => Remain: 2
// 16 => Remain: 1
// 18 => Remain: 0