Data Structure and Algorithms (3)

Linked List and Hash Table

 

Array vs. Linked List

Array(배열)는 “연속된 메모리 공간”에 “같은 타입”의 데이터를 순차적으로 저장하는 자료구조이고 Linked List는 array와 다르게 생성 후에 자유롭게 원소를 추가/삭제할 수 있는 자료구조입니다.

 

Array

Array는 index를 통해 빠르게 접근할 수 있습니다.

Array는 크기가 고정되어 있기 때문에 array를 생성할 때 크기를 지정해 주어야 합니다.

Array가 가득 차는 경우 새로운 데이터를 추가할 수 없거나 기존 데이터를 삭제해야 할 수 있습니다.

 

Linked List

Linked List는 가변적인 길이를 가지고 있기 때문에, 새로운 데이터 추가에 대한 제한이 거의 없다는 장점이 있습니다.

Linked List는 기본적으로는 하나의 요소에 그 다음 요소가 연결되어 있는 단순 연결리스트의 형태로 구현되고 경우에 따라 원형 연결 리스트, 이중 연결 리스트 등으로 나타내기도 합니다.

 

※ 파이썬의 List는 Linked List가 아니라 dynamic array로 구현되어 있습니다. (혼동하면 안 됩니다.)

특징	Static Array (정적 배열)	Dynamic Array (동적 배열)
크기	고정 (컴파일 시간에 크기 결정)	가변 (런타임 중 크기 변경 가능)
메모리 할당	스택에서 할당	힙에서 할당
성능	메모리 할당이 빠르고 효율적	크기 조정 시 메모리 재할당 필요, 상대적으로 느림
유연성	크기 변경 불가능	크기 동적 조정 가능
메모리 사용	메모리 낭비 또는 부족 가능	필요에 따라 메모리 할당, 효율적 관리 가능
사용 예시	고정 크기의 데이터를 다룰 때 적합

 

Hash Table

해시 테이블(hash table), 해시 맵(hash map), 해시 표는 컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조입니다. 

Hash table은 데이터의 key를 hash function(해시 함수)을 통해 hash value로 변환하고, 이 값을 인덱스로 사용하여 데이터를 저장하거나 검색하는 효율적인 자료 구조입니다. (색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산)

평균적으로 O(1)의 시간 복잡도로 데이터에 접근할 수 있습니다.
Hash table의 사용 목적은 정해진 메모리에 여러 원소를 효율적으로 저장하여 indexing 성능을 O(1)에 가깝게 만드는 것에 있습니다.
Hash function을 통해 hashing을 하게 되면 다른 원소가 같은 index를 가지는 hash collision(해시 충돌)이 발생할 수 있습니다. Hash collision을 해결하기 위해서 많이 사용되는 방법은 아래 두 가지가 있습니다.

• Separate Chaining
• Open Addressing

특징	Separate Chaining	Open Addressing
메모리 사용	추가 메모리(연결 리스트 등 필요)	추가 메모리 필요 없음
클러스터링	클러스터링 문제 없음	클러스터링 문제 발생 가능
테이블 크기	테이블이 꽉 차도 동작	테이블이 꽉 차면 성능 저하
삭제 연산	삭제가 간단 (리스트에서 제거)	복잡한 삭제 처리 (표시 필요)
탐색 성능	충돌이 많으면 성능 저하 (O(n))	테이블이 꽉 차면 성능 저하 (O(n))
간단한 구현	상대적으로 복잡함	상대적으로 간단함