Linear

배열

int[] array = new int[10];

Linked List

List<Integer> arrayList = new ArrayList<Integer>();
// List<T> : 인터페이스
// ArrayList<T> : 구현체

LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.add(1);
linkedList.remove(1);

Stack

ArrayDeque<Integer> stack = new ArrayDeque();
stack.push(1); // 넣기
stack.peek(); // 꺼내지 않고 보기
stack.pop(); // 꺼내기

Queue

ArrayDeque<Integer> queue = new ArrayDeque();
queue.offer(1); // 넣기
queue.poll(); // 꺼내기

Tree

Binary Tree

// Linked List
class Node {
	Object data;
	Node left_child, right_child;
}
LinkedList<Node> tree = new LinkedList<Node>();

// Index를 이용한 Array
Parent: i/2
Left Child: i*2;
Right Child: i*2+1;

Heap

• 완전 이진트리 형태
• 시간복잡도: O(logN)
• 최소값(Min Heap), 최대값(Max Heap)을 찾을 때 사용
• 삽입 연산 시 조건 만족 확인 후 만족하지 않는 경우 부모-자식 위치 변경
• 삭제 연산 시 항상 루트 노드를 삭제 후 가장 마지막 노드를 루트로 이동, 조건 확인 후 만족하지 않는 경우 리프 노드가 될 때까지 부모-자식 변경하며 확인

Priority Queue

Heap을 이용

PriorityQueue<Integer> pq = new PriorityQueue();
pq.offer(1);
pq.poll();

// order 변경
PriorityQueue<Integer> reversePq = new PriorityQueue(Collections.reverseOrder());

// order 변경 - comparator
PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
	@Override
    	public int compare(Integer o1, Integer o2) {
    		return Integer.compare(o1, o2);
	}
)