CS 부수기 - 선형 자료 구조 편

0. 들어가며

---

본격적으로 기술 면접을 준비하며 Computer Science의 전반야에 대해 하나씩 정리해 나가려고 한다.
그 첫번째는 선형 자료 구조(Linear Data Structure)편이다.

참고로 이 정리본은 내가 공부하기 위해 만들었고, 추후에도 지속적으로 보완해갈 예정이다.

단순히 현재 취업만을 위해 쓰일 것도 아니며, 이후에 이직을 하거나 또 다른 면접을 위해서도 사용할 예정이기에 최대한 간결하면서도 직관적으로 적어나갈 생각이다.

1. Linear Data Structure

---

자료 구조에는 크게 선형 자료 구조(Linear Data Structure)와 비선형 자료 구조(Nonlinear Data Structure)가 있다.

선형 자료 구조의 정의는 다음과 같다.

선형 자료구조 : 하나의 원소 뒤에 하나의 원소만이 존재하며, 직선 형태로 나열되어 있는 구조

우리가 개발을 하면서 가장 대표적으로 볼 수 있는 선형 자료 구조의 형태는 List, Array 등이 있다.

다음 사진을 참고하면 좋다.

선형 자료구조의 이해를 돕기 위한 사진

비선형 자료 구조(Nonlinear Data Structure)에 대해서는 추후에 새로운 포스팅으로 소개하곘다.

2. Stack & Queue

---

선형 자료 구조의 가장 기본이 되는 자료 구조는 스택(Stack)과 큐(Queue)이다.

결론부터 설명하자면 스택은 과자 프링글스를 생각하면 편하고, 큐는 에버랜드를 들어가기 위해 사람들이 질서정연하게 서있는 줄을 생각하면 된다.

• Stack
  • 의미 : 가장 마지막에 들어간 원소가 가장 먼저 나오는 자료 구조
  • 특징 : LIFO - Last In First Out
  • 예시 : Recursion Function (재귀 함수)
  • 시간 복잡도
    • 삽입 / 삭제의 시간 복잡도 : O(1)
    • 탐색의 시간 복잡도 : O(n)
  • 사진

  스택의 이해를 돕기 위한 사진

</p>

• Queue
  • 의미 : 가장 먼저 들어간 원소가 가장 먼저 나오는 자료 구조
  • 특징 : FIFO - First In First Out
  • 예시 : CPU 작업을 기다리는 프로세스들
  • 시간 복잡도
    • 삽입 / 삭제의 시간 복잡도 : O(1)
    • 탐색의 시간 복잡도 : O(n)
  • 사진

큐의 의해를 돕기 위한 사진

이 정도로 스택과 큐는 정리가 된다.

3. Linked List

---

다음은 링크드 리스트(Linked List) 혹은 연결 리스트로 불리는 녀석이다.

말 그대로 원소들이 서로 연결된 형태를 띄기 때문에 연결 리스트 영어로는 Linked List 라고 불리운다.

• Linked List
  • 의미 : 리스트의 원소 안에 다음 노드에 대한 포인터(pointer) 혹은 주소값을 가지는 리스트
  • 종류
    • Single Linked List : 다음 노드에 대해서만 포인터 존재
    • Double Linked List : 이전 노드와 다음 노드에 대해서 포인터 존재
    • Circular Linked List : Single Linked List와 똑같지만 마지막 노드의 포인터가 첫 번째 노드를 가리키는 형태
  • 특징
    • Head Node(첫번째 노드)가 존재
    • Single / Double Linked List의 경우 마지막 노드가 가리키는 포인터는 없거나 NULL
  • 시간 복잡도
    • 삽입 / 삭제 : O(1)
    • 탐색 : O(n)
  • 사진

Single Linked List

Double Linked List

Circular Linked List

이렇게 링크드 리스트도 정리가 되었다.

4. Array

---

이번엔 Array 즉, 배열을 알아보자. 코드를 치는 사람이라면 배열이 가장 친숙하지 않을까.

• Array
  • 의미 : 같은 타입의 변수로 이루어진, 정적이고 인접한 메모리 위치에 있는 원소의 집합
  • 특징 : Index로 해당 원소에 접근하는 Random Access가 가능.
  • 시간 복잡도
    • 삽입 / 삭제 : O(n)
      • 원소의 처음 혹은 중간에서 삽입과 삭제가 진행될 경우, 진행된 이후 위치의 원소들은 모두 Shift가 이루어지기 때문
    • 탐색 : O(1)
      • 인덱스로 Random Access가 가능하기 때문에 탐색에 매우 용이

이 정도로 배열은 간단하게 정리된다.

5. 정리하며

---

선형 자료 구조는 이 정도로 마무리 된다.

다음 포스팅은 비선형 자료 구조를 공부하고 리뷰할 예정이다.

Adios.