자료구조

Array

• 정적으로 필요한만큼만 원소를 저장할 수 있는 공간이 할당.
• 주소는 연속적으로 할당
  • 논리적 저장 순서와 물리적 저장 순서가 일치함
  • 인덱스로 해당 원소에 접근 (random access 가능)
  • 접근 : O(1)
  • 삭제 : O(N)
    • 해당 원소에 접근한 뒤 연속적인 특징이 깨져서 삭제한 원소보다 큰 인덱스의 원소들 shift
  • 삽입 : O(N)
    • 모든 원소들의 인덱스를 1씩 shift
• 지정된 개수 초과시 배열 크기를 재할당한 후 복사

Linked List

• 각각의 원소들이 자기 자신 다음에 어떤 원소인지만을 기억
  • 이 부분을 다른 값으로 바꿔주면 O(1)에 삭제와 삽입이 가능
• 원하는 위치를 찾기 위해 첫번째 원소부터 다 확인해봐야한다는 문제가 있음
  • 배열과 달리 논리적 저장 순서와 물리적 저장 순서가 일치하지 않음
  • 따라서 원소 찾는 데에 O(n)의 시간이 또 필요 -> 결국엔 삽입 삭제에 O(n)
  • 하지만 불필요한 데이터 복사는 일어나지 않는다
  • 앞이나 뒤만 삽입 삭제하면 찾는 과정이 없어서 O(1)
• 동적으로 메모리 할당

리스트 (List)

Arraylist

스택 (Stack)

• 선형 자료구조
• LIFO (Last In First Out) : 나중에 들어간 원소가 먼저 나오는 구조

큐 (Queue)

• 선형 자료구조
• FIFO (First In First Out) : 먼저 들어간 원소가 먼저 나온다

우선순위 큐 (Priority Queue)

트리 (Tree)

• 비선형 자료구조, 계층적 관계 표현
  1. Node (노드)
  2. Edge (간선)
  3. Root Node (루트 노드)
  4. Terminal Node (Leaf Node, 단말 노드)
  5. Internal Node (내부 노드, 비단말 노드)

이진탐색트리 (BST)

해시 테이블 (Hash Table)

https://github.com/gyoogle/tech-interview-for-developer/tree/master/Computer%20Science/Data%20Structure

https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure