Linked List Help

Question

DCvonB 0 Newbie Poster

14 Years Ago

Hello,

I am trying to create a doubly linked list that will print the entered input in the original order and then print it in the reverse order.

Earlier I was able to get it to print the list twice, but the second time was not in the reverse order. Now it only prints the last element and I am not sure where the mistake is. Any help would be greatly appreciated as I have been trying to fix it for hours without success.

/*
 Write a program so that it displays the movie list both in the original  order and in reverse order. One approach is to modify the linked-list 
 definition so that the list can be traversed in both directions. 
 Another approach is to use recursion.
*/ 

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#define TSIZE 45 

struct film {
	char title[TSIZE];
	int rating; 
	struct film* next ;
	struct film* previous ;
} ; 

int main(void) {

/* points to nextstruct in list */

	struct film* head = NULL ;
	struct film* prev ;
	struct film* current ; 
	char input[TSIZE] ;
 
	/* Gather and store information*/ 
	puts("Enter first movie title:") ; 

	while (gets(input) != NULL && input[0] != '\0'){
 
		current = malloc(sizeof(struct film)) ; 

		if (head == NULL) { /* first structure */
			head = current; 
		}

		else { /* subsequent structures */

			current->previous = head ;

			//prev->next = current ; 
			head->next = current ;
			head = current ;
		}

		current->next = NULL ; 
		current->previous = NULL ;
		strcpy(current->title, input) ; 
		puts("Enter your rating <0-10>:") ; 
		scanf("%d", &current->rating) ; 

		while(getchar() != '\n')
			continue ; 

		puts("Enter next movie title (empty line to stop):") ; 
		prev = current ;

	} 

	/* Show list of movies */	
	if (head == NULL) {
		printf("No data entered. ") ;
	}
   
	else {
		printf ("Here is the movie list:\n") ;
	}

	current = head ;

	/* print in original order */

	while (current != NULL) {
		printf("1Movie: %s Rating: %d\n", current->title, current->rating) ;
		current = current->next;
	} 

	/* print in reverse order */
	while (head != NULL) {
		printf("2Movie: %s Rating: %d\n", head->title, head->rating);
		head = head->previous;
	} 

	/* free allocated memory */
	current = head; 

	while (current != NULL) {
		free(current); 
		current = current->next;
	}

	printf("Bye!\n"); 

	return 0;
}

c

4 Contributors
10 Replies
303 Views
1 Day Discussion Span
Latest Post 14 Years Ago Latest Post by DCvonB

All 10 Replies

shah1248 5 Light Poster

14 Years Ago

You first while loop is wierd. You should not be moving head at all. You should only be moving current and prev.

thomas_naveen 105 Junior Poster

14 Years Ago

You are having a problem in line 32-36.

Instead of iterating through the linked list and adding your element at the end, you are pointing your head node to the new node and the new node points to your head.

All the intermediate nodes are lost. You are left with a LL of two nodes.

shah1248 5 Light Poster

14 Years Ago

Try changing line 35 to prev->next = current; and add the following after line 29 prev = current; And change your last loop to print reverse to use current instead of head and initialize current to prev before the start of the loop.

On the side note, I would call prev as tail as that's how you intend to use it.

Edited 14 Years Ago by shah1248 because: n/a

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

anup375 -2 Newbie Poster · Answer 1 · 2010-03-02T00:27:03+00:00

While playing with Linked List, you always have to have a pointer pointing to the start of the link. You should not change the pointer at any time during the program. Generally, 'head' is used to point the starting of the linked list. If you do not have a pointer to the start of the list, how are you going to process the list.

Also your linked list is messed up.

if (head == NULL) { /* first structure */
   head = current;                           
}
else { /* subsequent structures */
       current->previous = head ;
       //prev->next = current ;
       head->next = current ;
       head = current ;         //  this is wrong, you should not change the head pointer.
}
current->next = NULL ;
current->previous = NULL ;   // In the else loop, you are initializing the current->previous pointer and here you make it NULL. I doubt you are creating a doubly linked list.

DCvonB 0 Newbie Poster · Answer 2 · 2010-03-02T12:13:31+00:00

Thank you for the replies.

Its still not 100% correct yet. It prints the initial input followed by the next input (as it should) and then prints the previous input (the initial input)

Example output:
Here is the movie list:
1Movie: t1 Rating: 1
1Movie: t2 Rating: 2
2Movie: t1 Rating: 1
Bye!

I was hoping to get it to print like this:
Here is the movie list:
1Movie: t1 Rating: 1
1Movie: t2 Rating: 2
2Movie: t2 Rating: 2
2Movie: t1 Rating: 1
Bye!

Any help would be greatly appreciated

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#define TSIZE 45 

struct film {
	char title[TSIZE];
	int rating; 
	struct film* next ;
	struct film* previous ;
} ; 

int main(void) {
	
	 /* points to nextstruct in list */
	struct film* head = NULL;
	struct film* prev ;
	struct film* current; 
	char input[TSIZE];
			 
	/* Gather and store information*/ 
	puts("Enter first movie title:"); 
	
	while (gets(input) != NULL && input[0] != '\0'){
	 
		current = malloc(sizeof(struct film)) ; 
		
		if (head == NULL) {	/* first structure	*/
			head = current; 
		}
		
		else {	/* subsequent structures */
			
			current->previous = head ;
			head->next = current ;
		}
		
		current->next = NULL; 
		strcpy(current->title, input); 
		puts("Enter your rating <0-10>:"); 
		scanf("%d", &current->rating); 
		
		while(getchar() != '\n')
			continue; 
		puts("Enter next movie title (empty line to stop):"); 
		prev = current;

	} 
	
	/* Show list of movies	*/

	if (head == NULL) {
		printf("No data entered. ");
	}
		   
	else {
		printf ("Here is the movie list:\n");
	}
	current = head;
	
	/* print in original order */
	while (current != NULL) {
		printf("1Movie: %s Rating: %d\n", current->title, current->rating);
	
		current = current->next ;
	} 

	/* print in reverse order */
	while (head != NULL) {
		printf("2Movie: %s Rating: %d\n", head->title, head->rating);
		
		head = head->previous;
	} 
	
	/* free allocated memory */	
	current = head; 
	while (current != NULL) {
        struct film* currentFilm = current;
        current = current->next;
        free(currentFilm); 
    }
	
	printf("Bye!\n"); 
	return 0;

}

DCvonB 0 Newbie Poster · Answer 3 · 2010-03-02T13:24:58+00:00

Thanks again for your help.

It is so close. Along with changing parts of the code with the help of the comments above, I added a pointer to save the last location of 'current->next' before it becomes null at the end of the list to help transverse back to the head (see comments).

But now it will print all input using 'current->next' but will only print the last and first input when printing with 'current->previous.

Example:
Here is the movie list:
1Movie: t1 Rating: 1
1Movie: t2 Rating: 2
1Movie: t3 Rating: 3
1Movie: t4 Rating: 4
1Movie: t5 Rating: 5
2Movie: t5 Rating: 5
2Movie: t1 Rating: 1
Bye!

Again, your help is appreciated!

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#define TSIZE 45 

struct film {
	char title[TSIZE];
	int rating; 
	struct film* next ;
	struct film* previous ;
} ; 

int main(void) {
	
	 /* points to nextstruct in list */
	struct film* head = NULL;
	struct film* prev ;
	struct film* current; // added to try and save the last location of pervious
	struct film* last;
	char input[TSIZE];
			 
	/* Gather and store information*/ 
	puts("Enter first movie title:"); 
	
	while (gets(input) != NULL && input[0] != '\0'){
	 
		current = malloc(sizeof(struct film)) ; 
		
		if (head == NULL) {	/* first structure	*/
			head = current; 
			prev = current; //added thanks to shah1248 comments
		}
		
		else {	/* subsequent structures */
			
			current->previous = head ;
			prev->next = current; //added thanks to shah1248 comments
		}
		
		current->next = NULL; 
		strcpy(current->title, input); 
		puts("Enter your rating <0-10>:"); 
		scanf("%d", &current->rating); 
		
		while(getchar() != '\n')
			continue; 
		puts("Enter next movie title (empty line to stop):"); 
		prev = current;

	} 
	
	/* Show list of movies	*/
	if (head == NULL) {
		printf("No data entered. ");
	}
		   
	else {
		printf ("Here is the movie list:\n");
	}
	current = head;
	
	/* print in original order */
	while (current != NULL) {
		printf("1Movie: %s Rating: %d\n", current->title, current->rating);
	
		last = current ; //save last location before NULL. Used to print revers
		current = current->next ;
	} 

	current = last ; 
	/* print in reverse order */
	while (current != NULL) {
		printf("2Movie: %s Rating: %d\n", current->title, current->rating);
		
		current = current->previous;
	} 
	
	/* free allocated memory */	
	current = head; 
	while (current != NULL) {
        struct film* currentFilm = current;
        current = current->next;
        free(currentFilm); 
    }
	
	printf("Bye!\n"); 
	return 0;

}

shah1248 5 Light Poster · Answer 4 · 2010-03-02T23:22:31+00:00

The problem is in your first while loop (after else), you are setting previous of all the new nodes to the head. So after printing the last node, when you get its previous it takes you to the head.

You should change head to prev.

anup375 -2 Newbie Poster · Answer 5 · 2010-03-03T00:27:44+00:00

This will solve your problem.... Check the 'else' loop...

if (head == NULL) { 
    head = current;
    prev = current; //added thanks to shah1248 comments
}
 
else {  
   current->previous = prev ;  //   ****this should be changed*****
   prev->next = current; //added thanks to shah1248 comments
   prev=current; //   ****this should be added***** 

}

shah1248 5 Light Poster · Answer 6 · 2010-03-03T01:59:49+00:00

This will solve your problem.... Check the 'else' loop...

if (head == NULL) { 
    head = current;
    prev = current; //added thanks to shah1248 comments
}
 
else {  
   current->previous = prev ;  //   ****this should be changed*****
   prev->next = current; //added thanks to shah1248 comments
   prev=current; //   ****this should be added***** 

}

The first line you added is exactly what I said in the previous post.

The second change you suggested is not needed since he is already doing prev=current outside the loop since it applies to if part as well as else part (could take out from if part too).

DCvonB 0 Newbie Poster · Answer 7 · 2010-03-03T02:07:00+00:00

Alright, this issue is solved. Thank you for all the help!

I changed head to prev and had to set the head to NULL when reversing the input with the line head->previous = NULL ;.

Here is the code. I hope it can help someone else:

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#define TSIZE 45 
 
struct film {
	char title[TSIZE];
	int rating; 
	struct film* next ;
	struct film* previous ;
} ; 
 
int main(void) {
 
	 /* points to nextstruct in list */
	struct film* head = NULL;
	struct film* prev ;
	struct film* current; // added to try and save the last location of pervious
	struct film* last;
	char input[TSIZE];
 
	/* Gather and store information*/ 
	puts("Enter first movie title:"); 
 
	while (gets(input) != NULL && input[0] != '\0'){
 
		current = malloc(sizeof(struct film)) ; 
 
		if (head == NULL) {	/* first structure	*/
			head = current; 
			prev = current; //added thanks to shah1248 comments
			head->previous = NULL ;
		}
 
		else {	/* subsequent structures */
 
			current->previous = prev ;
			prev->next = current; //added thanks to shah1248 comments
		}
 
		current->next = NULL; 
		strcpy(current->title, input); 
		puts("Enter your rating <0-10>:"); 
		scanf("%d", &current->rating); 
 
		while(getchar() != '\n')
			continue; 
		puts("Enter next movie title (empty line to stop):"); 
		prev = current;
	} 
 
	/* Show list of movies	*/
	if (head == NULL) {
		printf("No data entered. ");
	}
 
	else {
		printf ("Here is the movie list:\n");
	}
	current = head;
 
	/* print in original order */
	while (current != NULL) {
		printf("1Movie: %s Rating: %d\n", current->title, current->rating);
		last = current ; //save last location before NULL. Used to print revers
		current = current->next ;
	} 
 
	current = last ; 
	/* print in reverse order */
	while (current != NULL) {
		printf("2Movie: %s Rating: %d\n", current->title, current->rating);
		current = current->previous;
	} 
 
	/* free allocated memory */	
	current = head; 
	while (current != NULL) {
        struct film* currentFilm = current;
        current = current->next;
        free(currentFilm); 
    }
 
	printf("Bye!\n"); 
	return 0;
}

Linked List Help

Recommended Answers Collapse Answers

All 10 Replies

Recommended Answers