How to change a single linked list into doubly linked list

Question

I'm having trouble changing this single linked list into a doubly linked list so that I can print a string of characters (the char s[] variable) backwards. I don't want to reverse the linked list, just print it in reverse, while using a doubly linked list. So how do I implement a doubly linked list with the following code?

#include <string.h>
#include <iostream>

using namespace std;


class node
{
  public:
  char data;
  node *next;
  node *prev;
};

int _tmain(int argc, _TCHAR* argv[])
{
    char s[] = "abcdefghijklmnopqrstuvwxyz";

    node *head; //start of list
    node *temp;
    node *current;

    head = new node;          // create the head of the linked list
    head->data = s[0];
    head->next = NULL;
    temp = head;   // get ready for the loop - save the head in temp - you are going to change temp in the loop

    for(size_t i=1; i < strlen(s); i++)      // create the rest of the linked list
    {
        current = new node;    // make a new node
        current->data = s[i];  // set it's data member
        current->next = NULL;
        temp->next = current;  // point to the new node
        temp = current;        // make temp point to current node (for next time through)
    }

    node *ptr = head;    // set a ptr to head, then increment the pointer

    while (ptr != NULL)
    {
        cout << ptr->data; // print out the linked list
        ptr = ptr->next;   // increment the linked list
    }

    cout << endl;
    system("pause");
    return 0;
}

@PankajBansal How do I implement a doubly linked list here and print the char s[] backwards — T-Bird
You're not initializing any of the prev pointers on newly created nodes so far. That would be a good place to start ... — dragosht
@dragosht I knew I would need that, I'm not sure where to use it though. — T-Bird
temp is initialised on the heap outside the loop then immediately overwritten by head. That's a memory leak. Also, initialise your prev pointers. — Andy Brown

T-Bird T-Bird · Accepted Answer · 2015-02-18T09:50:00

#include <string.h>
#include <iostream>
using namespace std;

class node
{
public:
   char data;
   node *next;
   node *prev;
   node(char Data, node* Prev, node* Next);
};

node::node(char Data, node* Prev, node* Next)
    : data(Data), prev(Prev), next(Next)
{
    if (prev)prev->next = this;
    if (next)next->prev = this;
}

int _tmain(int argc, _TCHAR* argv[])
{
    char s[] = "abcdefghijklmnopqrstuvwxyz";

    node *temp;
    node *current;

    node *head; // ptr to head of list
    node *tail; // ptr to tail of list

    // call constructor and initialize first node 
    head = tail = new node(s[0], NULL, NULL);

    for (size_t i = 1; i < strlen(s); i++) // create the rest of the linked list
    {
        tail = new node(s[i], tail, NULL);
    }

    node *ptr = head; // set a ptr to head, then you are going to "increment" the pointer

    while (ptr != NULL)
    {
        cout << ptr->data; // print out the linked list
        ptr = ptr->next;   // increment the linked list
    }

    node *ptr1 = tail; // set a ptr to tail, then "decrement" the pointer form z to a
    cout << endl;

    while (ptr1 != NULL)
    {
        cout << ptr1->data; // print out the linked list
        ptr1 = ptr1->prev; // decrement the linked list
    }

    cout << endl << endl;
    system("pause");
    return 0;
}

How to change a single linked list into doubly linked list

1 Answers