자료구조란 프로그램에서 사용하기 위한 자료를 기억장치의 공간내에 저장하는 방법과 저장된 그룹 내에 존재하는 자료 간의 관계, 처리 방법 등을 연구 분석하는것.
● 자료의 표현과 그것과 관련된 연산
● 일련의 자료들을 조직하고 구조화
● 어떠한 자료 구조에서도 필요한 모든 연산들을 처리하는 것이 가능
● 자료 구조에 따라 프로그램 실행시간이 달라짐(시간복잡도, 공간복잡도)
자료구조는 정렬, 검색, 파일 편성, 인덱스등으로 이용할 수 있다.
1. 선형구조 : 리스트
리스트 - 선형 리스트(Linear List)
배열처럼 연속되는 기억장소에 저장되는 리스트이다.
가장 간단하고 접근 속도가 빠르며 기억장소를 연속으로 배정받기에 밀도가 1로서 이용 효율이 제일 좋다.
자료의 개수가 n개일때, 삽입시 평균 이동횟수 : n + 1/2, 삭제시 평균 이동횟수 : n -1/2
삽입, 삭제시 자료의 이동이 필요해 작업이 번거로운 단점이 있음.
리스트 - 연결 리스트(Linked List)
자료들을 반드시 연속적으로 배열시키진 않고 임의의 기억공간에 저장하되 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결 시킨다.
노드의 삽입, 삭제 작업이 용이하지만 자료의 이동이 필요해 작업이 번거로움.
단순 연결 리스트, 단순 환상 연결 리스트, 이중 연결 리스트 등의 종류가 있다.
스택(Stack)
리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어진다.
가장 나중에 삽입된 자료가 가장 먼저 삭제되는 후입선출법을 따른다( LIFO : Last In First Out ).
큐(Queue)
선형 리스트의 한쪽에서는 삽입, 반대쪽에서는 삭제 작업이 이루어지도록 구성한 자료구조이다.
가장 먼저 삽입된 자료가 가장 먼저 삭제되는 선입선출법을 따른다( FIFO : First In First Out ).
데크(Deque)
삽입과 삭제가 리스트의 양쪽 끝에서 모두 발생할 수 있는 자료 구조이다.
스택과 큐의 장점만 따서 구성한 것.
2. 비선형구조
트리(Tree)
데이터 요소들을 단순한 나열이 아닌 부모 - 자식 관계의 계층적 구조로 나타낸다.
트리는 그래프의 한 종류이며 사이클이 없다.
• node : 트리를 구성하고 있는 각 요소
• edge(간선) : 트리를 구성하기 위해 노드와 노드를 연결하는 선
• Root node : 최상위 계층에 존재하는 노드
• depth : 트리의 특정 깊이를 가지는 노드의 집합
• siblings : 같은 부모를 가지고 있는 노드의 집합
• Terminal Node ( = leaf Node, 단말 노드) : 하위에 다른 노드가 연결되어 있지 않은 노드
• Internal Node (내부노드, 비단말 노드) : 단말 노드를 제외한 모든 노드로 루트 노드를 포함
그래프(Graph)
그래프는 vertex(Node, 정점)과 vertex와 vertex를 연결하는 edge(간선)으로 구성된다.
방향성, 무방향성 그래프로 나눌 수 있으며 Tree의 노드가 하나의 In-degree만 가지는 반면, 그래프이 vertex는 하나이상의 In-degree를 가질 수 있다.
