TIL9: Data Structure - 2 [ Linked List / Hash Table ]

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)