데이터 구조는 소프트웨어 엔지니어링의 필수 요소이자, 모든 프로그래밍 학습자들이 숙달해야 하는 핵심 구성 요소다. 그것들은 프로그래밍의 중요한 부분이기 때문에 거의 모든 프로젝트에서 사용해야 하며, 주어진 시나리오에 어떤 데이터 구조가 이상적인지 아는 것이 중요하다.
따라서, 취업을 준비하는 개발자라면 면접관이 데이터 구조와 관련된 질문을 할 수 있으므로, 데이터 구조 지식을 미리 복습하는 것이 좋다. 프로그래머와 면접을 위한 가장 중요한 데이터 구조를 나열하며, 반복 학습하는 것이 도움 된다.
MakeUseOf의 작가이자 컴퓨터 공학을 전공한 M. 파하드 카와자는 "처음에는 힘들게 보일 수 있지만 충분한 시간을 할애하면 파이처럼 쉽게 찾을 수 있다"고 조언했다. 다음은 파하드 카와자가 꼽은 프로그래머가 알아야 할 6가지 데이터 구조다.
1. 연결 리스트
연결 목록은 가장 기본적인 데이터 구조 중 하나로, 대부분의 데이터 구조 과정에서 학생들이 시작하는 경우가 많다. 연결 목록은 순차적 데이터 액세스를 허용하는 선형 데이터 구조다.
연결 목록 내의 요소는 포인터를 사용하여 연결된 개별 노드에 저장된다. 연결 목록은 다른 포인터를 통해 서로 연결된 노드 체인으로 생각할 수 있다.
2. 이진 트리
이진 트리는 트리 패밀리 데이터 구조의 가장 인기 있는 하위 집합이다. 이진 트리의 요소는 계층 구조로 배열되며, 다른 유형의 트리에는 AVL, 레드-블랙, B 트리 등이 있다. 이진 트리의 노드에는 데이터 요소와 각 자식 노드에 대한 두 개의 포인터가 포함된다.
이진 트리의 각 부모 노드는 최대 두 개의 자식 노드를 가질 수 있으며 각 자식 노드는 차례로 두 노드의 부모가 될 수 있다.
3. 해시 테이블
해시 테이블 또는 해시 맵은 데이터를 배열 형식으로 저장하는 매우 효율적인 데이터 구조다. 각 데이터 요소에는 해시 테이블의 고유 인덱스 값이 할당되어 효율적인 검색 및 삭제가 가능하다.
해시 맵에서 키를 할당하거나 매핑하는 프로세스를 해싱이라고 한다. 해시 함수의 효율성이 높을수록 해시 테이블 자체의 효율성이 높아진다. 각 해시 테이블은 값-색인 쌍에 데이터 요소를 저장한다.
여기서 값은 저장할 데이터고 인덱스는 요소를 테이블에 매핑하는 데 사용되는 고유 정수다. 해시 함수는 해시 테이블의 필요한 효율성과 충돌을 해결하는 방법에 따라 매우 복잡하거나 매우 간단할 수 있다.
충돌은 해시 함수가 다른 요소에 대해 동일한 매핑을 생성할 때 종종 발생한다. 해시 맵 충돌은 개방형 주소 지정 또는 체인을 사용하여 다양한 방식으로 해결할 수 있다.
해시 테이블 또는 해시 맵에는 암호화를 포함하여 다양한 응용 프로그램이 있으며, 상수 O(1) 시간에 삽입 또는 검색이 필요할 때 가장 먼저 선택되는 데이터 구조이기도 하다.
4. 스택
스택은 더 간단한 데이터 구조 중 하나로 마스터하기가 매우 쉽다. 스택 데이터 구조는 기본적으로 모든 실제 스택(상자 또는 플레이트 스택을 생각함)이며 LIFO(후입 선출) 방식으로 작동한다.
Stacks의 LIFO 속성은 마지막에 삽입한 요소가 먼저 액세스됨을 의미한다. 스택의 맨 위 요소를 팝하지 않고는 스택의 맨 위 요소 아래에 있는 요소에 액세스할 수 없다.
스택에는 푸시와 팝의 두 가지 기본 작업이 있다. 푸시는 스택에 요소를 삽입하는 데 사용되며 팝은 스택에서 최상위 요소를 제거하는 데 사용된다.
또한 유용한 응용 프로그램이 많이 있으므로 면접관이 스택과 관련된 질
5. 대기열
대기열은 스택과 유사하지만 FIFO(선입 선출) 방식으로 작동하므로 이전에 삽입한 요소에 액세스할 수 있으며, 대기열 데이터 구조는 사람들이 도착 순서에 따라 배치되는 실제 대기열로 시각화할 수 있다.
큐의 삽입 작업을 인큐(enqueue)라고 하고 큐의 시작 부분에서 요소를 삭제/제거하는 것을 디큐잉(dequeuing)이라고 한다.
우선 순위 대기열은 CPU 스케줄링과 같은 많은 중요한 응용 프로그램에서 대기열의 통합 응용 프로그램이다. 우선 순위 대기열에서 요소는 도착 순서가 아닌 우선 순위에 따라 정렬된다.
6. 힙
힙은 노드가 오름차순 또는 내림차순으로 배열되는 일종의 이진 트리다. 민 힙(Min Heap)에서 부모의 키 값은 자식의 키보다 작거나 같으며 루트 노드는 전체 힙의 최소값을 포함한다.
마찬가지로 맥스 힙(Max Heap)의 루트 노드에는 힙의 최대 키 값이 포함되며, 힙 전체에서 최소/최대 힙 속성을 유지해야 한다.
힙은 매우 효율적인 특성으로 인해 많은 응용 프로그램이 있다. 주로 우선 순위 대기열은 종종 힙을 통해 구현되며, 힙 정렬 알고리즘의 핵심 구성 요소다.
[저작권자ⓒ CWN(CHANGE WITH NEWS). 무단전재-재배포 금지]
