선형 자료 구조 - LinkedList, Stack, QueQue

1-1. LinkedList의 특성을 설명해주세요.

순서 유지 : 데이터는 삽입된 순서대로 유지
동적 크기 : 필요에 따라 노드를 추가하거나 제거하여 크기를 조정
삽입/삭제 효율성 : 중간 위치에 데이터 삽입/삭제 작업이 빠름 (O(1) 시간 복잡도)
임의 접근 비효율성 : 특정 인덱스의 데이터에 직접 접근하는 데 느림 (O(n) 시간 복잡도)
추가 메모리 사용 : 각 노드는 데이터와 다음 노드를 가리키는 포인터를 저장하기 때문에 메모리 사용량이 증가

1-2. LinkedList는 언제 사용하면 좋은 자료구조인가요? 반대로 언제 사용하기 불리할까요?

데이터 순서가 중요한 경우 : 데이터 삽입/삭제 순서를 유지해야 하는 경우
중간 삽입/삭제 빈도가 높은 경우 : 데이터 목록의 중간 부분에서 자주 삽입/삭제 작업을 수행해야 하는 경우
동적 크기 조정 필요한 경우 : 데이터 목록의 크기가 미리 정해지지 않고 필요에 따라 변동될 가능성이 있는 경우

2-1. Stack의 특성을 설명해주세요.

스택(Stack)은 후입선출(LIFO) 방식의 자료구조로, 요소는 한쪽 끝에서만 삽입되고 삭제된다.
연산이 단순하며 빠르다. 함수 호출 관리, 괄호 검사, 깊이 우선 탐색 등 다양한 용도로 사용된다.
메모리를 효율적으로 사용하며, 요소에 무작위 접근은 불가능하다.

2-2. Stack은 언제 사용하면 좋은 자료구조인가요? 반대로 언제 사용하기 불리할까요?

유리한 경우 : 함수의 호출을 관리할 때(C#의 호출스택), 괄호 검사 및 수식을 계산할 때, 탐색 알고리즘에서 경로를 추적할 때, 데이터를 역순화 할 때 등을 사용할 경우 유리하다

불리한 경우 : 무작위 접근이 필요할 때, 순서가 중요할 때, 대용량 데이터를 처리해야 할 때, 선입선출형 자료구조가 필요할 때, 양방향 접근이 필요할 때 등을 사용할 경우 불리하다.

3-1. Queue의 특성을 설명해주세요.

Queue는 C#에서 제공하는 컬렉션 중 하나로, FIFO(First-In, First-Out) 특성을 가진 데이터 구조이다.
이는 먼저 들어온 데이터가 먼저 나가는 구조를 의미한다.
추가, 제거가 O(1)만큼 걸린다. 선입 선출의 방식이기에 임의 접근이 불가능하다.

3-2. Queue는 언제 사용하면 좋은 자료구조인가요? 반대로 언제 사용하기 불리할까요?

선입 선출의 방식이기에 일을 들어오는 순서대로 처리를 해야하고 앞에 내용을 처리할 때 뒤에 내용을 추가하거나 대기 시켜야할 때 좋다. 예를 들어 네트워크 라우터에서 큐잉을 통해 들어온 데이터 패킷을 패킷 스위칭 하기 전에 사용하거나, BFS로 탐색한 내용을 하나씩 살펴보며 나아가는 길찾기 알고리즘 등에서 사용한다.

반대로 선입후출의 방식에서는 사용이 어렵고 임의 접근을 해야하는 데이터에서는 사용하기 불리하다.