데이터 구조 개선

Question

Dublly Linked List를 사용하여 구현 한 스택처럼 작동하는 데이터 구조가있는 경우 중간 요소를 항상 유지하는 포인터도 추가했습니다.

O (log (k))에 K 번째로 삽입 된 요소를 반환하는 peekAt (k) 메서드를 추가하여 수정하려고합니다.

나는이 작업을 수행하는 방법에 어떤 아이디어? 감사.

Answer 1

double linked list으로 구현 한 경우 연결된 목록에 요소에 대한 임의 액세스 권한이 없으므로 k-th 요소 시간을 O(log(k)) 시간으로 반환 할 수 없습니다. 대신 O(1) 액세스를 얻을 수있는 곳에서 스택을 (dynamic) array으로 구현하는 것이 좋습니다.

편집 : 당신은 그때가 balanced binary tree을 사용하는 것이 좋습니다, 어떤 장소에서도 빠른 insertion/deletion하려면

.