개인 공부를 위해 작성했습니다.

자료구조(data structure)

자료구조: 대량 데이터의 효율적인 유지 관리 방법

다양한 종류의 자료구조들

알고리즘 작성에 사용되는 자료구조에는 다양한 종류가 있지만 그 중 대표적인 5개를 알아보자.

1. 배열

데이터를 빈틈없이 나열한 자료구조.

• 데이터의 순서가 고정되어 있다
• 배열의 종류
  • 1차원 배열: 일직선 상에 데이터를 나열
  • 2차원 배열: 사각형처럼 가로세로 빈틈없이 데이터를 나열
  • 3차원 배열: 직육면체처럼 가로, 세로, 높이에 데이터를 나열

2. 리스트(linked list)

데이터를 순서대로 나열한 자료구조.

• 배열과 같이 차례대로 나열한 데이터를 관리한다.
• 그러나 데이터들이 화살표로 서로 연결되어 있어 데이터들이 떨어진 장소에 위치해도 된다는 점이 배열과는 다르다.
• 리스트의 종류
  • 단방향 리스트: 앞쪽에서 뒤쪽을 가리키는 방향성을 가진 끈으로 순서가 있는 데이터를 연결하는 방식. 단방향 리스트의 각 요소는 2가지 항목을 가지고 있다.
    • 데이터
    • 다음 요소를 가리키는 포인터: 요소와 요소를 연결하는 끈의 역할. 위치 정보가 저장되어 있다
      즉, 단방향 리스트는 HEAD 포인터(첫 번째 요소를 가리키는 포인터)가 가리키는 요소에서 시작하고 NEXT 포인터가 종료 정보를 저장한 요소(TAIL 포인터: 마지막 요소를 가리키는 포인터)에서 끝난다.
  • 양방향 리스트: 앞에서부터 뒤를 가리키는 끈과 뒤에서 앞을 가리키는 끝 2개를 사용하여 순서가 있는 데이터들을 연결하는 방법. 양방향 리스트의 각 요소는 3가지 항목을 가지고 있다
    • 데이터
    • NEXT 포인터: 다음 요소를 가리키는 포인터
    • PREV 포인터: 이전 요소를 가리키는 포인터

이미지: [자료구조] C - 링크드리스트, LInkedList

N번째 요소의 참조가 빠른 것은 배열, 느린 것은 리스트 구조.
데이터의 삽입 삭제가 빠른 것은 리스트 구조, 느린 것은 배열.

3. 스택(stack)

책상 위에 책을 쌓듯 데이터를 관리하는 자료구조.

• FILO(First In Last Out), LIFO(Last In First Out)
• 데이터를 넣는(쌓는) 작업을 푸시(PUSH)
• 데이터를 꺼내는 작업을 팝(POP)

4. 큐(queue)

대기 행렬. 데이터를 넣은 순서대로 데이터를 꺼내는 데이터 관리 방법

• FIFO(First In First Out), LILO(Last In Last Out)
• 큐에서는 중간에 끼어들거나
• 순서를 어기고 새치기 하는 행동은 허용되지 않는다.

5. 트리(나무 구조)

나무가지가 2개, 3개, ...로 갈라지고, 그 갈라진 끝에서 2개, 3개, ... 나뉘듯 펴져 나가는 자료구조.

이미지: 자료구조-트리의 기본 개념/용어

• 트리의 종류
  • 이진 트리(바이너리 트리): 부모 하나에서 자식 둘이 딸린 구조
  • 힙: 부모 노드의 값이 자식 노드의 값보다 항상 적은 이진 트리. 실제로 힙을 구현할 때에는 일반적으로 배열을 사용. 배열 요소 번호는 힙의 '뿌리' 첫 번째 요소로,
    • '깊이'는 작은 쪽에서 큰 쪽으로
    • 노드의 왼쪽에서 오른쪽 방향으로 대입한다.

---

✨ tl;dr

✔️ 자료구조란?

• 대량의 데이터를 입력하고 처리한 후, 그 결과를 출력하는 알고리즘에는 대량 데이터의 입출력 및 처리에 보다 효율적인 대량 데이터의 유지 관리 방법이 필요하다.
• 자료 구조의 종류는 여러가지가 있지만 그 중 대표적으로 배열, 리스트, 스택, 큐, 트리가 있다