자료구조란 ?
데이터 값의 모임, 각 원소들이 논리적으로 정의된 규칙에 의해 나열되며, 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분해 표현한 것.
책장과 데이터
- 1번의 경우 책장의 모든 공간을 사용할 수 있지만 처음에 책을 꽂거나 이후에 책을 추가할 때 수고스러움이 생긴다.
- 2번의 경우 분야별로 책을 찾을 순 있지만 공간의 비효율이 생긴다.
- 3번의 경우 2번보다는 더 효율적으로 공간을 사용할 수 있지만, IT와 소설 분류가 밑으로 넘어가버려 책을 꽂거나 찾을 때 헷갈림이 생길 수 있다. 또한
자료구조 분류
1. Arrays (배열)
- 자료형을 원소로 취급해 나열한 것이다.
- 기본적으로 배열의 크기는 정해져있다.
- 동일한 타입의 데이터들을 저장한다.
- 인덱싱이 되어있어 인덱스를 통해 빠르게 데이터에 접근할 수 있다.
- 갯수가 정해진 자료를 다룰 때 유용하다.
- 배열 목록, 힙, 해시 테이블, 벡터 및 행렬과 같은 기타 데이터 구조를 구축하기 위한 빌딩 블록으로 사용한다.
- 삽입정렬, 빠른정렬, 버블정렬 및 병합 정렬과 같은 다양한 정렬 알고리즘에 사용된다.
2. Linked-Lists (리스트)
- 하나의 자료가 다른 자료를 가리키며 자료를 축적해나가는 구조이다.
- 갯수가 정해져 있지 않은 자료들을 다룰 때 유용하다.
- 따라서 배열에 비해 빈 공간을 낭비하지 않는다.
- 인덱스가 없으므로 접근시 배열과 달리 한 번에 찾아가기 어렵다.
-
각 요소는 Node이고, Node안에는 key와 다음 노드를 가리키는 포인터인 next가 포함되어있다.
-
첫 번째 요소는 Head, 마지막 요소는 Tail이다.
-
Alt + Tab을 이용하여 프로그램간 전환 시 사용
-
갤러리
3. Stack (선형 자료구조)
- 순서가 보존되는 선형 데이터 구조이다.
- 가장 마지막에 넣은 요소부터 처리하는 LIFO(Last In First Out)
- 실행취소
- 수학적 표현식을 구문 분석하고 평가
- 재귀 프로그래밍에서 함수 호출을 구현
4. Queue (선형 자료구조)
- 가장 먼저 입력된 요소를 처리하는 FIFO(First In First Out)
- 멀티 스레딩에서 스레드를 관리시 사용
- 대기열 시스템
5. Hash Table
-
해시 함수를 사용하여 변환한 값을 색인(index)로 삼아 키(key)와 데이터(value)를 저장하는 자료구조
-
데이터의 크기에 관계 없이 삽입 및 검색에 매우 효율적이다.
-
데이터베이스 인덱스 구현
-
사용자 로그인 인증
-
‘set’ 데이터 구조 구현
6. Graph (비선형 자료구조)
7. Tree (비선형 자료구조)
8. Heap
