### Create a doubly linked list from a singly

How can I create a doubly linked list?
I overall understand the concept of the singly linked list but the doubly is giving me a hard time.

I cannot for the life of me figure how to add a node at the beginning of the list or at the middle. I have looked at examples online but they don't really seem to help. I think I have it figured out for adding at the end of the list. I also am having a hard time linking the previous nodes to one another to create a 'doubly'. I say this because obviously I am doing something wrong because I can display my list forwards correctly but when I try to display it in reverse order it will only show my last element in the list.

Also, I have to make the node in main(). So no, I cannot use the OOP approach. I also cannot use the STL list.

Here is my code so far...

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185`` ``````#include using namespace std; int main() { struct ListNode { int value; ListNode *next; ListNode *prev; }; ListNode *head = nullptr; ListNode *tail = nullptr; ListNode *newNode = nullptr; ListNode *nodePtr = nullptr; ListNode *prevPtr = nullptr; ListNode *nextNode = nullptr; ListNode *temp = nullptr; char ch = 'q'; int val; do { cout << "a-add element to the list\n"; cout << "d-delete element in the list\n"; cout << "p-print this list\n"; cout << "q-quit\n"; cin >> ch; switch (ch) { case 'a': cout << "1-add element at beginning, 2-add at end, 3-add after an item\n"; cout << "choice: "; cin >> ch; cout << "Enter the value to be added: "; cin >> val; newNode = new ListNode; newNode->value = val; newNode->next = nullptr; newNode->prev = nullptr; if (ch == '1') //add element at beginning { if (head == nullptr) { head = newNode; tail = newNode; } else if (head != nullptr) { nodePtr = head; temp = head; newNode->prev = head; head = newNode; nodePtr->next = temp; while (nodePtr->next != nullptr) { nodePtr->prev = nodePtr; nodePtr = nodePtr->next; } } } else if (ch == '2') //add at end { if (head == nullptr) { head = newNode; tail = newNode; } else { nodePtr = head; while (nodePtr->next != nullptr) { nodePtr->prev = nodePtr; nodePtr = nodePtr->next; } nodePtr->next = newNode; tail->next = newNode; tail = newNode; } cout << "\nhead = " << head->value; cout << "\ntail = " << tail->value << endl; } else if (ch == '3') //add after an item { } break; case 'd': cout << "deleting...\n"; cout << "enter a value to be deleted "; cin >> val; if (head != nullptr) { if (head->value == val) { nodePtr = head->next; delete head; head = nodePtr; } else { nodePtr = head; while (nodePtr != nullptr && nodePtr->value != val) { prevPtr = nodePtr; nodePtr = nodePtr->next; } if (nodePtr != nullptr) { prevPtr->next = nodePtr->next; delete nodePtr; } } } else cout << "list is empty" << endl; break; case 'p': cout << "1-print forward, 2-print in reverse\n"; cout << "choice: "; cin >> ch; if (ch == '1') { nodePtr = head; while (nodePtr != nullptr) { cout << "elem: " << nodePtr->value << endl; nodePtr = nodePtr->next; } } else if (ch == '2') { nodePtr = tail; while (nodePtr != nullptr) { cout << "elem: " << nodePtr->value << endl; nodePtr = nodePtr->prev; } } break; case 'q': cout << "quitting...\n"; nodePtr = head; while (nodePtr != nullptr) { nextNode = nodePtr->next; cout << " deleting ... " << nodePtr->value << endl; delete nodePtr; nodePtr = nextNode; } break; default: cout << "invalid character -- please try again\n"; break; } } while (ch != 'q'); cout << endl; system("pause"); return 0; }``````
When dealing with linked lists, it is always a good idea to get out a piece of paper and a pencil and start drawing.

┌───┐   ┌───┐   ┌───┐   ┌───┐
head ──►│ 0 ├──►│ 1 ├──►│ 2 ├──►│ 3 ├──► nullptr
└───┘   └───┘   └───┘   └───┘

A doubly linked list also has pointers going back the the previous node:

┌───┐   ┌───┐   ┌───┐   ┌───┐
head ──►│ 0 ├──►│ 1 ├──►│ 2 ├──►│ 3 ├──► nullptr
nullptr ◄──┤   │◄──┤   │◄──┤   │◄──┤   │◄── tail
└───┘   └───┘   └───┘   └───┘

To add or remove nodes, work out how to adjust the arrows (pointers).

Hope this helps.
Topic archived. No new replies allowed.