Discussion in 'C Programming' started by Perpetual Snow, Nov 26, 2003.

1. ### Perpetual SnowGuest

How can I reverse a linked list with no memory allocation?
I'm searching for an algorithm which is constant in runtime and space.

Thanks

Perpetual Snow, Nov 26, 2003

2. ### Kevin GoodsellGuest

Perpetual Snow wrote:
> How can I reverse a linked list with no memory allocation?
> I'm searching for an algorithm which is constant in runtime and space.

That would be a neat trick (to do it in constant time), but it's not
topical here. Try an algorithms group.

-Kevin
--
My email address is valid, but changes periodically.

Kevin Goodsell, Nov 26, 2003

3. ### James HuGuest

On 2003-11-26, Kevin Goodsell <> wrote:
> Perpetual Snow wrote:
>> How can I reverse a linked list with no memory allocation?
>> I'm searching for an algorithm which is constant in runtime and space.

>
> That would be a neat trick (to do it in constant time), but it's not
> topical here. Try an algorithms group.

Assuming something like this:

typedef struct list list;
typedef struct node node;

node * first_node(list *);
node * last_node(list *);
node * next_node(node *);
node * prev_node(node *);

typedef struct list_interface {
node * (*first_)(list *);
node * (*last_)(list *);
} list_interface;

typedef struct node_interface {
node * (*next_)(node *);
node * (*prev_)(node *);
} node_interface;

const list_interface List = { first_node, last_node };
const node_interface Node = { next_node, prev_node };

Then reversing it is easy:

const list_interface RevList = { last_node, first_node };
const node_interface RevNode = { prev_node, next_node };

-- James

James Hu, Nov 26, 2003
4. ### J. J. FarrellGuest

"Perpetual Snow" <> wrote in message
news:3fc46186\$0\$27027\$...
>
> How can I reverse a linked list with no memory allocation?
> I'm searching for an algorithm which is constant in runtime and space.

Walk the list, changing the pointers as you go.

J. J. Farrell, Nov 26, 2003
5. ### SeverianGuest

On Wed, 26 Nov 2003 03:23:09 -0600, James Hu <>
wrote:

>On 2003-11-26, Kevin Goodsell <> wrote:
>> Perpetual Snow wrote:
>>> How can I reverse a linked list with no memory allocation?
>>> I'm searching for an algorithm which is constant in runtime and space.

>>
>> That would be a neat trick (to do it in constant time), but it's not
>> topical here. Try an algorithms group.

>
>Assuming something like this:
>
> typedef struct list list;
> typedef struct node node;
>
> node * first_node(list *);
> node * last_node(list *);
> node * next_node(node *);
> node * prev_node(node *);
>
> typedef struct list_interface {
> node * (*first_)(list *);
> node * (*last_)(list *);
> } list_interface;
>
> typedef struct node_interface {
> node * (*next_)(node *);
> node * (*prev_)(node *);
> } node_interface;
>
> const list_interface List = { first_node, last_node };
> const node_interface Node = { next_node, prev_node };
>
>Then reversing it is easy:
>
> const list_interface RevList = { last_node, first_node };
> const node_interface RevNode = { prev_node, next_node };
>
>-- James

James,

lists yet!

- Sev

Severian, Nov 26, 2003
6. ### Just curiousGuest

J. J. Farrell wrote:
> "Perpetual Snow" <> wrote in message
> news:3fc46186\$0\$27027\$...
>
>>How can I reverse a linked list with no memory allocation?
>>I'm searching for an algorithm which is constant in runtime and space.

>
>
> Walk the list, changing the pointers as you go.

And that is supposed to be constant in time?

Just curious, Nov 26, 2003
7. ### Chris DollinGuest

Just curious wrote:

> J. J. Farrell wrote:
>> "Perpetual Snow" <> wrote in message
>> news:3fc46186\$0\$27027\$...
>>
>>>How can I reverse a linked list with no memory allocation?
>>>I'm searching for an algorithm which is constant in runtime and space.

>>
>>
>> Walk the list, changing the pointers as you go.

>
> And that is supposed to be constant in time?

That's easily achived, assuming the implementation has a limit on the

--
Chris "the impossible we relabel at once" Dollin
C FAQs at: http://www.faqs.org/faqs/by-newsgroup/comp/comp.lang.c.html
C welcome: http://www.angelfire.com/ms3/bchambless0/welcome_to_clc.html

Chris Dollin, Nov 26, 2003
8. ### CBFalconerGuest

Perpetual Snow wrote:
>
> How can I reverse a linked list with no memory allocation? I'm
> searching for an algorithm which is constant in runtime and space.

It obviously cannot execute in constant time. An O(n) process is:

/* The bare minimum to form a linked list */
typedef struct node {
struct node *next;
void *data;
} node, *nodeptr;

/* ======================================================= */
/* believed necessary and sufficient for NULL terminations */
/* Reverse a singly linked list. Reentrant (pure) code */
nodeptr revlist(nodeptr root)
{
nodeptr curr, nxt;

if (root) { /* non-empty list */
curr = root->next;
root->next = NULL; /* terminate new list */
while (curr) {
nxt = curr->next; /* save for walk */
curr->next = root; /* relink */
root = curr; /* save for next relink */
curr = nxt; /* walk onward */
}
}
/* else empty list is its own reverse; */
return root;
} /* revlist */

--
Chuck F () ()
Available for consulting/temporary embedded and systems.

CBFalconer, Nov 26, 2003
9. ### MacGuest

On Wed, 26 Nov 2003 10:33:46 +0000, Chris Dollin wrote:

> Just curious wrote:
>
>> J. J. Farrell wrote:
>>> "Perpetual Snow" <> wrote in message
>>> news:3fc46186\$0\$27027\$...
>>>
>>>>How can I reverse a linked list with no memory allocation?
>>>>I'm searching for an algorithm which is constant in runtime and space.
>>>
>>>
>>> Walk the list, changing the pointers as you go.

>>
>> And that is supposed to be constant in time?

>
> That's easily achived, assuming the implementation has a limit on the
> length of a linked list.

Now THAT is funny. ;-)

Mac
--

Mac, Nov 27, 2003
10. ### Derk GwenGuest

# if (root) { /* non-empty list */
# curr = root->next;
# root->next = NULL; /* terminate new list */
# while (curr) {
# nxt = curr->next; /* save for walk */
# curr->next = root; /* relink */
# root = curr; /* save for next relink */
# curr = nxt; /* walk onward */
# }
# }
# /* else empty list is its own reverse; */
# return root;
# } /* revlist */

for (prev=0,curr=list; curr; prev=curr,curr=next) {
next = curr->next; curr->next = prev;
}
list = prev;

--
Derk Gwen http://derkgwen.250free.com/html/index.html
I love the smell of commerce in the morning.

Derk Gwen, Nov 27, 2003