자료구조

• 효율적으로 접근할 수 있고 수정할 수 있도록 데이터를 구성하고 저장하는 방법

제목을 누르면 각 자료구조에 대한 더 자세한 설명이 있는 글로 이동 !

✏️ 선형 구조

• 데이터가 일렬로 나열되어 있음

배열 (Array)

• 동일한 자료형의 데이터를 일렬로 나열한 자료구조
  
  • 데이터 접근이 용이 - O(1)
  • 데이터 삽입/삭제가 어려움 - O(n)
  • 구조가 간단

연결 리스트 (Linked List)

• 각 노드가 데이터와 포인터를 가지고 일렬로 나열되어 있는 방식으로 데이터를 저장하는 자료구조
  
  • 데이터 접근이 느림 - O(n)
  • 데이터 삽입/삭제 용이 - O(1)
  • 포인터를 위한 추가 공간 필요

✏️ Array와 Linked list 차이

• Array
  • 연속된 메모리 공간에 순차적으로 데이터 저장
  • 데이터에 빠르게 접근하기 위해 사용
    • index를 통해 바로 접근 가능 → 빠름, O(1)
  • 중간에 데이터 삽입/삭제하는 경우
    • shift 연산 필요 → 느림
  • index가 n인 요소의 주소값 얻는 경우
    • 배열의 주소 + index*데이터 타입의 크기를 계산해 데이터에 빠르게 접근 → 검색(읽기) 유리

• LinkedList
  • 데이터가 불연속적으로 존재하며 데이터가 서로 연결되어 있음
  • 효율적으로 중간에 데이터 삽입/삭제하기 위해 사용
    • 포인터만 변경해주면 됨 → 빠름, O(1)
  • 데이터 검색하는 경우
    • 시작 index부터 찾고자하는 데이터까지 순차적으로 각 노드에 접근해야 함 → 느림, O(N)

‼️ 결론

• 데이터의 수가 변하지 않고 데이터에 빠르게 접근하고 싶은 경우 → Array
• 데이터 삽입/삭제가 자주 발생하는 경우 → Linked list

스택 (Stack)

• 데이터를 순서대로 쌓는 자료구조
• 삽입 연산, 삭제 연산이 한 방향에서 이루어지는 선형 자료구조
  
  • 후입선출 (LIFO)

큐 (Queue)

• 한 방향에서는 삽입 연산이, 반대편에서는 삭제 연산이 이루어지는 선형 자료구조
  
  • 선입선출 (FIFO)
  • 덱(Deque) : 양 방향에서 삽입 연산과 삭제 연산이 모두 이루어지는 큐

스택, 큐, 우선순위 큐 비교

자료구조	추출되는 데이터
스택 (Stack)	가장 나중에 삽입된 데이터
큐 (Queue)	가장 먼저 삽입된 데이터
우선순위 큐 (Priority Queue)	가장 우선순위가 높은 데이터

해쉬 테이블 (Hash Table)

• 비선형 구조로 구현될 수도 있음

✏️ 비선형 구조

• 데이터가 특정한 형태를 띄고 있음

트리 (Tree)

• 자료들 사이의 계층적 관계를 나타내는데 사용하는 자료구조
  

• 부모-자식 관계로 표현

그래프 (Graph)

• 여러 개의 점들이 서로 복잡하개 연결되어 있는 관계를 표현한 자료구조