똑똑한 코드 작성을 위한 실전 알고리즘

283

8

장

정리

이 책의 목표는 기초 알고리즘과 컴퓨터 과학의 기본 데이터 타입을 소개하는 것이었다. 코드

의 성능을 최대화하려면 다음과 같은 데이터 타입을 효율적으로 구현하는 방법을 알아야 한다.

백

연결 리스트는 값을 추가할 경우에

O

(

1

)의 성능을 보장한다. 배열을 사용하고자 한다면, 배

열 크기를 확장하기 위해 기하학적 크기 재조정을 도입할 필요가 있어 평균적인 사용에서 거

의

O

(

1

)의 성능을 보장한다(드물게 크기 재조정 이벤트가 발생하면 런타임 성능이

O

(

N

)이

된다 ). 백은 일반적으로 값 제거를 허용하지 않으며 중복 값이 추가되는 것을 방지하지도 않

는다.

스택

연결 리스트는 스택에 값을 저장할 수 있는데

push

()

와

pop

()

은

O

(

1

) 런타임 성능을 보인다.

스택은 값을 삽입하고 제거하기 위해 스택의 최상단을 기록한다.

큐

연결 리스트는 효율적으로 큐를 저장할 수 있는데

enqueue

()

와

dequeue

()

는

O

(

1

)의 런타

임 성능을 보인다. 큐는 연결 리스트의

first

와

last

노드를 기록해 효율적으로 큐에서 값을

제거하거나 추가한다.

정리

CHAPTER

8

284

똑똑한 코드 작성을 위한 실전 알고리즘

심볼 테이블

심볼 테이블에 대한 개방 주소법 접근은 (키, 값 ) 쌍을 분배하기 위한 알맞은 해시 함수를 가

지고 효율적으로 운영된다. 저장 ...