-
Linked Lists Question
Hello, I have created a linked list and am wanting to print out information from it in reverse order... I'm not sure how to go about this. Could someone help me.... I'm not looking for code, just in words if anyone knows could explain how I might go about this
So far I've been thinking.... I will make a function called print_reverse( pointer ) somthing like that and it will take in the pointer to the top of my linked list
I can move the pointer all the way down the linked list till it reaches a null... which is the end, I can print this, but I have no way of moving the pointer back to print the one before it
Any ideas on this would be greatly appreciated
Thank You
-
Three methods:
1: Use a recursive function to traverse the list, and print the node after the recursive call returns.
+ Very easy to implement.
- Doesn't work on circular lists.
- Very large lists will run your program out of stack space.
2: Use some nested loops, comparing pointers.
+ It'll work.
- It's not the most efficient way to do it, but this is probably what you'll end up with.
3: Use a double linked list.
+ It's also easy to implement and use.
+ I like them.
- It takes a tiny bit more memory for the extra pointer per node.
4: Reverse the list, then print it in the new order.
+ It works.
- You have to know how to reverse a list.
I'm sure someone will be along with a few more, but there are some ideas for you to kick around.
Quzah.
-
Thanks for the tips quzah, I went with door number 4 and attempted to write my own function that would reverse my linked list. Its my first time doing this, this is what I wrote:
Code:
STUDENT* rev_list( STUDENT* stud ) {
STUDENT * ptr;
while( stud != NULL ) {
ptr = malloc(sizeof(STUDENT));
strcpy( (ptr -> name) , (stud -> name) );
(ptr -> ID) = (stud -> ID);
stud = stud -> studentPtr; /*Moves pointer stud to next
node in original list */
ptr -> studentPtr = rev_top;
rev_top = ptr;
}
}
where my struct data type student is this:
Code:
typedef struct student {
char name[11]; /* Students Name **************/
int ID; /* Student's ID number ********/
struct student* studentPtr; /* Pointer to next student ****/
} STUDENT;
I was wondering if I have created unneccassary garbage doing this? I think what I have done now is created to linked-lists (2 stacks) I don't think creating the reversed one affected my original one.... am I correct in thinking this?
Thank You
-
Correct. That's the easiest way to reverse a list, since you typically prepend data in single linked lists. So you just be sure to free the old list if you don't want it any more. (Just remember, you have 2 lists, so you have to be sure to free 2 lists also.)
Quzah.
-
Quzah I am impressed at how much you know about this C stuff. I posted this somewhere else but I wanted to ask you, it's similar to what we were discussing here, so I'm reposting it here, maybe you know something about this. Thanks for your help
repost:
I have a linked list. Each node has 2 pieces of data (a name and a number) plus the pointer to the next node.
One of the pieces of data is an arbitrary number. I need to somehow create a function that can print out the names in the ascending order of their corresponding numbers.
for example if:
Code:
NODE 1: brad,5
NODE 2: joe, 7
NODE 3: ralph, 2
then my function should print out:
does anyone know how I might go about doing this, I'm new to link lists and this is confusing for me, I'm not asking for code just ideas.