今天武林技術頻道小編在這里，使用簡潔的語言，讓您了解雙向循環(huán)列表的實現(xiàn)，并對這種結構進行了深入的分析，讓我們像對待藝術一樣對待編寫代碼，希望對你學習有幫助！
雙向循環(huán)鏈表，即每個節(jié)點都擁有一前一后兩個指針且頭尾互鏈的鏈表。各種鏈表的簡單區(qū)別如下：
單向鏈表：基本鏈表；
單向循環(huán)鏈表：不同于單向鏈表以 NULL 判斷鏈表的尾部，單向循環(huán)鏈表的尾部鏈接到表頭，因此當?shù)僮鞯奖眍^前即是尾部；
雙向鏈表：比單向鏈表多出指向前一個節(jié)點的指針，但實際上使用雙向鏈表時很少使用不循環(huán)的；
雙向循環(huán)鏈表：相對于單向循環(huán)鏈表，雙向循環(huán)鏈表可從頭部反向迭代，這在鏈表長度很大且需要獲取、插入或刪除靠近鏈表尾部元素的時候十分高效。單向循環(huán)列表只能從表頭正向迭代，執(zhí)行的時間大于從反向迭代。
node.h
?
?
?
/*
* 節(jié)點類型。三個成員分別是：指向前一個節(jié)點的指針，元素本身，指向后一個節(jié)點的指針。
*/
class Node {
public:
??? int element;
??? Node *next;
??? Node *previous;
??? Node(int element, Node *next, Node *previous) {
??????? this->element = element;
??????? this->next = next;
??????? this->previous = previous;
??? }
};
linkedlist.h:
#include "node.h“
struct LinkedList {
??? LinkedList();
??? void addFirst(int);
??? void addLast(int);
??? void add(int index, int element);
??? int getFirst();
??? int getLast();
??? int get(int);
??? int removeFirst();
??? int removeLast();
??? int remove(int);
??? void iterate();
private:
??? Node *header;
??? int size;
};
linkedlist.cpp:
#include "linkedlist.h"
#include <iostream>
using std::cout;
/*
* 構造方法。
* 生成一個空的節(jié)點介于表頭和表尾之間，初始前后指針都指向自己。
*/
LinkedList::LinkedList() {
??? header = new Node(NULL, NULL, NULL);
??? header->next = header;
??? header->previous = header;
??? size = 0;
}
/*
* 在鏈表頭部添加一個元素。
* 生成一個新的節(jié)點，向前指向空節(jié)點，向后指向原來空節(jié)點的下一個節(jié)點，即原來的第一個節(jié)點。
* 空節(jié)點向后指向此節(jié)點，原來的第一個節(jié)點向前指向此節(jié)點。
*/
void LinkedList::addFirst(int i) {
??? header->next = new Node(i, header->next, header);
??? header->next->next->previous = header->next;
??? ++size;
}
/*
* 在鏈表最后添加一個元素。
* 生成一個新的節(jié)點，向前指向原來空節(jié)點的前一個節(jié)點，即原來的最后一個節(jié)點，向后指向空節(jié)點。
* 原來的最后一個節(jié)點向后指向此節(jié)點，空節(jié)點向前指向此節(jié)點。
*/
void LinkedList::addLast(int i) {
??? header->previous = new Node(i, header, header->previous);
??? header->previous->previous->next = header->previous;
??? ++size;
}
/*
* 在指定的索引前插入一個元素。0 <= 索引 <= 鏈表長度。
* 如果索引值小于鏈表長度的一半，向后（正向）迭代獲取索引值位置的節(jié)點，反之則向前（反向）。
* 生成一個新的節(jié)點，向前指向原來這個位置的節(jié)點的前一個節(jié)點，向后指向原來這個位置的節(jié)點。
* 原來這個位置的節(jié)點的前一個節(jié)點向后指向此節(jié)點，原來這個位置的節(jié)點向前指向此節(jié)點。
* （在指定的索引刪除一個元素實現(xiàn)方法類似）
*/
void LinkedList::add(int index, int i) {
??? if(index > size || index < 0) {
??????? cout << "Exception in add(): Index out of bound." << '/n';
??? return;
??? }
??? Node *entry;
??? if(index < size / 2) {
??????? entry = header->next;
??????? for(int i = 0; i < index; ++i)
??????????? entry = entry->next;
??? }
??? else {
??????? entry = header;
??????? for(int i = size; i > index; --i)
??????????? entry = entry->previous;
??? }
??? entry->previous->next = new Node(i, entry, entry->previous);
??? entry->previous = entry->previous->next;
??? ++size;
}
/*
* 獲取鏈表第一個元素。
* 空節(jié)點向后指向的節(jié)點即是第一個元素。
*/
int LinkedList::getFirst() {
??? if(!size)
??????? cout << "Exception in getFirst(): List is empty." << '/n';
??? return header->next->element;
}
/*
* 獲取鏈表最后一個元素。
* 空節(jié)點向前指向的節(jié)點即是最后一個元素。
*/
int LinkedList::getLast() {
??? if(!size)
??????? cout << "Exception in getLast(): List is empty." << '/n';
??? return header->previous->element;
}
/*
* 刪除并返回鏈表第一個元素。
* 鏈表第二個節(jié)點向前指向空節(jié)點，空節(jié)點向后指向第二個節(jié)點。
*/
int LinkedList::removeFirst() {
??? int remove = header->next->element;
??? header->next->next->previous = header;
??? header->next = header->next->next;
??? --size;
??? return remove;
}
/*
* 刪除并返回鏈表最后一個元素。
* 鏈表倒數(shù)第二個節(jié)點向后指向空節(jié)點，空節(jié)點向前指向倒數(shù)第二個節(jié)點。
*/
int LinkedList::removeLast() {
??? int remove = header->previous->element;
??? header->previous->previous->next = header;
??? header->previous = header->previous->previous;
??? --size;
??? return remove;
}
/*
* 用來輸出所有元素的迭代方法。
*/
void LinkedList::iterate() {
??? if(!size) {
??????? cout << "Exception in iterate(): List is empty." << '/n';
??????? return;
??? }
??? for(Node *entry = header->next; entry != header; entry = entry->next)
??????? cout << entry->element << " ";
??? cout << '/n';
}
?以上就是關于如何用C++實現(xiàn)雙向循環(huán)鏈表的介紹，隨著IT行業(yè)的高速發(fā)展，目前這行對于程序員的要求也是很高的，大家要多多學習才能有所進步！
