Doubly Linked List

[pooshi]

Hey Everyone, it's been a while but I am back and needs some assistance. I have a linked list and I want to take it to a doubly linked list so I can print the alphabet backwards using my *prior but can seem to figure it out. Any ideas?

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

class node
{
  public:
  char data;
  node *next;
  node *prior;
  node();
};

node::node( )
{
	data = ' ';
	next = NULL;
	prior = NULL;
}

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

	node *head; // pointer to front
	node *tail; // pointer to back
	node *temp;
	node *temp1;
	node *current;
	node *prior;

	head = new node; // create the head of the linked list
	head->data = s[0];
	head->next = NULL;
	temp = head;

	tail = new node; // create the tail of the linked list
	tail->data = s[0];
	tail->next = NULL;
	temp1 = tail;

	// This creates the alphabet but I am haing a hard time trying to figure out
	// how to implement tail so I can traverse the alphabet backwards.

	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)
	}

	// Prints alphabet 
	node *ptr = head;    // set a ptr to head
	while (ptr != NULL)
	{
		cout << ptr->data; // print out the linked list
		ptr = ptr->next;   // increment the linked list
	}

	// Prints alphabet backwards
	node *ptr1 = head;    // set a ptr to head
	while (ptr1 != NULL)
	{
		cout << ptr1->data; // print out the linked list
		ptr1 = ptr1->next;   // increment the linked list
	}

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

Thanks,

[D80DSL3A]

When you create the 1st node it is both head and tail of the list:

head = new node;
head->data = s[0];
head->next = NULL;
head->prior = NULL;
tail = head;

Each node that follows in the list becomes the new tail. In your for loop:

current = new node;    // make a new node
current->data = s[i];  // set it's data member
current->next = NULL;
current->prior = tail;
tail->next = current;
tail = current;

Note that the code for all of this can be simplified a lot by adding this constructor to your node structure:

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

The 5 lines for creating the 1st node can become 1 line:
head = tail = new node(s[0], NULL, NULL);
and the 6 lines in the for loop become:

tail = new node(s[i], tail, NULL);

EDIT: You never made use of the prior data member in your node structure. You will need to use it to print the list backwards. Presently both of your while loops are printing the list forward.

[pooshi]

Thanks fun2code. This is what I got and it works due to your input and advice.

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

class node
{
  public:
  char data;
  node *next;
  node *prior;
  node( char, node*, node* );
};
// use constructor to initialize members of Class node
node::node(char Data, node* Prior, node* Next ): data(Data), prior(Prior), next(Next) 
{
    if(prior)prior->next = this;
    if(next)next->prior = this;
}

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

	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 << "\n\nThe alphabet reversed using prior ptr:" << endl; // output 2 empty lines and add a comment
	while ( ptr1 != NULL )
	{
		cout << ptr1->data; // print out the linked list
		ptr1 = ptr1->prior; // decrement the linked list
	}

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

Thanks again.

[D80DSL3A]

You're welcome. One more thing...
You ought to delete the nodes since they were dynamically allocated. One more while loop can do this. Just iterate through the list and delete each node as you go (but save a pointer to the next node first).

1) Try writing a function to insert a new node within the list! The constructor I gave makes this easy.

2) Try writing a function to remove a node from within the list. A destructor for the node class which assigns the links across the node to be deleted (and then deletes the node) would be useful.

[pooshi]

Alright, I will give it a go. You will be hearing form me again, I'm sure.
Thanks again.