Data Strcutures
-
[ 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을 사용하여 공간의 낭비를 줄인다. 조금 더 상세하..