자료구조 기초

대량의 데이터를 효과적으로 관리하는 매커니즘 = 자료구조

배열, 리스트, 스택, 큐(대기 행렬), 트리(나무 구조)

1. 배열
- 데이터를 빈틈없이 나열한 자료구조
- 일직선 상에 빈틈없이 데이터를 나열한 1차원 배열
- 테이블처럼 가로세로 빈틈없이 데이터를 나열한 2차원 배열
- 직육면체처럼 가로, 세로, 높이에 빈틈없이 데이터를 나열한 3차원 배열
- 유효한 데이터의 개수를 관리할 때 다른 변수를 사용

2. 리스트
- 데이터를 순서대로 나열한 자료구조
- 데이터들이 화살표로 서로 연결되어 있어 데이터들이 떨어진 장소에 위치할 수 있다.
- 데이터 위치에 구애 받지 않는다.
- 데이터들이 ‘포인터’로 연결되어 있다.
- 따라서 데이터의 위치에 관계없이 데이터의 순서를 관리할 수 있다.
- 유효한 데이터의 개수를 관리할 때 다음 데이터에 연결된 화살표의 여부로 데이터의 끝을 파악
-- 단방향 리스트
- 단방향 리스트의 요소는 ‘데이터+NEXT 포인터’로 이루어져있다.
- 한쪽 방향으로만 요소를 가리킴(다음)
- ‘데이터’는 그 요소에 저장된 정수, 실수, 문자열 등 리스트에서 관리하고자 하는 값
- ‘NEXT 포인터’에는 현재 요소에서 다음 요소가 어디에 있는지 위치 정보 저장되어 있다.
- 마지막 포인터에는 종료 정보가 저장되어 있다.
- 다음 요소를 가리키는 포인터는 ‘NEXT 포인터’라고 부른다.
- 1번째 요소를 가리키는 포인터는 ‘HEAD 포인터’라고 부른다. 
-- 양방향 리스트
- 양방향 리스트의 요소는 ‘데이터+NEXT 포인터+PREV 포인터’로 이루어져있다.
- 2개의 방향으로 요소를 가리킴(이전, 다음)
- ‘데이터’는 그 요소에 저장된 정수, 실수, 문자열 등 리스트에서 관리하고자 하는 값
- ‘NEXT 포인터’에는 현재 요소에서 다음 요소가 어디에 있는지 위치 정보 저장되어 있다.
- ‘PREV 포인터’에는 현재 요소에서 이전 요소가 어디에 있는지 위치 정보 저장되어 있다.
- 1번째 요소를 가리키는 포인터와 마지막 포인터에는 종료 정보가 저장되어 있다.
- 다음 요소를 가리키는 포인터는 ‘NEXT 포인터’라고 부른다.
- 1번째 요소를 가리키는 포인터는 ‘HEAD 포인터’라고 부른다.
- 마지막 요소를 가리키는 포인터는 ‘TAIL 포인터’라고 부른다.

3. 스택
- 책상 위에 책을 쌓듯 데이터를 관리하는 자료구조
- 쌓여있는 가장 위의 데이터부터 꺼내서 사용
- 데이터 넣는 순서와 반대의 순서로 데이터를 꺼내서 사용
- 데이터를 넣는 작업 푸시(PUSH)
- 데이터를 꺼내는 작업 팝(POP)
- 마지막에 입력된 데이터가 먼저 출력되는 특징을 갖는 데이터 관리 방식을 
  LIFO(Last In, First Out) 또는 FILO(First In, Last Out)라고 부른다.

4. 큐(대기 행렬)
- 계산대에서 먼저 줄을 선 손님부터 차례대로 계산하듯, 데이터를 넣은 순서대로 꺼내서 사용하는 자료구조
- 중간에 끼어들거나 순서를 어길 수 없다. 
- 먼저 입력된 데이터가 먼저 처리되는 특징을 갖는 데이터 관리 방식을
  FIFO(Fast In, First Out) 또는 LILO(Last In, Last Out)라고 부른다.

5. 트리(나무 구조)
- 나뭇가지가 2개, 3개 가지를 뻗고, 갈라진 끝에서도 2개, 3개 나뉘어 퍼져가는 형태의 자료구조
-- 이진 트리(바이너리 트리)
- 데이터 X의 다음 요소로 2개의 데이터 L과 R이 존재한다.
- 이진 트리의 구성요소들은 노드라고 부른다.
- 데이터 X는 부모 요소, L과 R은 자식요소
- 이진 트리에서 자식 노드가 반드시 좌, 우 모두가 있을 필요는 없다. 왼쪽만 있거나, 오른쪽만 있어도 된다. 
- 부모 노드는 자식 노드를 2개 이상 가질 수 없다.
- 자식 노드는 부모 노드이기도 하다.
- 모든 노드의 시작점 = 부모 노드가 없는 노드 = 뿌리 또는 루트 노드라고 한다.
- 말단 노드 = 자식 노드가 없는 노드 = 잎 또는 리프라고 한다.
- 루트 노드에서 특정 노드에 도달하기까지의 경로의 길이는 깊이 또는 뎁스라고 한다.
-- 부모 노드의 값이 자식 노드의 값보다 항상 적은 이진 트리는 힙
- 힙 : 각 노드의 값이 다음 조건을 충족하도록 관리되는 이진 트리
- 조건 : 부모 노드의 값은 항상 하위 노드의 값보다 작다.
  또는 부모 노드의 값은 항상 하위 노드의 값보다 크다.
- 데이터 열 중에 ‘최소 값(최대 값)’은 루트 노드의 값
- 실제로 힙을 구현할 땐 일반적으로 배열을 사용. 루트를 1번째 요소로, 깊이가 작은 쪽에서 큰 쪽으로, 노드의 왼쪽에서 오른쪽으로 표현

해시 테이블
- 해시테이블은 배열과 리스트를 조합한 자료구조
- N개의 요소를 가진 루트 배열이라는 이름의 배열 + 루트 배열의 각 요소들이 가리키는 리스트
- 루트 배열의 각 요소들이 가리키는 리스트 중에서 어떤 리스트에 저장할지를 결정해야 하므로 루트 배열의 index number부터 구해야 한다. => index number 구할 때 사용하는 도구는 해시 함수
- 해시 함수는 관리할 데이터를 입력 받아서, 그 데이터를 해시 값(0~[n-1] 사이 값)으로 바꿔주는 함수
- 해시 값을 루트 배열의 index number로 삼으면, 데이터를 루트 배열의 몇 번째 요소가 가리키는 리스트에 저장해야 할지 결정할 수 있다.
- 같은 배열 요소에 그룹화된 데이터가 여러 개 나오는 상황이 발생(충돌) -> 루트 배열의 각 요소가 리스트를 가리키도록 만들면, 해시 값이 동일한 데이터들을 여러 개 관리할 수 있다.
- 데이터를 찾을 땐, 해시 값 먼저 구하고, 찾고자 하는 데이터가 속한 그룹을 찾아낸다.
- 가장 간단한 해시 함수는 저장할 데이터가 숫자일 경우 데이터를 해시 테이블의 요소 수로 나눈 나머지를 반환한다.

 

 

N번째 요소의 참조가 빠른 것은 배열
-> Index를 사용하기 때문에 빠르다.
N번째 요소의 참조가 느린 것은 리스트
-> 포인터가 가리키는 요소부터 차례대로 찾기 때문에 느리다.

데이터의 삽입, 삭제가 빠른 것은 리스트(포인터 조작)
-> 삽입 위치의 앞뒤 데이터를 연결하는 끈을 잘라 새로운 데이터에 연결시킨다.
-> 제거하고자 하는 데이터의 끈을 자른 후 앞뒤 데이터를 이어 붙인다.
데이터의 삽입, 삭제가 느린 것은 배열(데이터 이동이 많다.)
-> 모든 데이터를 앞으로 이동시키거나 뒤로 이동시켜야 한다.
-> 삭제된 데이터보다 뒤에 있는 데이터를 앞으로 이동시켜야 한다.

마지막 요소까지 이동하면 1번째 요소로 되돌아 오는 링 버퍼
-> 1차원 배열의 1번째 요소와 마지막 요소를 합쳐서 ‘배열 마지막 요소의 다음에도 요소가 존재한다.’고 만들어 버리는 자료구조 = 링 버퍼(마지막 요소 뒤에 1번째 요소가 있다.)
-> FIFO의 큐 구조를 구현할 때 유용