[자료구조] 자료구조 종류

😉각 자료구조의 제목을 누르시면 좀 더 자세한 내용을 다룬 포스팅으로 넘어갑니다! (아직 미완인 것도 있음!)😉

1. Array(배열)

https://bnzn2426.tistory.com/115

• 배열(Array : 정렬)은 동일한 타입의 데이터들을 저장(배열이 "int"타입인 경우 정수 요소만 저장 가능)하며, 고정된 크기를 가지고 있다.
• 인덱싱이 되어 있어 인덱스 번호로 데이터에 접근할 수 있다. (인덱스를 지정하여 접근하기 때문에 모든 요소에 빠르게 접근 가능하다.)

 

📌 배열의 용도

- 특정 요소를 빠르게 읽어야 할 때

- 다차원 데이터를 다룰 때

 

2. Linked List(연결 리스트)

https://code-lab1.tistory.com/2

• 연결 리스트(Linked List : 연결 목록)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다.
• ex) 첫 번째 노드의 포인터로 두 번째 데이터를 찾을 수 있다. 두 번째 노드의 포인터로는 세 번째 데이터를 찾을 수 있다.
• 배열의 크기를 미리 선언해야 하는 배열 리스트와 달리 연결 리스트는 데이터의 숫자만큼만 메모리를 사용하면 되니 메모리 낭비가 적다.

 

📌 연결 리스트의 용도

- Alt + Tab을 사용하여 프로그램 간 전환

- 갤러리

 

3. Stack(스택)

https://luv-n-interest.tistory.com/161

• 스택(Stack : 쌓다)은 그림에서 사과를 쌓을 때 위로 쌓는 것만 가능하듯이 한 방향으로만 입력할 수 있으며 구조 중간에 값을 끼어 넣어 저장할 수 없다. 즉, 같은 크기의 자료를 정해진 한 방향으로만 입력, 저장, 삭제가 가능하다.
• 맨 아래 있는 사과를 꺼내기 위해서 가장 위에 있는 사과부터 꺼내야 하는 것 처럼 후입선출(Last In First Out, LIFO) 구조로 가장 마지막에 들어온 데이터가 가장 먼저 리턴, 삭제된다는 뜻이다.

 

📌 스택의 용도

- 브라우저의 뒤로가기

- 실행 취소

- 후위 표기법 계산

 

4. Queue(큐)

https://luv-n-interest.tistory.com/161

• 큐(Queue : 대기줄)는 그림에서 놀이공원 티켓을 사는 줄 같이 양 방향에서 입력과 출력이 진행되는 자료구조를 뜻한다.
• 먼저 온 사람이 먼저 티켓을 사고 나가는 것 처럼 선입선출(First In First Out, FIFO) 구조로 가장 먼저 들어온 데이터가 가장 먼저 리턴, 출력된다는 뜻이다.

 

📌 큐의 용도

- 프로세스 관리

- 윈도우 시스템 메세지 처리기

- 캐시

- 너비 우선 탐색

 

5. Tree(트리)

• 트리(Tree : 나무)는 노드들이 나무 가지처럼 계층적으로 연결된 비선형 자료구조이다.
• 최상위 노드(루트)가 있고 최상위 노드 아래에 다른 하위 노드가 있고 그 하위 노드 안에는 또 다른 하위 노드가 있는 부모(parent)와 자식(child) 형태이다.
• ex) C:\Program Files\League of Legends → 최상위 노드(C:\)아래 하위 노드(Program Files) 아래 또 다른 하위 노드(League of Legends)

 

📌 트리의 용도

- 컴퓨터의 디렉터리 구조

- 조직도

 

6. Heap(힙)

https://tildacoderecorder.tistory.com/106

• 힙(Heap : 더미)은 완전 이진 트리의 형태로 만들어진 자료구조이다.
• 최대 힙(max heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
• 최소 힙(min heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

 

📌 힙의 용도

- 최댓값 혹은 최솟값을 빠르게 찾아내기 위해 사용 (우선순위 큐, 힙 정렬)

 

7. Hash Table(해시 테이블)

https://bnzn2426.tistory.com/115

• 해시함수를 사용하여 변환한 값을 색인(index)으로 삼아 키(key)와 데이터(value)를 저장하는 자료구조
• 데이터의 크기에 관계없이 삽입 및 검색에 매우 효율적

 

📌 해시 테이블 용도

- 데이터베이스 인덱스 구현

- 사용자 로그인 인증

 

8. Graph(그래프)

https://bnzn2426.tistory.com/115

• 그래프는 정점(Vertex)과 간선(edge)으로 이루어진 자료구조이다. 정확히는 정점간의 관계를 표현하는 조직도이다.
• 그래프는 정점마다 간선이 없을수도 있고 있을수도 있으며 루트 노드, 부모와 자식이라는 개념이 존재하지 않는 부분에서 트리와 다르다.
• 정점(Vertex) : 노드(node)라고도 하며 정점에는 데이터가 저장된다. (0, 1, 2, 3)
• 간선(edge) : 링크(arcs)라고도 하며 노드간의 관계를 나타낸다.

 

📌 그래프의 용도

- GPS에서 위치와 경로를 나타내는 데 사용

- 검색 엔진에 의해 웹 페이지 및 링크를 나타내는 데 사용

 

References

📄 https://luv-n-interest.tistory.com/161

📄 https://ontheway.tistory.com/23

📄 https://bnzn2426.tistory.com/115

📄 https://code-lab1.tistory.com/2

📄 https://bnzn2426.tistory.com/115

📄 https://bite-sized-learning.tistory.com/239

📄 https://coding-factory.tistory.com/610

📄 https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html