Linked List(연결 리스트)

  • 특징
    • 크기가 동적으로 변하는 자료 구조
    • 자료 구조를 구성하는 요소 Node들의 연결로 이루어짐
  • 종류
    • Single Linked List(단일 연결 리스트)
    • Double Linked List(이중 연결 리스트)
  • 메소드: addToTail, remove, getNodeAt, contains, indexOf, size
  • 속성
    • 노드: value, next
    • 연결리스트: head, tail, size
  • Big O 표기
    • 가져오기: O(n)
    • 추가하기: O(1)
    • 삭제하기: O(1)

Hash Table(해시 테이블)

  • 특징
    • Hash Map이라고도 함
    • key-value 쌍을 저장하는 자료 구조
    • 키를 **Hash Function(해시 함수)**를 통해 특정 숫자값의 인덱스로 변환
    • 해시 테이블은 필요할 때에만 메모리 크기를 늘리고, 가능한 작은 크기를 유지
    • 해싱된 인덱스와 값이 항상 1:1로 매핑되지 않고, 사이즈가 커짐에 따라 확률적으로 두 가지 이상의 값에 대하여 한개의 인덱스가 생성될 수 있어 이러한 경우에 대한 '충돌' 해결 방법이 필요
  • 메소드: insert, retrieve, remove, resize
  • 속성 : size, limit, storage
  • Big O 표기
    • 가져오기: O(1)
    • 추가하기: O(1)
    • 삭제하기: O(1)

한 가지 불편한(?) 진실은 이제까지 언급한 Stack/ Queue/ Linked List 의 Big O Notation은 Average Cases나 Worst Cases 모두 동일하였으나, Hash Table의 경우 데이터가 커질수록 즉, Worst Cases가 될 수록 가져오기, 추가하기, 삭제하기 모두 **O(n)**에 가까워진다는 사실입니다.

자료 출처: 코드스테이츠(CodeStates)

0개의 댓글