C++ - Doubly Linked List
Singly Linked List, Doubly Linked List, Singly Linked Circular List and Doubly Linked Circular List are an important data structure used in C++ applications.
I have given here the sample code for doubly linked list, filling elements and traversal in forward and backward direction. I have NOT given the code for deleting the nodes. It is easy to implement by changing the insert functions.
Source Code
// Program for doubly linked list
#include <iostream>
#include <string>
struct DLinkList
{
std::string data;
DLinkList *next;
DLinkList *prev;
DLinkList() : data(""), next(NULL), prev(NULL) { }
DLinkList(const char *value) : data(value), next(NULL), prev(NULL) { }
DLinkList* InsertNext(const char *data)
{
DLinkList *node = new DLinkList(data);
if(this->next == NULL)
{
// Easy to handle
node->prev = this;
node->next = NULL; // already set in constructor
this->next = node;
}
else
{
// Insert in the middle
DLinkList *temp = this->next;
node->prev = this;
node->next = temp;
this->next = node;
temp->prev = node;
// temp->next does not have to be changed
}
return node;
}
DLinkList* InsertPrev(const char *data)
{
DLinkList *node = new DLinkList(data);
if(this->prev == NULL)
{
node->prev = NULL; // already set on constructor
node->next = this;
this->prev = node;
}
else
{
// Insert in the middle
DLinkList *temp = this->prev;
node->prev = temp;
node->next = this;
this->prev = node;
temp->next = node;
// temp->prev does not have to be changed
}
return node;
}
void TraverseFront(DLinkList *node = NULL)
{
if(node == NULL)
node = this;
std::cout << "\n\nTraversing in Forward Direction\n\n";
while(node != NULL)
{
std::cout << node->data;
std::cout << "\n";
node = node->next;
}
}
void TraverseBack(DLinkList *node = NULL)
{
if(node == NULL)
node = this;
std::cout << "\n\nTraversing in Backward Direction\n\n";
while(node != NULL)
{
std::cout << node->data;
std::cout << "\n";
node = node->prev;
}
}
};
int main()
{
DLinkList *node1 = new DLinkList("ONE");
DLinkList *node3 = node1->InsertNext("THREE");
DLinkList *node2 = node3->InsertPrev("TWO");
DLinkList *node5 = node3->InsertNext("FIVE");
DLinkList *node4 = node5->InsertPrev("FOUR");
node1->TraverseFront();
node5->TraverseBack();
std::cout << "\n";
return 0;
}
Output
Traversing in Forward Direction
ONE
TWO
THREE
FOUR
FIVE
Traversing in Backward Direction
FIVE
FOUR
THREE
TWO
ONE
|
|