Stay organized with collections
Save and categorize content based on your preferences.
C++ Reference: class DenseDoublyLinkedList
Note: This documentation is automatically generated.
Specialized doubly-linked list that initially holds [0..n-1] in an arbitrary
(user-specified) and fixed order.
It then supports O(1) removal and access to the next and previous element of
a given (non-removed) element.
It is very fast and compact: it uses exactly 8*n bytes of memory.
[[["Easy to understand","easyToUnderstand","thumb-up"],["Solved my problem","solvedMyProblem","thumb-up"],["Other","otherUp","thumb-up"]],[["Missing the information I need","missingTheInformationINeed","thumb-down"],["Too complicated / too many steps","tooComplicatedTooManySteps","thumb-down"],["Out of date","outOfDate","thumb-down"],["Samples / code issue","samplesCodeIssue","thumb-down"],["Other","otherDown","thumb-down"]],["Last updated 2024-08-06 UTC."],[[["\u003cp\u003e\u003ccode\u003eDenseDoublyLinkedList\u003c/code\u003e is a specialized doubly-linked list in C++ designed for efficient element removal and access to next/previous elements.\u003c/p\u003e\n"],["\u003cp\u003eIt initializes with a user-defined order of elements [0..n-1] and maintains this order throughout its operations.\u003c/p\u003e\n"],["\u003cp\u003eThis data structure boasts a compact memory footprint, using only 8*n bytes.\u003c/p\u003e\n"],["\u003cp\u003eKey functionalities include \u003ccode\u003eNext()\u003c/code\u003e, \u003ccode\u003ePrev()\u003c/code\u003e, and \u003ccode\u003eRemove()\u003c/code\u003e for navigating and manipulating the list, with \u003ccode\u003eO(1)\u003c/code\u003e time complexity for these operations.\u003c/p\u003e\n"],["\u003cp\u003eThe list also provides a \u003ccode\u003eSize()\u003c/code\u003e method to retrieve the current number of elements.\u003c/p\u003e\n"]]],["The `DenseDoublyLinkedList` class creates a specialized doubly-linked list containing elements \\[0..n-1\\] in a fixed order. It provides O(1) removal via `Remove(int i)` and access to adjacent elements using `Next(int i)` and `Prev(int i)`. `Next()` and `Prev()` returns -1 when called on the last/first elements, and they require that the element is not removed. The constructor `DenseDoublyLinkedList(const T& sorted_elements)` creates the list, and `Size()` gets its size. The list uses 8\\*n bytes of memory.\n"],null,["# DenseDoublyLinkedList\n\nC++ Reference: class DenseDoublyLinkedList\n==========================================\n\n\nNote: This documentation is automatically generated.\nSpecialized doubly-linked list that initially holds \\[0..n-1\\] in an arbitrary (user-specified) and fixed order. It then supports O(1) removal and access to the next and previous element of a given (non-removed) element. \n\nIt is very fast and compact: it uses exactly 8\\*n bytes of memory.\n\n| Method ||\n|---------------------------------------------------------------------------------------------------------------------------|-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|\n| [`DenseDoublyLinkedList`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/dense_doubly_linked_list.h#L35) | Return type: `explicit ` Arguments: `const T& sorted_elements` \u003cbr /\u003e |\n| [`Next`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/dense_doubly_linked_list.h#L41) | Return type: `int ` Arguments: `int i` Next() (resp. Prev()) must be called on elements that haven't yet been removed. They will return -1 if called on the last (resp. first) element. |\n| [`Prev`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/dense_doubly_linked_list.h#L42) | Return type: `int ` Arguments: `int i` \u003cbr /\u003e |\n| [`Remove`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/dense_doubly_linked_list.h#L45) | Return type: `void ` Arguments: `int i` You must not call Remove() twice with the same element. |\n| [`Size`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/dense_doubly_linked_list.h#L37) | Return type: `int ` \u003cbr /\u003e |"]]