연결 리스트 (Linked List)

특징

배열 보다 삽입/삭제가 빠르고 데이터 접근은 더 느린 자료구조이다.

자바 구현

자바의 LinkdedList는 List 인터페이스의 구현체이므로 add remove set 같은 메소드를 사용 가능하다.
내부적으로 이중 연결 리스트로 구현되어있고, 최적화가 잘 되어있어 직접 연결 리스트를 구현하는것 보다 바로 사용하는게 낫다.

예시 코드

List<Integer> list = new LinkedList<>();

list.addFirst(10);
list.addLast(20);

System.out.println(list.getFirst()); // 10
System.out.println(list.removeLast());  // 20

메소드 시간복잡도

• 뒤에 데이터 추가 O(1): addFirst(E e)
• 앞에 데이터 추가 O(1): addLast(E e)
• 맨 앞의 값 가져오기 O(1) : E getFirst()
• 맨 뒤의 값 가져오기 O(1) : E getLast()
• 특정 인덱스의 값 가져오기 O(N) : E get(int index)
• 맨 앞의 값 가져오고 삭제 O(1) : E removeFirst()
• 맨 뒤의 값 가져오기 O(1) : E removeLast()

스택 (Stack)

특징

선입후출 자료구조다.

자바 구현

Stack 클래스를 사용하거나 ArrayList로 구현할 수 있지만, 스택에 최적화된 ArrayDeque를 쓰는 것이 좋다. 단일 스레드 환경에서 가장 빠르고 효율적이다.

예시 코드 (Stack)

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
System.out.println(stack.pop()); // 2

Stack, ArrayDeque

• 데이터 넣기: push()
• 데이터 꺼내기: pop()

ArrayList

• 데이터 넣기: add()
• 데이터 꺼내기: remove(size - 1)

참고: Stack 클래스는 오래된 클래스이고 동기화가 필요 없는 단일 스레드에서는 ArrayDeque가 더 효율적이다.

큐 (Queue)

특징

선입선출 자료구조다.

자바 구현

Queue 인터페이스를 구현한 ArrayDeque를 사용하면 대부분의 단일 스레드 환경에서 가장 빠르고 효율적이다. LinkedList도 가능하지만, 배열 기반 구조인 ArrayDeque가 일반적으로 더 좋다.

예시 코드

Queue<Integer> queue = new ArrayDeque<>();
queue.offer(1); // 또는 add(1)
int a = queue.poll(); // 또는 remove()

poll 은 remove 와 다르게 리스트가 비어있을때 예외가 아닌 null을 반환하므로 안전하다.

참고: 선언 방식에 따라 사용 가능 메서드가 다르다.

• Queue<Integer> queue = new ArrayDeque<>(); → Queue 메서드만 사용 가능
• LinkedList<Integer> list = new ArrayDeque<>(); → 모든 메서드 사용 가능
• Deque<Integer> deque = new ArrayDeque<>(); → Deque 관련 메서드 사용 가능

단일 스레드 큐/스택 용도로는 ArrayDeque가 최적 선택입니다.

트리 (Tree)

특징

계층 구조로 데이터를 표현하는 자료구조이다. 탐색, 삽입, 삭제 동작을 모두 효율적으로 해야할 때 유용하다.

자바 구현

컬렉션에 TreeSet 과 TreeMap 이 구현되어 있지만
웬만하면 문제에 맞게 직접 구현해서 쓴다.

예시 코드

private static class Node<T> {
    T data;
    Node left;
    Node right;

    Node(T data, Node left, Node right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
}

//..

List<Node> tree = new LinkedList<>();

//..

// 중위 순회 코드
void inOrder(TreeNode node) {
    if (node == null) return;
    inOrder(node.left);
    System.out.print(node.key + " ");
    inOrder(node.right);
}

이진 트리

특징

• 이진 트리는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리 구조이다.

이진 탐색 트리 (Binary Search Tree)

특징

탐색을 효율적으로 하기 위한 자료구조이다.

• 루트 기준 작은 값을 왼쪽, 큰 값을 오른쪽으로 배치하여 중위 순회시 정렬된 값을 얻을 수 있다.
• 키값 x 를 탐색 또는 삽입 할 때, 매우 빠르다. h는 트리의 높이일 때 모두 $O(h)$이다.
• 균형적일 경우 h = LogN, 한쪽에 쏠려있을 경우 h = N
• 값의 중복을 허용하지 않는다.

자바 구현

TreeSet 으로 구현되어있다.

예시 코드

Set<Integer> tree = new TreeSet<>(Arrays.asList(5, 3, 1, 9, 7));
tree.add(2);
for(int i: tree) {
	System.out.print(i + " "); // 1 2 3 5 7 9
}

이진 탐색 트리의 조건은 정렬과 중복된 값 없음 이므로 특정 리스트를 TreeSet 으로 변환하면 정렬되고 중복된 값이 제거된다.
값의 위치를 찾고싶다면 다시 List로 변환해서 Collections.binarySearch() 를 사용해도 된다.

완전 이진 트리

특징

• 완전 이진 트리는 모든 레벨이 채워져 있으며, 마지막 레벨은 왼쪽부터 순차적으로 채워진 트리이다.
• 완전 이진 트리의 특성상 노드들이 배열에 연속적으로 저장될 수 있다. 예를 들어, 루트 노드가 인덱스 1에 있고, i번 노드의 왼쪽 자식은 2i, 오른쪽 자식은 2i+1이라는 관계를 이용하여 매우 효울적으로 작동한다.

구현 예시

// 배열을 사용하여 트리의 노드들을 저장하는 경우 (1-based 인덱스 사용)
int[] tree = new int[size + 1]; // size는 트리의 노드 수

이 구조는 힙(Heap) 등 여러 트리 기반 자료구조에서 사용된다.

힙 (Heap)

특징

완전 이진 트리에 부모노드가 자식노드보다 무조건 작거나 큰 값을 가지면 힙 구조이다.
모든 값이 아닌, 최대값이나 최소값을 빠르게 찾기 위한 구조이다.

• 힙 생성 O(N)
• 삽입/삭제 O(LogN)

우선순위 큐 (Priority Queue)

특징

• 내부적으로 Heap 구조이다. (완전 이진 트리)
• 우선순위가 가장 높은 요소를 맨 앞에 위치하도록 한다.

자바 구현

PriorityQueue 클래스를 사용한다.

// 작은 수가 우선순위인 우선순위 큐
Queue<Integer> q = new PriorityQueue<>();
q.offer(3);
q.offer(1);
q.offer(12);
q.offer(2);
System.out.println(q); // [1, 2, 12, 3]
int a = q.poll(); // a == 1
System.out.println(q); // [2, 3, 12]

우선순위 변경

Comparator 를 활용하여 다른 우선순위를 적용할 수 있다.

• 기본: 작은 값 우선

• 큰 값 우선 : new PriorityQueue<>(Collections.reverseOrder());

• 임의의 순서: Comparator 사용

  class Node {
      int num;  // 노드 번호
      int cost; // 노드까지의 비용
  
      public Node(int num, int cost) {
          this.num = num;
          this.cost = cost;
      }
  }
  
  // Node.cost 가 작은 것이 우선순위인 우선순위 큐
  Queue<Node> q = new PriorityQueue<>((o1, o2) -> Integer.compare(o1.cost, o2.cost));

해시 (Hash)

특징

• 검색과 저장이 매우 빠른 자료구조
• 특정 항목 탐색 시, 키가 있는 위치를 계산하여 직접 접근하여 탐색이 O(1) 이다.
• 내부적으로 저장할 때 인덱스를 해시 함수로 구해서 저장한다.

Map<String, Integer> map = new HashMap<>();
map.put("s", 2);
map.put("s", 1); // 덮어쓰기
map.put("s1", 3);
map.get("s"); // 1

트라이 (Trie)

특징

• 문자열의 집합을 표현하는 트리.

• 많은 단어에서 빠른 접두사 검색을 할 때 사용

• 각 간선 (또는 정점)이 하나의 문자에 대응하고

• 단말 노드 (자식이 없는) 노드는 루트부터 쭉 내려오며 문자를 모두 합한 문자열에 대응하게 된다.

그래프

[알고리즘] 그래프 표현 및 문제 풀이시 표현 방법 선택 기준 참고

Java 문법 공식 문서: oracle JDK 11 Docs