如何創建一個空的雙向鏈表？

如果我有以下節點類如何創建一個空的雙向鏈表？

class Node { 
public: 
Node() { next = NULL; prev = NULL; } 
~Node() {} 
public : 
Node *next; 
Node *prev; 
T data; 
};

我如何在功能

鏈表::鏈表（）

我鏈表班組長具有以下功能創建一個空鏈表

void append(T item); 
T get(int idx); 
void insert(int idx, T item); 
void map(T (*pf)(T item)); 
T remove(int index); 
int size(); 
void unshift(T item);

來源

2011-04-13 Technupe

你的'LinkedList'類是什麼樣的？ – birryree 2011-04-13 18:05:43

你可以使用'STL'嗎？ – Donotalo 2011-04-13 18:06:07

雙鏈表通常會引用列表中的第一個和（有時）最後一個元素。

Node *first, *last;

在您的構造函數中，只需將它們設置爲NULL即可。然後制定一個isEmpty方法來檢查這種情況，並且你完成了。

LinkedList::LinkedList() 
{ 
    first = NULL; 
    last = NULL; 
} 

bool LinkedList::isEmpty() 
{ 
    return (first == NULL) && (last == NULL); 
}

來源

2011-04-13 18:07:30

我正在嘗試使用我上面顯示的節點類 – Technupe 2011-04-13 18:13:03

有更多的* magicky *實現雙向鏈表的方式，如在列表中保留一個空的節點，該節點通過指向自身的初始化並且不參與列表的內容。這種方法可以簡化代碼，因爲不需要在每個操作中檢查null，所以代碼分支的數量減少了。 – 2011-04-13 18:30:14

我一直在努力完成這項任務，有人請指導我通過這個 – Technupe 2011-04-14 23:01:23

我的解決方案（從預標準天）一直有一個類NodeBase與指針，並從中導出到添加數據。這允許我的DLList對象包含 a NodeBase，而不必單獨管理指針。而NodeBase總是有一個構造函數，它鏈接到無處—通常，通過設置兩個指針到這一點，例如：

struct NodeBase 
{ 
    NodeBase* next; 
    NodeBase* prec; 
    NodeBase() 
     : next(this) 
     , prec(this) 
    { 
    } 
    ~NodeBase() 
    { 
     next->prec = prec; 
     prec->next = next; 
    } 
};

這樣做意味着有列表指標沒有明確的一端（實際列表是圓形），因此您必須跟蹤迭代時開始的位置，但它使得其他操作變得如此簡單，因此要容易得多。

來源

2011-04-13 18:13:29

正如其他答案指出的那樣，有多種方法可以做到這一點。這裏是一個特別特殊的一個，供大家參考：雖然它不移植的C所以可能更適合於組裝：

struct Node { 
    Node *next; 
    Node *prev; 
}; 

struct List { 
    Node *a; 
    Node *b; 
    Node *c; 
    List : a(tail()), b(0), c(head()) 
    Node *head() { return (Node *)&a; } 
    Node *tail() { return (Node *)&b; } 
};

所以，一個結構包含虛擬頭節點（其prev指針當然是始終爲0）和一個僞尾節點（其next指針始終爲0），並且爲每個列表保存大量的sizeof(Node*)字節存儲，它們重疊（這使得它不可移植）。重疊不是必需的，您可以在List中放置兩個Node而不是三個Node*。

這是它給你一個有用的結構既是「之前，最開始」，並在列表中的「後 - 端」節點，這意味着你可以在執行所有的remove，insert_after和insert_before節點，根本不參考列表頭。在這方面，它就像詹姆斯的通告清單一樣，但與他不同的是，你也可以通過查找空指針來檢查末端 - 也沒有提及頭部。

檔下，「竅門我不需要玩」。

來源

2011-04-13 18:49:43

如何創建一個空的雙向鏈表？

回答

相關問題