Space-Efficient List
-
[ Open Data Structures ] - Space-Efficient Linked List - 2DataStructure 2021. 5. 14. 20:00
Nodeを包括する関数の場合, template 宣言のため、 コンパイラーの問題が発生する。これらの問題はMeta programmingに関する問題点と推定される。SEList自体が今まで学んできたデータ構造の中で一番やっかい構造の一つである。 参考 : Introduction to metaprogramming in C++ | InfoWorld Removing an Element 자료의 제거는 추가와 유사하다. 가장 먼저 자료의 index i를 포함하는 노드 u를 찾는다. 그리고 블록의 크기가 b - 1보다 작아지지 않도록 주의하며 자료가 삭제될 수 없는 모든 경우를 고려하는 것이다. Amortised Analysis of Spreading and Gathering 여기서는 Add와 Remove에 의해 호출될 수 있는 Gath..
-
[ Open Data Structures ] - Space-Efficient Linked List - 1DataStructure 2021. 5. 14. 13:13
Linked List의 깊은 곳에 위치한 Node에 접근하는 시간적인 비용을 차치하고도 Linked List엔 단점이 하나 존재하는데 그것은 공간의 효율성이다. DLList의 각 Node는 해당 Node의 전후를 가리키는 Prev와 Next 두 개의 Reference 혹은 Pointer를 요구한다. DLList의 Node를 보면 prev, next와 실제 정보를 저장하는 x의 총 세 개의 Field로 이루어져 있는데 이들 중에서 실질적으로 정보를 저장하는 Field는 x밖에는 없다. 따라서, Space-Efficient Linked List(以下SEList)는 DLList에 개별의 자료/원소를 저장하기 보다는 몇 개의 자료를 포함하는 Array/Block을 사용하여 공간의 낭비를 줄인다. 조금 더 상세하..