An implementation of Doubly Linked List data structure.

DoublyLinkedList.cpp

#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();
	}
}