linked list

[junky_fellow]

Consider a singly-linked list. Each node has a structure,

struct node {
char c;
struct node *next;
};

Each of the nodes contain an alphabetic character.
Can anybody suggest a way to print the characters in reverse order.

thanx in advance.....

 

[Morris Dovey]

Consider a singly-linked list. Each node has a structure,

struct node {
char c;
struct node *next;
};

Each of the nodes contain an alphabetic character.
Can anybody suggest a way to print the characters in reverse order.

Consider recursion.

 

[Richard Heathfield]

Consider a singly-linked list. Each node has a structure,

struct node {
char c;
struct node *next;
};

Each of the nodes contain an alphabetic character.
Can anybody suggest a way to print the characters in reverse order.

Consider a stack. Each node has a structure,

struct stack {
char c;
struct stack *next;
};

Each of the stack nodes contains an alphabetic character.

Start at the top of the list, and copy each node's character into a string,
since strings are by far the best way of representing characters. Now take
each character from the string, and push it onto the stack. When you're
done, empty the string, and then simply pop each character /off/ the stack
again, and feed it into the string (at the end, each time).

Now reverse the string:

void revstr(char *s) { if(s && *s) { char *t = s + strlen(s) - 1; while(t >
s) { char c = *t; *t-- = *s; *s++ = c; } } }

Now reverse it again, just to be absolutely sure that it's definitely,
definitely reversed. (This is quite simple - just call revstr again.)

Finally, loop through the string, placing each character on the standard
output device.

Simple!

 

[Richard Heathfield]

Consider recursion.

And I thought /I/ was being a little cruel. Consider just how fragile
recursion is, in this context. For example, what if the characters were
taken from ISO/IEC 9899:1999 in its entirety? What machine among you will
be able to recurse that deeply?

 

[Morris Dovey]

And I thought /I/ was being a little cruel. Consider just how fragile
recursion is, in this context. For example, what if the characters were
taken from ISO/IEC 9899:1999 in its entirety? What machine among you will
be able to recurse that deeply?

My DS-9000 could do it without filling its top-level cache. (-:

For any list being procesed by someone who needs to ask this
question, the scenario you posit seems improbable - and for
reasonable list sizes, I think it'd be a not-too-difficult and
instructive exercise - and hardly cruel.

Of course, it's also possible to count the list elements and
malloc an appropriate-sized array that could be filled backwards,
puts'd, and freed - I guess it'd all depend on whether the
exercise is intended to focus on memory management functions or
to explore solution techniques.

So, what does junky_fellow do if there isn't room to build this
horrendous string and malloc fails? Well, he could also consider
making a pass through the list for each character, moving the
stop point back by one element for each pass...

 

[nrk]

My DS-9000 could do it without filling its top-level cache. (-:

For any list being procesed by someone who needs to ask this
question, the scenario you posit seems improbable - and for
reasonable list sizes, I think it'd be a not-too-difficult and
instructive exercise - and hardly cruel.

Of course, it's also possible to count the list elements and
malloc an appropriate-sized array that could be filled backwards,
puts'd, and freed - I guess it'd all depend on whether the
exercise is intended to focus on memory management functions or
to explore solution techniques.

So, what does junky_fellow do if there isn't room to build this
horrendous string and malloc fails? Well, he could also consider
making a pass through the list for each character, moving the
stop point back by one element for each pass...

If space and recursion are issues, consider reversing the list
(non-recursive, O(1) space, O(n) time), then printing the contents, then
reversing it again. Better than the O(n^2) stop element solution you've
proposed.

-nrk.

 

[Morris Dovey]

If space and recursion are issues, consider reversing the list
(non-recursive, O(1) space, O(n) time), then printing the
contents, then reversing it again. Better than the O(n^2)
stop element solution you've proposed.

True - a good solution in the context of the standard's C
environment (where other tasks/threads would not have concurrent
access). Why didn't I think of that!

 

[junky_fellow]

Consider recursion.

i would like to avoid recursion, because if the list is quite
big it may cause "stack overflow".
So, can u suggest some other way?

 

[junky_fellow]

Consider a stack. Each node has a structure,

struct stack {
char c;
struct stack *next;
};

Each of the stack nodes contains an alphabetic character.

Start at the top of the list, and copy each node's character into a string,
since strings are by far the best way of representing characters. Now take
each character from the string, and push it onto the stack. When you're
done, empty the string, and then simply pop each character /off/ the stack
again, and feed it into the string (at the end, each time).

Now reverse the string:

void revstr(char *s) { if(s && *s) { char *t = s + strlen(s) - 1; while(t >
s) { char c = *t; *t-- = *s; *s++ = c; } } }

Now reverse it again, just to be absolutely sure that it's definitely,
definitely reversed. (This is quite simple - just call revstr again.)

Finally, loop through the string, placing each character on the standard
output device.


Simple!

But, this would require lots of extra storage and if the list is too big
you may face "out of memory" problem.

 

[pete]

But, this would require lots of extra storage
and if the list is too big
you may face "out of memory" problem.

#define N_TYPE \
struct node { \
char c; \
struct node *next; \
}
#define NEXT next

typedef N_TYPE n_type;

n_type *slist_rev(n_type *head)
{
n_type *previous, *next;

next = NULL;
while (head -> NEXT != NULL) {
previous = head;
head = previous -> NEXT;
previous -> NEXT = next;
next = previous;
}
head -> NEXT = next;
return head;
}

 

[Annit Bhattacharya]

Reverse the list in place, print contents and reverse it back in place. Some
syntax may be wrong, I am a newbie.

void revlist(node **p) {
node *q = NULL, *r = NULL;
if (( (*p)!= NULL) && ((*p)->next != NULL))
q = (*p)->next;
if (( q != NULL) && (q->next != NULL))
r = q->next;
while (q != NULL) {
q->next = *p;
*p = q;
q = r;
if (r != NULL)
r = r->next;
}
}

main() {
node *p, *q;

/*Load list code here, 'p' - points to the first node*/

revlist(&p);

q = p;
while (q != NULL) {
printf("%c",q->c);
q = q->next;
}

revlist(&p);

}

This should not cause any memory problems.

Regards,
Annit

 

[xarax]

Morris Dovey <[email protected]> wrote in message

i would like to avoid recursion, because if the list is quite
big it may cause "stack overflow".
So, can u suggest some other way?

This question has arisen in various forms. The generally
accepted solution is to reverse the list, then process it,
then reverse it again back to its original sequence. If
there are other requirements or restrictions (e.g.,
multi-threading, read-only nodes, etc.), then you must
be more specific with your statement of requirements.


--
----------------------------
Jeffrey D. Smith
Farsight Systems Corporation
24 BURLINGTON DRIVE
LONGMONT, CO 80501-6906
http://www.farsight-systems.com
z/Debug debugs your Systems/C programs running on IBM z/OS!
Are ISV upgrade fees too high? Check our custom product development!

 

[Thomas Matthews]

junky_fellow wrote:

Consider a singly-linked list. Each node has a structure,

struct node {
char c;
struct node *next;
};

Each of the nodes contain an alphabetic character.
Can anybody suggest a way to print the characters in reverse order.

Consider a stack. Each node has a structure, [snip]

Finally, loop through the string, placing each character on the standard
output device.

Simple!

Dude, I'm disappointed in you.

This issue goes back to Linked Lists 101. With lists,
changing the order involves changing the links. One of
the advantages to a linked list is not having to copy
or move elements.

If one has enough memory, one could create a new list
by traversing the current list and adding the current
node to the beginning of the new list. This reverses
the order; but requires enough memory for a second
list.

Another alternative is to perform an in-place change
of the links. Using a new head link, traverse
the list, prepending the current nodes to the new
head link.

--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.raos.demon.uk/acllc-c++/faq.html
Other sites:
http://www.josuttis.com -- C++ STL Library book

 

[Rob Thorpe]

i would like to avoid recursion, because if the list is quite
big it may cause "stack overflow".
So, can u suggest some other way?

It would be a good idea to store more than one character in each node.

If you can't it might be a good idea to copy the entire linked-list
into a string and operate on it there.

 

[Richard Heathfield]

junky_fellow wrote:

Consider a singly-linked list. Each node has a structure,

struct node {
char c;
struct node *next;
};

Each of the nodes contain an alphabetic character.
Can anybody suggest a way to print the characters in reverse order.

Consider a stack. Each node has a structure, [snip]

Finally, loop through the string, placing each character on the standard
output device.

Simple!

Dude, I'm disappointed in you.

Then you misunderstood my reply entirely, in which case /I/ am disappointed
in /you/.

 

[Nick Landsberg]

i would like to avoid recursion, because if the list is quite
big it may cause "stack overflow".
So, can u suggest some other way?

Make it a doubly linked list with head and tail pointers?

Or is that not an option?

 

[Peter Nilsson]

#define N_TYPE \
struct node { \
char c; \
struct node *next; \
}
#define NEXT next

typedef N_TYPE n_type;

n_type *slist_rev(n_type *head)
{
n_type *previous, *next;

next = NULL;

assert(head != NULL); /* !! */

while (head -> NEXT != NULL) {
previous = head;
head = previous -> NEXT;
previous -> NEXT = next;
next = previous;
}
head -> NEXT = next;
return head;
}

node *list_reverse(node *head)
{
node *rev = NULL;
node *next;
node *next_next = head;

while ((next = next_next) != NULL)
{
next_next = next->next;
next->next = rev;
rev = next;
}

return rev;
}

 

[yudi1226]

#include <iostream>
using namespace std ;

struct linklist
{
char data ;
struct linklist *next ;
} ;

int main()
{
struct linklist *ll_begin ,*ll_end ;

ll_begin = NULL ;
ll_end = NULL ;


for(int i = 0 ; i < 5 ; i++ )
{
struct linklist *ll_temp = new struct linklist ;
cout << "Pls input : " ;
cin >> ll_temp->data ;

if(ll_begin == NULL )
{
ll_begin = ll_temp ;
ll_end = ll_temp ;

}
else
{
ll_end->next = ll_temp ;
ll_end = ll_temp ;
ll_end->next = NULL ;

}//if(ll_begin == NULL )

} //for(int = 0 ; i < 5 ; i++ )

struct linklist *ll_store_end = ll_end ;
struct linklist *ll_store_begin = ll_begin;
struct linklist *ll_cur = NULL ;

//Loop linklist
ll_store_end->next = ll_store_begin ;

cout << "reverse linklist : " ;
ll_cur = ll_store_begin = ll_store_end ;


do
{

cout << ll_cur->data ;
while(ll_cur->next != ll_store_end)
{
ll_cur = ll_cur->next ;
}
ll_store_end = ll_cur ;
}while(ll_cur != ll_end) ;
cout << endl ;

//destructor loop linklist
ll_end->next = NULL ;


return 0 ;
}

 

[yudi1226]

#include <iostream>
using namespace std ;

struct linklist
{
char data ;
struct linklist *next ;
} ;

int main()
{
struct linklist *ll_begin ,*ll_end ;

ll_begin = NULL ;
ll_end = NULL ;


for(int i = 0 ; i < 5 ; i++ )
{
struct linklist *ll_temp = new struct linklist ;
cout << "Pls input : " ;
cin >> ll_temp->data ;

if(ll_begin == NULL )
{
ll_begin = ll_temp ;
ll_end = ll_temp ;

}
else
{
ll_end->next = ll_temp ;
ll_end = ll_temp ;
ll_end->next = NULL ;

}//if(ll_begin == NULL )

} //for(int = 0 ; i < 5 ; i++ )

struct linklist *ll_store_end = ll_end ;
struct linklist *ll_store_begin = ll_begin;
struct linklist *ll_cur = NULL ;

//Loop linklist
ll_store_end->next = ll_store_begin ;

cout << "reverse linklist : " ;
ll_cur = ll_store_begin = ll_store_end ;


do
{

cout << ll_cur->data ;
while(ll_cur->next != ll_store_end)
{
ll_cur = ll_cur->next ;
}
ll_store_end = ll_cur ;
}while(ll_cur != ll_end) ;
cout << endl ;

//destructor loop linklist
ll_end->next = NULL ;


return 0 ;
}

 

[Ben Pfaff]

#include <iostream>
using namespace std ;

Please don't post C++ to comp.lang.c.