[자료 구조] Interview Question for Beginner

Array

- 조회: 논리적 저장 순서 = 물리적 저장 순서 (random access O(1) 가능)

- 삭제, 삽입: 접근 O(1) + shift O(n) = O(n)

Linked List

- 조회: 논리적 저장 순서 != 물리적 저장 순서 O(n)

- 삭제, 삽입: O(n)

Stack

- LIFO or FILO

 

Queue

- Heap 구현하기

 

Stack 2개로 Queue 구현하기
하나는 입력만 받고, 다른 하나는 pop 만 하게 한 후, pop 하는 쪽이 비면 입력 받는 stack 에 원소가 있다면 pop 시켜서 가져오게끔 구현하면 된다.

 

Tree

- 포화 이진 트리: 모든 노드가 2개의 자식 노드를 갖는 트리

- 완전 이진 트리: 위에서 아래로, 왼쪽에서 오른쪽으로 차곡차곡 채워져 있는 트리

- 정 이진 트리: full binary tree, 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리

 

이진탐색트리

- 구현 시 고려할 점이 많고 까다롭다.

 

Heap

시간복잡도

종류	ArrayList	LinkedList	HashSet	TreeSet	HashMap	TreeMap	PriorityQueue	ConcurrentHashMap
add	O(1)	O(1)	O(1)	O(logn)	-	-	O(logn)	-
remove	O(n)	O(1)	-	-	-	-	O(logn)	-
get	O(1)	O(n)	-	-	O(1)	O(logn)	O(1)	O(1)
contains	O(n)	O(n)	O(1)	O(logn)	-	-	-	-
containsKey	-	-	-	-	O(1)	O(logn)	-	O(1)
iterator.remove	O(n)	O(1)	-	-	-	-	-	-
next	-	-	O(h/n)	O(logn)	O(h/n)	O(logn)	-	O(h/n)
size	-	-	-	-	-	-	O(1)	-

HashSet 과 HashMap

• HashSet: 중복을 허용하지 않는다. 순서가 없다. equals() 와 hashcode() 메서드를 사용해 중복 여부를 체크한다.
• HashMap: key 는 중복이 없지만, value 는 중복이 허용된다.