問題描述
我的問題很簡單，是否可以使用 C++，在不使用指針(下一個節點)的情況下實現鏈表數據結構?為了進一步限定我的問題，我的意思是可以僅使用類實例化來創建鏈表數據結構.
My question is very simple, can one using C++, implement a link-list data structure without using pointers (next nodes)? To further qualify my question, I'm mean can one create a Linked-List data structure using only class instantiations.
一個常見的節點定義可能是這樣的:
A common node definition might be like so:
template<typename T>
struct node
{
T t;
node<T>* next;
node<T>* prev;
};
我知道 std::list 等，我只是想知道它是否可能 - 如果有的話如何?代碼示例將不勝感激.
I'm aware of std::list etc, I'm just curious to know if its possible or not - and if so how? Code examples will be greatly appreciated.
更多說明:
- 插入應該是 O(1).
- 遍歷不應該超過 O(n).
- 實節點和空節點應該是可微的.
- 鏈表的大小應僅受可用內存量的限制.
推薦答案
當然，如果你不介意鏈表有一個最大大小，你可以靜態分配一個鏈表節點數組，然后使用整數索引到數組作為每個節點的上一個"和下一個"值，而不是指針.我過去這樣做是為了節省一點內存(因為整數可以是 2 或 4 個字節，而在 64 位系統上，指針將是 8 個字節)
Sure, if you don't mind the linked list having a maximum size, you could statically allocate an array of list nodes, and then use integer indices into the array as your "previous" and "next" values for each node, rather than pointers. I've done in this in the past to save a bit of memory (since an integer can be either 2 or 4 bytes, whereas on a 64-bit system a pointer will be 8 bytes)
這篇關于不使用指針的鏈表實現是否可行?的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，也希望大家多多支持html5模板網！