항해99 워밍업 11일차

• 오늘 공부한 것
  - 자료구조 LinkedList, Stack, Queue, HashTable 구현
  - 알고리즘 문제 풀이
  
  
• 고민했던 문제
  - LinkedList Node의 parameter인 next는 어떤 타입이라고 할 수 있는가?
    -> value는 data field, next는 link field로 볼 수 있음 / 다음 노드의 포인터나 참조값을 저장함
  

  // Java Node definition
  
  private static class Node<E> {
      E item;
      Node<E> next;
      Node<E> prev;
  
      Node(Node<E> prev, E element, Node<E> next) {
          this.item = element;
          this.next = next;
          this.prev = prev;
      }
  }​

   
• 알게 된 것
  - 해시값 충돌 시 해결 방법 Seperate chaining(LinkedList) vs Open addressing(Open Bucket)
    -> Python은 Open addressing, Java는 Seperate chaining
    -> Java8 이후 LinkedList가 8개를 넘어가면 Red-Black Tree로 변경
  https://en.wikipedia.org/wiki/Red-black_tree