Data structures - reversing doubly linked lists

[bklearner]

code not working

#include<iostream>
using namespace std;

typedef struct node{

	int data;
	struct node *next;
	struct node *previous;
}mynode;

mynode *head,*temp,*current,*tail;

void add(int data);

int main() {
	
	head=NULL;
	tail=NULL;
	add(1);
	cout<<"added 1"<<endl;
	add(2);
	add(3);
	add(4);
	
}

void add(int data) {

	
	temp=(mynode*)malloc(sizeof(mynode));
	temp->next=NULL;
	temp->previous=NULL;
	
	if(head == NULL) {
		head=temp;
		tail = temp;
		temp->data=data;
		cout<<"Here "<<temp->data<<endl;
	}

	
	else {
		 current=head;			
		 while(current->next==NULL) {	
				current->next=temp;
				temp->previous=current;
				temp->data=data;
				cout<<"Now "<<temp->data<<endl;
				tail=temp;
				current=current->next;
		}
				
	}
	
				
}

[daviddoria]

What is wrong with it? Give us a sample input, current output, and expected output. Does it crash? If so, have you used a debugger to track down where?

Dave

[bklearner]

Here 1
added 1
Now 2
Now 2
This is the o/p I get..

[daviddoria]

I haven't looked closely, but you should definitely use 'new' instead of 'malloc'. 'malloc' is deprecated in c++.

[bandtank]

I can't follow your algorithm without drawing a flow chart. You need to comment your code.

[bandtank]

I haven't looked closely, but you should definitely use 'new' instead of 'malloc'. 'malloc' is deprecated in c++.

Similarly, you also need to free the memory at the end of the function using delete.

[daviddoria]

I haven't compiled myself, but this is very confusing:

typedef struct node{

	int data;
	struct node *next;
	struct node *previous;
}mynode;

mynode *head,*temp,*current,*tail;

First, why have you used a typedef? Second, you seem to have declared an object named mynode, then tried to declare things (head,temp,etc) of type mynode. Shouldn't they be type 'node'?

[nbaztec]

First, why have you used a typedef? Second, you seem to have declared an object named mynode, then tried to declare things (head,temp,etc) of type mynode. Shouldn't they be type 'node'?

No it's fine OP has typdef-ed node to bye mynode. Though it's uncalled for when he can just declare the struct as mynode.

[bandtank]

No it's fine OP has typdef-ed node to bye mynode. Though it's uncalled for when he can just declare the struct as mynode.

Ah, I see. I was confused by that as well.

struct node{
    int data;
    node *next;
    node *previous;
};

node *head,*temp,*current,*tail;

I would change it to that for readability.

[nbaztec]

Try changing this:

else {
		 current=head;			
		 while(current->next==NULL) {	
				current->next=temp;
				temp->previous=current;
				temp->data=data;
				cout<<"Now "<<temp->data<<endl;
				tail=temp;
				current=current->next;
		}

to this:

else {	
  		 tail->next=temp;
		 temp->previous=current;
		 temp->data=data;
  		 cout<<"Now "<<temp->data<<endl;
		 tail=temp;
		}

[Kanoisa]

Ok i dont know if this s really the best way to help here but i have a couple of classes i made a while ago.

one C_Day is a class which holds a list of tasks to be done on that day which are stored as a linked list. when adding an item to the list the list is sorted in order of smallest to largest (schedule time in minutes) the list is doubly linked like yours.

Hopefully you can dissassemble what you need and it might help to see sorting the list as well.

Find attached my project which is a visual studio2008 project, if you dont have visual studio the files of interest are C_Day.h and C_Day.cpp (where the linked list stuff is happening) and C_Task.h and .cpp which is the class my linked list stores instances of. organiserDosV2.3.cpp is the main program entry point

please bear in mind this project is still a work in progress i have found no bugs from what testing i have done but i have not yet implimented all the functionality i wanted but the bits of interest to you are fine

Hope this helps you

[daviddoria]

Is this for an assignment? If not, surely there is a function in the STL called something like "reverse()" that operate on std::list. Have you looked into this?

[mrnutty]

I haven't compiled myself, but this is very confusing:

typedef struct node{

	int data;
	struct node *next;
	struct node *previous;
}mynode;

mynode *head,*temp,*current,*tail;

First, why have you used a typedef? Second, you seem to have declared an object named mynode, then tried to declare things (head,temp,etc) of type mynode. Shouldn't they be type 'node'?

The main reason for doing this is backward compatibility. In C, you have to use the
keyword struct before declaring a struct variable. So usually, programmer use typedefs
to simply things and make things easier. But In C++, thats not required.

[Taywin]

Not sure why you need to initiate next/previous for temp when you just created. And why do you assign variable 'tail' outside for??? You automatically know that 'tail' is 'head' in doubly linked list! Also, if you don't know what the last element in the list before head, just use head->previous and you get it in doubly linked list.

By the way, your topic said it is 'reversing doubly linked list', but your code has only 'add'. Does this mean to add it reversely? Or just add???

Here is the code I fixed it for you. Hope it gives you some ideas.

#include<iostream>
using namespace std;

typedef struct node {
  int data;
  struct node *next;
  struct node *previous;
}mynode;

mynode *head,*temp,*current,*tail;

void add(int data);

int main() {
	
  head=NULL;
  add(1);
  cout<<"added 1"<<endl;
  add(2);
  add(3);
  add(4);

}

// add it at tail
void add(int data) {

  temp=(mynode*)malloc(sizeof(mynode));
  temp->data=data;

  if(head == NULL) {  // newly create doubly linked list
    temp->next=temp;      // point to itself because of doubly linked list
    temp->previous=temp;  // point to itself because of doubly linked list
    head=temp;
    cout<<"Here "<<temp->data<<endl;
  }
  else {  // already exist, just need to insert the node at a proper location
    tail=head->previous;  // get the last node in the list before loop
    tail->next=temp;
    temp->previous=tail;
    temp->next=head;
    head->previous=temp;
//    if you want to add it reversely, move your head up to the temp here
//    head=temp;  // move head up to temp
    cout<<"Now "<<temp->data<<endl;
  }
}

One note here, you do not need to traversal the list when add if it is a doubly linked list unless you are doing a search. Do not confuse doubly linked list with singly linked list even though their implementations are close.