Delete a node in a single link list that takes O(1) time

[hotice]

How to write code to delete a specific node in a single link list that
takes O(1) time? £¨ link list uses pointers, not hash. £© That is, the
time deleting a node is the same (independent from the length of the
list. Show your c/c++ source code.

[Ian Collins]

hotice wrote:

How to write code to delete a specific node in a single link list that
takes O(1) time? £¨ link list uses pointers, not hash. £© That is, the
time deleting a node is the same (independent from the length of the
list. Show your c/c++ source code.

You first!

--
Ian Collins.

[Daniel T.]

hotice <xu*******@gmail.comwrote:

How to write code to delete a specific node in a single link list that
takes O(1) time? £® link list uses pointers, not hash. £© That is, the
time deleting a node is the same (independent from the length of the
list. Show your c/c++ source code.

Think about how a single linked list works. What is a node in such a
list? What properties does it have? Now think of a couple ways to remove
a node from the list. What information do you need to do it? Do
different removal strategies require different information?

Do all the above without code first. Write a simple description of what
needs to happen in what ever language you feel most comfortable in.

[Salt_Peter]

On May 18, 8:48 pm, hotice <[e-mail]:

How to write code to delete a specific node in a single link list that
takes O(1) time? £¨ link list uses pointers, not hash. £© That is, the
time deleting a node is the same (independent from the length of the
list. Show your c/c++ source code.

What you describe is not a linked list anymore.
Show your own code.

[Alf P. Steinbach]

* Salt_Peter:

On May 18, 8:48 pm, hotice <[e-mail]:

>How to write code to delete a specific node in a single link list that
takes O(1) time? ( link list uses pointers, not hash. ) That is, the
time deleting a node is the same (independent from the length of the
list. Show your c/c++ source code.

What you describe is not a linked list anymore.

Well, not that I like doing homework for anyone, but this problem goes
back to about 1967. It's well known with well known solution. Young
"hotice" is just too dishonest to think of any way of finding a solution
other than to cheat, not even doing his own googling.

Show your own code.

Second that.

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

[Clark Cox]

On 2007-05-18 18:51:47 -0700, Salt_Peter <pj*****@yahoo.comsaid:

On May 18, 8:48 pm, hotice <[e-mail]:

>How to write code to delete a specific node in a single link list that
takes O(1) time? （ link list uses pointers, not hash. ） That

is, the

>time deleting a node is the same (independent from the length of the
list. Show your c/c++ source code.

What you describe is not a linked list anymore.

Of course it is. In fact, I'd say that the obvious way of removing an
element from a linked list is O(1) time. (think about it).

Show your own code.

--
Clark S. Cox III
cl*******@gmail.com

[Salt_Peter]

On May 19, 12:05 am, Clark Cox <[e-mail]:

On 2007-05-18 18:51:47 -0700, Salt_Peter <[e-mail]:

On May 18, 8:48 pm, hotice <[e-mail]:

How to write code to delete a specific node in a single link list that
takes O(1) time? £¨ link list uses pointers, not hash. £© That

is, the

time deleting a node is the same (independent from the length of the
list. Show your c/c++ source code.

What you describe is not a linked list anymore.

Of course it is. In fact, I'd say that the obvious way of removing an
element from a linked list is O(1) time. (think about it).

I agree with the O(1), but thats not was he's asking for.

>

Show your own code.

--
Clark S. Cox III
[e-mail]

[Salt_Peter]

On May 19, 12:05 am, Clark Cox <[e-mail]:

On 2007-05-18 18:51:47 -0700, Salt_Peter <[e-mail]:

On May 18, 8:48 pm, hotice <[e-mail]:

How to write code to delete a specific node in a single link list that
takes O(1) time? £¨ link list uses pointers, not hash. £© That

is, the

time deleting a node is the same (independent from the length of the
list. Show your c/c++ source code.

What you describe is not a linked list anymore.

Of course it is. In fact, I'd say that the obvious way of removing an
element from a linked list is O(1) time. (think about it).

Its definitely O(1), he doesn't know it but thats not what he's asking
for.

[Juha Nieminen]

hotice wrote:

How to write code to delete a specific node in a single link list that
takes O(1) time? £¨ link list uses pointers, not hash. £©

What info do you have to delete the node? If you have only a pointer
to the node to be deleted and nothing else, it's obviously impossible
to delete it in constant time. You need a pointer to the previous node.

[Alf P. Steinbach]

* Juha Nieminen:

hotice wrote:

>How to write code to delete a specific node in a single link list that
takes O(1) time? ( link list uses pointers, not hash. )

What info do you have to delete the node? If you have only a pointer
to the node to be deleted and nothing else, it's obviously impossible
to delete it in constant time. You need a pointer to the previous node.

No.

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

[antonov84]

What info do you have to delete the node? If you have only a pointer
to the node to be deleted and nothing else, it's obviously impossible
to delete it in constant time. You need a pointer to the previous node.

No.

What info do you have to delete the node? If you have only a pointer
to the node to be deleted and nothing else, it's obviously impossible
to delete it in constant time. You need a pointer to the previous node.

No.

---------
list_t *tmp = this->next;
this->val = this->next->val;
this->next = this->next->next;
delete tmp;
---------

but your 'val' has to support '=' ;]

[Howard]

<an*******@ukr.netwrote in message
news:11**********************@h2g2000hsg.googlegro ups.com...

>

What info do you have to delete the node? If you have only a pointer
to the node to be deleted and nothing else, it's obviously impossible
to delete it in constant time. You need a pointer to the previous node.

No.

What info do you have to delete the node? If you have only a pointer
to the node to be deleted and nothing else, it's obviously impossible
to delete it in constant time. You need a pointer to the previous node.

No.

---------
list_t *tmp = this->next;
this->val = this->next->val;
this->next = this->next->next;
delete tmp;
---------

but your 'val' has to support '=' ;]

Consider: what if you're at the end of the list, and this->next is NULL?

-Howard

(P.S., please don't do other people's homework for them. How are they
supposed to learn anything if we help them cheat on their assignments?)