본문 바로가기
6. 리스트(List) & 스택(Stack) & 큐(Queue) & 힙(Heap) & 트리(Tree) 종합 정리 6. 스택(Stack) & 큐(Queue) & 힙(Heap) & 트리(Tree) 종합 정리 6.1 리스트(List) - 데이터를 순차적으로 저장하며 선형 구조를 띈다 또한 하나의 데이터와 다음 노드를 가르키는 주소로 구성된다. - 리스트의 종류 ㆍ링크드 리스트(Linked List) : 노드의 연결로 이루어져 있다. ㆍ이중연결 리스트(Doubly Linked List) : 양방향으로 이루어져있다. ㆍ환영연결 리스트(Circular Linked List) : 머리가 꼬리를 물고 있다. 6.2 스택(Stack) - 모든 원소들의 삽입(Insert)와 삭제(Delete)가 리스트의 한쪽 끝에서만 수행되는 제한 조건을 가진 선형 자료구조 - 가장 최근에 삽입돈 원소를 스택의 Top로 한 원소를 제거하는것 (FI.. 더보기
5. 힙(Heap) 힙(Heap) : 특별한 트리를 기본으로 하는 자료구조- 힙의 자료구조는 최대 힙(Max Heap)과 최소 힙(Min Heap)으로 나뉜다.- 힙은 최대값 또는 최소값을 짧은 시간내에 찾기 위해서 만덜어진 자료 구조 ㆍ최대 힙이란 부모 노드의 값이 항상 자식 노드의 값보다 크다. ㆍ최소 힙이란 부모의 노드값이 항상 자식의 노드값보다 작다. 1. 최소 힙(Min Heap)에서의 삽입과정 - 최소 힙의 삽입과정을 보면 만약 15라는 값을 추가 한다면 15는 부모 노드와 비교를 한 후 부모노드보다 더 작을 경우 15와 51을 서로 교환한다. 더보기
4. 트리(Tree) 트리(Tree) : 나무 모양의 계층적 구조- 트리의 자료구조는 계층적인 구조를 띄고 있다. 나무의 뿌리와 가지와 잎이 있듯이 트리의 구조에서도 나무와 뿌리 그리고 가지가 존재한다.- 뿌리 노드는 루트 노드라고 하며 가지와 잎은 그대로 노드라고 부릅니다.- 트르의 경우 주 목적이 탐색이며, 의사 결정, 파일 시스템, 검색 엔진, DBMS, 라우터 알고리즘, 계층적 데이터를 다루는 등 매우 다양한 곳에서 응용된다.- 전에 배운 리스트, 큐, 스택은 모두선형(---선)구조를 띄고 있다면 이 트리는 계층 구조(비선형)를 띈다.- 트리 구조의 경우 A의 루트 노드에서 나머지 가지?형태로 구조가 뻗어나가는 모양이다. - 트리 구조의 경우는 차수(Degree), 높이(Height), 레벨(Level)이라는 형태가 .. 더보기

티스토리툴바