[ Open Data Structures ] - Space-Efficient Linked List - 2

Nodeを包括する関数の場合, template 宣言のため、 コンパイラーの問題が発生する。これらの問題はMeta programmingに関する問題点と推定される。SEList自体が今まで学んできたデータ構造の中で一番やっかい構造の一つである。

参考 : Introduction to metaprogramming in C++ | InfoWorld

 

Removing an Element

 

자료의 제거는 추가와 유사하다. 가장 먼저 자료의 index i를 포함하는 노드 u를 찾는다. 그리고 블록의 크기가 b - 1보다 작아지지 않도록 주의하며 자료가 삭제될 수 없는 모든 경우를 고려하는 것이다.

SEList의 b가 3인 경우에 자료 x를 삭제하는 경우들을 나열한 것이다.

 

Amortised Analysis of Spreading and Gathering

 

여기서는 Add와 Remove에 의해 호출될 수 있는 Gather과 Spread의 Running time을 분석한다. 코드는 다음과 같다.

 

Lemma

 

 

Summary

 

개인적으로 소화하기가 벅차다. 평소에 어떤 생활을 해야 이런 것을 떠올릴 수 있는지 궁금하다. 다음 Theorem을 통해 Space-Efficient List를 정리할 수 있다.

HiddenWriter/LinkedList (github.com)