DATA CONSTRUCTOR
DEV ·여기서는 간략하게 비선형 구조, 선형 구조로 나누어 살펴본다.
추후에 더 자세한 정리가 이루어지면 링크를 걸어놓을 예정이다.
1. 비선형 구조
하나의 데이터 안에 여러 개의 자료가 존재할 수 있는 것을 말한다.
A. 트리
정점과 선분을 이용해 사이클을 이루지 않도록 구성한 그래프 형태로, 방향성이 존재해 부모 ∙ 자식 계층 구조가 명확하다.
B. 그래프
정점, 선분을 이용해 사이클을 이루도록 구성한 것으로, 순환이 가능하다.
2. 선형 구조
자료를 구성하는 데이터를 순차적으로 나열한 형태를 말한다.
종류로는 배열(선형 리스트), 연결 리스트, 스택, 큐, 테크 등이 있다.
포인터 등을 사용해 자료를 연결하면 그 결과가 일직선 상에 표시되거나 하나의 원상에 표시된다.
A. 배열 (Array)
인덱스를 갖고 있으며, 순차적으로 데이터가 삽입, 삭제될 수 있는 구조이다.
데이터의 순차적 삽입, 삭제 시 가장 효과적이다.
인덱스를 사용해 검색이 빠르다는 장점이 있지만, 중간 삽입 ∙ 삭제가 어렵다는 단점이 있다.
B. 연결리스트 (Linked List)
자료 항목 순서에 따라 노드의 포인터 부분을 이용해 서로 연결한 구조이다.
노드의 삽입, 삭제 작업이 용이하며, 기억 공간이 연속적으로 놓이지 않아도 저장이 가능하다.
중간 삽입 ∙ 삭제가 빠르고 용이하다는 장점이 있지만, 접근 속도가 느리며 중간 노드 연결이 끊어질 시 다음 노드를 찾기 어렵다는 단점이 있다.
C. 스택 (Stack)
리스트의 한 쪽 끝으로만 자료 삽입, 삭제 작업이 이루어지는 구조이다.
Last In, First Out / 인터럽트가 발생하여 복귀주소를 저장할 때 사용한다.
스택의 용도로 7가지가 있다.
- 부 프로그램 호출 시 복귀주소 저장
- 함수 호출 순서 제어
- 인터럽트가 발생해 복귀 주소 저장 시
- 후위 표기법으로 표현된 산술식 연산
- 0 주소 지정방식 명령어 자료 저장소
- 재귀 프로그램 순서 제어
- 컴파일러를 이용한 언어 번역
D. 큐 (Queue)
한 쪽에서는 삽입, 다른 쪽에서는 삭제가 이루어지는 구조이다.
시작과 끝을 표시하는 두 개의 포인터가 존재한다.
E. 데크 (DEQ : Double Ended Queue)
스택, 큐의 장점만을 갖고 만든 것으로, 삽입과 삭제가 리스트 양쪽에서 모두 발생하는 구조이다.
입력이 한쪽, 출력이 양쪽에서 일어나는 입력제한과 입력이 양쪽, 출력이 한쪽에서 일어나는 출력제한이 있다.