자료구조

자료구조란?

자료를 논리적으로 정의된 규칙에 의해 효율적으로 관리하는 방법

자료구조의 종류

자료구조의 종류는 자료형의 따라서 분류하는 단순 구조, 선형 구조, 비선형 구조, 파일 구조가 있다.

단순 구조

단순 구조 자료구조는 정수, 실수, 문자, 문자열과 같은 컴퓨터가 기본적으로 제공하는 자료형을 뜻한다.

1. 정수 (Integer)
   • 소수점이 없는 형태로 0, 1, 10, 100, -100과 같은 숫자를 의미한다.
2. 실수 (Float)
   • 소수점이 있는 형태다.
3. 문자 (Character)
   • 한 글자를 의미하며, 일반적으로 프로그래밍 언어에서는 작은 따옴표를 통해서 표기한다.
4. 문자열 (String)
   • 문자 여러개를 묶은 것으로 일반적으로 프로그래밍 언어에서는 큰 따옴표를 통해 표기한다.

선형 구조

데이터를 순차적으로 한 줄로 표기한 자료구조로 선형리스트, 연결리스트, 스택, 큐가 있다.

1. 선형리스트 (Linear List)
   • 데이터를 논리적인 순서대로 메모리에 연속하여 저장하는 구현 방식
   • 주로 고정된 크기를 가진 배열을 통해서 구현
   • 때문에 각 원소의 순서가 정해져있고, 각 원소의 인덱스를 사용할 수 있다.
   • 이로 인하여 데이터 검색에 효율적이지만 삽입과 삭제 시 크기를 더 할당하거나, 모든 데이터를 이동해줘야하기 때문에 비효율적이다.
2. 연결리스트 (Linked List)
   • 연결리스트는 노드를 통해 연결하는 리스트이다.
   • 선형리스트와 다르게 고정이 아니라 가변적인 크기의 리스트를 가진다.
   • 따라서 데이터를 삽입, 삭제 시 크기 할당이나 데이터를 이동할 필요 없이 노드를 추가하거나 제거할 수 있다.
   • 하지만 검색에 대해서는 선형리스트와 다르게 원하는 데이터를 한번에 찾아낼 수 없고, 리스트를 전부 탐색해야한다.
   • 주로 데어터 삽입, 제거가 많이 발생하는 프로그램이면 연결리스트가 유리
   • 탐색이 주가 되면 선형리스트를 사용하는 것이 유리
3. 스택 (Stack)
   • 스택은 한쪽으로만 데이터를 넣고 뺄 수 있는 구조의 자료구조다.
   • 마지먹에 넣은 데이터가 가장 먼저 나가는 LIFO (Last-In First-Out) 구조를 가진다.
   • 주로 연결리스트를 통해 구현하고, 웹브라우저의 페이지 뒤로가기, undo, 문자열 뒤집기와 같이 사용
     
4. 큐 (Queue)

• 큐는 양쪽으로 데이터를 넣고 뺄 수 있는 자료구조다.
• 큐의 종류에 따라 차이점이 있지만, 기본적인 큐는 한쪽으로 데이터를 넣고, 다른 한쪽으로는 데이터를 뺄 수 있다.
• 따라서 가장 먼저 들어온 데이터가 가장 먼저 나오는 FIFO (First-In First-Out) 구조를 가진다.
• 큐는 일반적으로 연결리스트를 통해 구현되고, 선입선출을 필요로 하는 대기열, 프로세스 관리, 너비 우선 탐색에 사용된다.

비선형 구조

비선형 구조는 하나의 자료 뒤에 여러개의 자료가 존재할 수 있는 자료구조다. 트리와 그래프가 대표적인 비선형 구조의 자료구조다.

1. 트리 (Tree)
   • 트리는 노드가 나무 가지처럼 연결되어 있는 비선형 구조다.
   • 마치 나무를 뒤집어 놓은 모습과 유사하다.
   • 트리 내 또 다른 하위 트리가 있고, 그 안에 또 다른 하위 트리가 있는 재귀적인 구조를 가진다.
   • 컴퓨터 디렉토리 구조가 트리 구조다.
     
2. 그래프 (Graph)
   • 그래프는 노드와 노드를 연결하는 간선을 모아놓은 자료구조다.
   • 트리와 많이 비교가 되는데 트리 역시 그래프 형태지만 그래프는 방향이 있거나 없을 수 있다.
   • 또한 루트 노드라는 개념이 없고, 사이클이 가능한 형태로 구성되어 있다.
     

파일 자료구조

파일이 디스크에 저장되는 방식에 따라 순차 파일과, 직접 파일, 색인 순차 파일로 구분된다.

1. **순차 파일 (Sequential File)
   • 파일 내용을 논리적인 처리 순서에 따라 연속해서 저장하는 것
   • 구조가 간단하여 공간 효율성은 높지만 다른 내용을 추가하거나 제거할 때
   • 파일 내용을 재구성 해야하기 때문에 시간이 오래걸린다.
2. 직접 파일 (Direct File)
   • 파일의 내용을 임의의 물리적인 위치에 기록하는 방식이다.
   • 내용을 저장하는 위치는 해서 함수라는 계산식으로 결정된다.
3. **색인 순차 파일 (Indexed Sequential File)
   • 순차 파일과 직접 파일이 결합된 형태로, 데이터를 키 값 순서로 정렬시켜 기록
   • 키 항목만 모은 색인을 구성하여 편셩하는 방식