자료구조 정리

자료구조 종류

• 선형구조: 데이터가 일렬로 연결되어있는 구조
• 비선형구조: 자료의 구성이 일렬이 아닌 특정한 형태 구조

배열(Array)

• 한가지 데이터 타입의 데이터를 순차적으로 저장 및 정렬하는 자료구조
• 각 데이터마다 index를 부여하여 데이터 검색에 용이(장점)
• 배열은 크기가 고정적(단점)
• 데이터가 삭제되면 배열 전체의 데이터를 재정렬(단점)

큐(Queue)

• FIFO(First In, First Out)방식으로 데이터를 저장 및 정렬하는 자료구조
• FIFO방식으로 인해 데이터 삭제시, 재정렬이 필요없다

스택(Stack)

• 데이터를 쌓는 방식(LIFO)으로 데이터를 정장 및 정렬하는 자료구조
• LIFO방식으로 인해, 구현이 단순하여 쉽다
• LIFO방식으로 인해, 데이터의 저장 및 검색 속도가 빠르다

연결리스트(Linked List)

• 배열의 단점이 보완된 형태의 자료구조로, 크기가 가변적인 배열
• 노드(Node) : 데이터의 저장단위로, 데이터 값과 포인터(주소값)를 한 쌍으로 구성
• 포인터(Pointer): 각 노드의 위치정보(주소값)을 의미한다
• 포인터를 위한 저장공간이 따로 필요(단점)
• 포인터를 이용해 연결노드를 찾는 시간이 필요하다(접근속도가 느리다)
• 데이터가 삭제하면 삭제된 데이터의 이전과 다음 데이터의 연결을 재구성해야한다(단점)

해시테이블(Hash Table)

• Key와 Value를 한 쌍으로 저장하는 자료구조
• Key를 이용하여 Value를 빠르게 검색할 수 있다(장점)
• 특정 데이터의 중복을 쉽게 확인할 수 있다(장점)
• 저장공간을 많이 필요로 하다(단점)

트리(Tree)

• 노드와 브랜치를 이용하여 구성한 자료구조로, 사이클이 없는 것이 특징
• 트리를 기반한 이진트리를 이용하여 탐색 알고리즘 구현에 자주 사용

• 루트 노드(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.
• 단말 노드(leaf node): 자식이 없는 노드, ‘말단 노드’ 또는 ‘잎 노드’라고도 부른다.
• 내부(internal) 노드: 단말 노드가 아닌 노드
• 간선(edge): 노드를 연결하는 선 (link, branch 라고도 부름)
• 형제(sibling): 같은 부모를 가지는 노드
• 노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수
• 노드의 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
• 노드의 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합
• 노드의 차수(degree): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
• 트리의 차수(degree of tree): 트리의 최대 차수
• 트리의 높이(height): 루트 노드에서 가장 깊숙히 있는 노드의 깊이

힙(Heap)

• 트리구조를 기반으로한 자료구조로, 데이터에서 최대값과 최솟값을 빠르게 찾기 위해 고안된 완전이진트리다
• 완전이진트리란, 데이터가 트리에 삽입될 때 왼쪽 노드를 우선 채우는 규칙을 가지고 있다
• 힙의 루트노드에 최대값이 위하면 최대힙(MAX HEAP), 최소값이 위치하면 최소힙(MIN HEAP 분류)