Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
An implementation of Doubly Linked List data structure.
#include <sstream>
#include <cstdlib>
#include <iostream>
using namespace std;
// Represents an element of the doubly linked list.
struct element
{
// The key of the element.
int key;
// Pointer to the previous element.
element* prev;
// Pointer to the next element.
element* next;
};
element* find(element* head, int key)
{
element* current = head;
while(current != NULL && current->key != key) {
current = current->next;
}
return current;
}
void insertIntoHead(element* &head, element* &tail, element* newEl)
{
newEl->next = head;
newEl->prev = NULL;
if(head == NULL) {
tail = newEl;
} else {
head->prev = newEl;
}
head = newEl;
}
void insertAfter(element* elem, element* &tail, element* newEl)
{
newEl->prev = elem;
newEl->next = elem->next;
elem->next = newEl;
if(newEl->next == NULL) {
tail = newEl;
} else {
newEl->next->prev = newEl;
}
}
void remove(element* &head, element* &tail, element* elem)
{
if(elem->prev == NULL && elem->next == NULL) {
// the element is the only element in the list
head = NULL;
tail = NULL;
delete elem;
return;
}
if(elem->prev == NULL) {
// the element is the head
head = elem->next;
head->prev = NULL;
} else {
elem->prev->next = elem->next;
}
if(elem->next == NULL) {
// the element is the tail
tail = elem->prev;
tail->next = NULL;
} else {
elem->next->prev = elem->prev;
}
delete elem;
}
void outputHeadToTail(element* head)
{
element* current = head;
while(current != NULL) {
cout << current->key << " ";
current = current->next;
}
}
void outputTailToHead(element* tail)
{
element* current = tail;
while(current != NULL) {
cout << current->key << " ";
current = current->prev;
}
}
int showMenu();
int getInt(string prompt);
int main()
{
element* head = NULL;
element* tail = NULL;
while(true) {
switch(showMenu()) {
case 1: // Insert into head
{
element* newEl = new element;
if(newEl == NULL) {
cout << "No more memory!" << endl;
break;
}
newEl->key = getInt("Insert a number: ");
insertIntoHead(head, tail, newEl);
break;
}
case 2: // Insert after an element
{
int key = getInt("Insert the key of the existing element: ");
element* elem = find(head, key);
if(elem == NULL) {
cout << "The element with key '" << key << "' does not exist!" << endl;
break;
}
element* newEl = new element;
if(newEl == NULL) {
cout << "No more memory!" << endl;
break;
}
newEl->key = getInt("Insert the new key: ");
insertAfter(elem, tail, newEl);
break;
}
case 3: // Remove element
{
int key = getInt("Insert a number: ");
element* elem = find(head, key);
if(elem == NULL) {
cout << "The element with key '" << key << "' does not exist!" << endl;
break;
}
remove(head, tail, elem);
break;
}
case 4: // Output entire list from head to tail
{
cout << "Entire list from head to tail:" << endl;
outputHeadToTail(head);
cout << endl;
break;
}
case 5: // Output entire list from tail to head
{
cout << "Entire list from tail to head:" << endl;
outputTailToHead(tail);
cout << endl;
break;
}
case 6: // Exit
{
return 0;
}
}
}
}
int showMenu()
{
cout << endl;
cout << "Doubly linked list - menu:" << endl;
cout << endl;
cout << "1) Insert into head" << endl;
cout << "2) Insert after an element" << endl;
cout << "3) Remove element" << endl;
cout << "4) Output entire list from head to tail" << endl;
cout << "5) Output entire list from tail to head" << endl;
cout << "6) Exit" << endl;
cout << endl;
int option;
do {
option = getInt("Choose: ");
} while(option<1 || option>6);
cout << endl;
return option;
}
int getInt(string prompt)
{
int output;
string input;
while(true) {
cout << prompt;
getline(cin, input);
stringstream ss(input);
if(ss >> output && !(ss >> input)) {
return output;
}
cin.clear();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.