오늘 드디어 자료구조로 들어가는 날입니다.
아마도 프로그래밍을 배우면서 많이 들었던 말은 자료구조와 알고리즘을 잘 알고 있어야
기업에서 좋아한다는 말일 겁니다.
저도 대학생 때 교수님께서 그 부분을 상당히 강조하시면서 전공과 크게 관련은 없었지만
스스로 찾아보면서 배우라고 하셨던 기억이 나네요. 전공 공부하기도 힘들었는데...😭
1. 📖 자료구조
그러면 그 중요한 자료구조는 무엇일까요?
말 그대로 자료 즉 데이터들의 구조의 형태들을 말합니다.
이 데이터들은 어떻게 배치하고, 어떻게 사용하느냐에 따라 구성한 프로그램의 효율이 달라지기 때문에 수많은 데이터들을 더 효율적으로 저장하고, 더 빠르게 찾아서 사용하기 위해 사용되는 데이터 저장 기법으로 정의할 수 있겠습니다.
1. 📖 C#에 구현되어 있는 자료구조
1-1 🔖 리스트
리스트는 배열과 유사하지만 차이점이 있습니다.
배열의 경우 5개로 크기가 이미 정해진 상태로 있습니다.
int[] array = new int[5];
리스트는 한번에 배치되는 것이 아닌 점점 데이터가 추가되는 차이가 있습니다.
즉, 필요할 때 데이터를 추가하고 제거할 수 있습니다.
List<int> list = new List<int>();
list.Add(1);
list.Add(2);
list.Add(3);
list.Add(4);
list.Remove(1);
list.Remove(2);배열과 동일하게 인덱스 접근이 가능하여 데이터를 바꿀 수 있다
list[1] = 5; // 1 자리의 데이터를 5로 변경한다
int value = list[1];1-1-1 ✔️ 리스트 기능 정리
리스트도 많은 기능들이 있는데 일단 많이 사용하는 기능을 정리해보겠습니다.
⭕ 데이터 추가
list.Add(1); // 1 추가하기⭕ 데이터 삭제
중간에 데이터를 삭제한 뒤 빈자리를 채우기 위해 이후 데이터들을 앞으로 당깁니다.
list.Remove(1); // 1을 찾아 지워주기⭕ 특정 위치에 있는 요소 지우기
list.RemoveAt(1); // 1번 위치에 있는 요소 지우기⭕ 삽입 기능
중간에 데이터를 추가하기 위해 이후 데이터들을 뒤로 밀어내고 삽입을 진행합니다.
list.Insert(1, 5); // 중간에 끼워넣기 1번 자리에 5 끼워넣기⭕ 탐색하는 기능 1 (있으면 인덱스 값을 출력)
list.IndexOf(4); // 4를 찾는다 만약 못찾으면 -1로 나온다⭕ 탐색하는 기능 2 (있는지 없는지만 판단)
bool contain = list.Contains(4); // 4번 자리에 찾아서 있으면 true 없으면 false ✔️ 1-1-2 리스트 용량
보통은 리스트는 여분의 용량을 고려해서 만들어주기는 하지만 프로그램을 사용하다보면 용량이 가득 찬 상황에서 데이터를 추가하는 경우가 생길 수도 있습니다.
이 때 리스트는 더 큰 용량의 배열을 새로 생성한 뒤 데이터를 복사하여 새로운 배열을 사용합니다!
List<int> list = new List<int>();
for (int i = 0; i < 10; i++)
{
list.Add(i);
Console.WriteLine("Count = {0}, Capacity = {1}", list.Count, list.Capacity);
}Count = 1, Capacity = 4
Count = 2, Capacity = 4
Count = 3, Capacity = 4
Count = 4, Capacity = 4
Count = 5, Capacity = 8
Count = 6, Capacity = 8
Count = 7, Capacity = 8
Count = 8, Capacity = 8
Count = 9, Capacity = 16
Count = 10, Capacity = 16코드 결과를 보시면 Count가 진행될 수록 수용범위가 계속 증가하는 것을 알 수 있습니다.
자동으로 용량을 늘려주긴 하지만 용량을 늘리는 작업 자체가 성능에 영향을 주기 때문에
미리 수용범위를 선정해주는 것이 중요합니다.
List<int> list = new List<int>();
list.Capacity = 30; // 미리 수용범위 지정
for (int i = 0; i < 10; i++)
{
list.Add(i);
Console.WriteLine("Count = {0}, Capacity = {1}", list.Count, list.Capacity);
}Count = 1, Capacity = 30
Count = 2, Capacity = 30
Count = 3, Capacity = 30
Count = 4, Capacity = 30
Count = 5, Capacity = 30
Count = 6, Capacity = 30
Count = 7, Capacity = 30
Count = 8, Capacity = 30
Count = 9, Capacity = 30
Count = 10, Capacity = 301-2 🔖 링크드 리스트
list의 경우 순차적 데이터가 저장되기 때문에 데이터를 추가하거나 삭제할 때 데이터를 밀어주는 작업이 진행됩니다. 결국은 중간에 추가하거나 삭제를 할 때 효율적이지 않은 자료구조입니다.
linkedlist는 연속적으로 위치하지 않지만 하나의 원소가 Node로 연결되어 있습니다.
데이터를 노드를 통해 연결식으로 구성하기 때문에 데이터의 추가나 삭제할 때 데이터들을 뒤로 미는 과정 없이 그냥 연결만 해주기 때문에 list보다는 효율적인 특징을 가지고 있습니다.
Node로 연결은 되어있지만 순차적이지 않아 난잡하게 되어있기 때문에 Index로 찾을 수 없습니다.
1-2-1 ✔️ 연결리스트
⭕ 단방향 연결리스트
노드가 다음 노드를 참조하는 방식
A → B → C → D
⭕ 양방향 연결리스트 (C#이 사용하는 연결 리스트)
노드가 이전/다음 노드를 참조하는 방식
A ↔ B ↔ C ↔ D
⭕ 원형 연결리스트
노드가 이전/다음 노드를 참조하며, 시작 노드와 마지막 노드를 참조하는 방식
1-2-2 ✔️ 링크드 리스트
LinkedList<int> linkedList = new LinkedList<int>();
// 추가 기능
LinkedListNode<int> node0 = linkedList.AddFirst(2);
LinkedListNode<int> node1 = linkedList.AddLast(9);
LinkedListNode<int> node2 = linkedList.AddLast(10);
LinkedListNode<int> node3 = linkedList.AddFirst(1);
LinkedListNode<int> node4 = linkedList.AddBefore(node1, 8);
LinkedListNode<int> node5 = linkedList.AddAfter(node0, 3);
// 삭제 기능
linkedList.Remove(10);
linkedList.Remove(node1);
linkedList.RemoveFirst();
linkedList.RemoveLast();
// 접근 기능
LinkedListNode<int> firstNode = linkedList.First;
LinkedListNode<int> lastNode = linkedList.Last;
LinkedListNode<int> prevNode = node0.Previous;
LinkedListNode<int> nextNode = node0.Next;
// 탐색 기능
LinkedListNode<int> findNode = linkedList.Find(9); // 못 찾으면 Null을 배출한다.
bool contain = linkedlist.Contain(9);