array
자료형이 같은 자료를 나열하여 메모리에 연속으로 저장하여 만든 자료 그룹
index
배열 요소를 구별하기 위한 번호
자료형 배열이름[크기][크기][크기]
pointer
변수의 주소 값이 저장된 변수, (32비트 4바이트), (64비트 8바이트)
순차 자료구조
- 메모리의 저장 시작 위치부터 빈 자리 없이 자료를 순서대로 연속하여 저장한다.
- 삽입, 삭제 연산을 해도 빈자리 없이 순서대로 연속하여 저장된다.
linear list, ordered list
- 메모리에 저장하는 구현 방식에 따라 순차 방식으로 구현하는 선형 순차 리스트와 연결 방식으로 구현하는 linear linked list로 나뉜다.
- linear sequential list는 array를 이용해 구현한다.
- Row Major Order, Column Major Order
- 순차 자료구조는 물리적 주소의 순서로 간단히 구성할 수 있고, 인덱스를 사용해 주소를 계산할 수 있어 특정원소를 쉽게 액세스할 수 있다.
- 원소를 삽입하거나 삭제할 때 물리적으로 원소들을 움직여 연속 저장 순서를 유지해야 하므로 이동 연산에 대하여 오버헤드가 발생한다.
Linked Data Structure, none-sequential data structure
- 포인터를 이용해 구현
- 각 원소에 저장되어 있는 다음 원소의 주소에 의해 순서가 연결되는 구현 방식
- 물리적인 순서를 맞추기 위한 오버헤드가 발생하지 않는다.
- 노드 단위로 메모리가 할당되며, 저장 위치의 순서와 상관 없이 노드의 링크 필드에 다음 자료의 주소를 저장한다.
singly linked list
- 노드의 링크 필드가 하나이며, 링크 필드는 다음 노드와 연결되는 구조
- linear linked list, singly linked linear list
- 삽입이나 삭제할 경우 링크 필드를 잘 수정해야한다.
circular linked list
마지막 노드가 NULL이 아닌 첫 노드를 가리킨다.
Doubly Linked list
왼쪽 오른쪽 둘을 가리키는 포인터 존재, 양방향으로 순회 가능
stack
- top으로 정한 곳으로만 접근하도록 제한되어 있다.
- top에서 삽입과 삭제가 일어나며 top은 스택의 가장 위에 있는데 데이터 위치이다.
system stack
- 함수의 호출과 복귀 순서를 관리할 때 사용하는 스택.
- 함수나 서브프로그램 호출이 발생하면 현재 작업 중인 지역변수, 매개변수, 완료 후 복귀할 주소 등의 정보를 stack frame에 저장하여 system stack에 삽입한다. 함수 실행이 끝나면 시스템 스택의 top원소를 pop하면서 프레임에 저장되어 있던 복귀 주소를 확인하고 복귀한다.
- 스택을 이용한 수식의 괄호 검사
- 스택을 이용한 표기법 변환
- prefix notation, infix notation, postfix notation
Queue
- FIFO
- front는 삭제 연산을 수행하고 rear는 삽입연산을 수행한다.
sequential queue
- 1차원 배열을 이용, 포화상태일 때 삽입연산을 수행하지 못함
- 잘못된 포화 상태를 배열의 비어 있는 앞부분으로 이동하여 해결할 수 있지만 오버헤드가 커서 효율성이 떨어진다.
Circular Queue
- 1차원 배열을 이용한다. (다른 방식으로 해도 되긴 함)
- mod n 을 이용해서 접근
Linked Queue
- 순차 자료구조를 이용하면 큐의 길이를 자유롭게 조절할 수 있고 빈 공간 때문에 생기는 메모리 낭비를 막을 수 있다.
Deque
- double ended queue: 큐의 양쪽 끝에서 삽입과 삭제가 가능하다.
- 운영체제의 작업큐(?)
rust로 뭐할까