자료 구조에 대하여

오늘은 자료구조에 종류와 정의에 대해 공부해볼 거예요 

 

자료 구조를 선형 구조와 비선형 구조로 구분할 수 있도록 확실하게 공부해두는 게 중요해요!

 

일단 자료구조의 정의에 대하여 알아봅시다. 

효율적인 프로그램을 작성할때 가장 우선적으로 고려해야 할 사항은 무엇일까요? 

저장 공간의 효율성과 실행시간의 신속성입니다.  자료구조는 프로그램에서 사용하기 위한 자료를 기억장치의 공간 안에 저장하는 방법과 저장된 그룹 내의 존재하는 자료 간의 관계, 처리 방법 등을 연구하고 분석하는 것을 말합니다. 

 

자료구조의 특징에 대해 알아보면

• 자료 구조는 자료의 표현과 그것과 관련된 연산을 뜻해요
• 자료 구조는 일련의 자료를 구조화하고 조직화합니다. 
• 어떠한 자료 구조에서도 필요한 모든 연산을 처리 가능 하답니다. 
• 자료 구조에 따라서 프로그램 실행시간이 달라지기도 해요.

자료구조의 분류는 크게 선형 구조와 비선형 구조로 나뉩니다. 

 

선형 구조의 종류

• 배열
• 선형 리스트( 연속리스트, 연결 리스트)
• 스택
• 큐
• 데크

비선형 구조의 종류

• 트리
• 그래프

그럼 이제부터 자료구조의 각각의 종류의 특성에 대해 알아봅시다. 

 

배열 

배열은 동일한 자료형의 데이터들이 같은 크기로 나열되어 순서를 갖고 있는 집합니다. 

• 배열은 정적인 자료 구조로 기억 장소의 추가가 어렵고, 데이터 삭제 시 데이터가 저장되어 있던 기억 장소는 빈 공간으로 남아 있어 메모리의 낭비가 발생한다는 단점이 있습니다. 
• 배열은 첨자를 이용하여 데이터에 접근합니다. 
• 반복적인 데이터 작업을 할때 적합한 구조입니다. 
• 배열은 데이터마다 동일한 이름의 변수를 사용하여 처리할 때 간편하다는 장점이 있습니다. 
• 배열은 사용한 첨자의 개수에 따라 n차원 배열이라고 부르기도 합니다. 

배열에서 가장 중요한건 첨자입니다. 문제 푸실 때 첨자가 들어간다고 하면 무조건 배열을 찍으시면 됩니다. 

 

선형 리스트

선형리스트는 일정한 순서에 의해 나열된 자료 구조로 크게 배열을 이용하는 연속 리스트와 포인터를 이용하는 연결 리스트로 나뉩니다. 

 

연속 리스트

• 배열과 같이 연속되는 기억 장소에 저장되는 자료구조입니다. 
• 연속 리스트는 기억 장소를 연속적으로 배정받기 때문에 기억 장소 이용 효율은 밀도가 1로서 가장 좋습니다. 
• 연속 리스트는 중간에 데이터를 삽입하기 위해서는 연속된 빈 공간이 있어야 하며, 삽입, 삭제 시 자료의 이동이 필요하다는 단점을 가지고 있어요.

연결 리스트 

• 연결 리스트는 자료들을 반드시 연속적으로 배열시키지는 않고 임의의 기억공간에 기억시키되, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료 구입니다. 
• 연결 리스트는 노드의 삽입 또는 삭제 작업 시 유리하다는 장점이 있습니다. 
• 연결 리스트는 연결을 위한 링크 부분이 필요하기 때문에 순차 리스트에 비해 기억 공간의 효율이 좋지는 않습니다. 
• 연결을 위한 포인터 찾는 시간이 필요하기 때문에 속도가 느립니다. 
• 연결 리스트는 중간 노드가 끊어질 시 그다음 노드를 찾기 힘듭니다. 

스택 

스택은 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료 구조이다. 

• 스택은 가장 나중에 삽입된 데이터가 가장 먼저 삭제되는 Last In First Out 방식 LIFO방식으로 데이터를 처리합니다. 
• 스택의 모든 기억 공간이 꽉 채워져 있는 상태에서 데이터가 삽입될 시 오버 플로우가 발생하며, 더 이상 삭제할 데이터가 없는 상태에서 데이터를 삭제하면 언더 플로가 발생할 수 있습니다. 
• TOP : 스택으로 할당된 기억 공간에 가장 마지막으로 삽입된 자료가 기억된 위치를 가리키는 요소
• Bottom : 스택의 가장 밑바닥이다. 

큐 (Queue)

큐는 리스트의 한쪽에서는 삽입 작업이 이루어지고 다른 한쪽에서는 삭제 작업이 이루어지도록 구성한 자료구조를 말합니다. 

• 큐는 가장 먼저 삽입된 자료가 가장 먼저 삭제되는 선입 선출 FIFO ( First In First Out) 방식을 사용합니다. 
• 시작과 끝을 표시하는 두 개의 포인터가 존재합니다. 
• 프런트 포인터 : 가장 먼저 삽입된 자료의 기억 공간을 가리키는 포인터로, 삭제 작업을 할 때 사용됨
• 리어 포인 턴 : 가장 마지막에 삽입된 자료가 위치한 기억공간을 가리키는 포인터로, 삽입 작업을 할 때 사용됨
• 큐는 운영체제의 작업 스케줄링에 사용된다. 

트리 

트리는 정점(Node)과 선분(Branch, 가지)을 이용하여 사이클을 이루지 않도록 구성한 그래프(Graph)의 특수한 형태입니다. 

• 트리는 하나의 기억 공간을 노드라고 하며, 노드와 노드를 연결하는 선을 링크(Link)라고 합니다. 
• 트리는 가족의 계보, 조직도를 표현하기 적당합니다.