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]

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!

 

[Daniel T.]

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]

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:

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.

 

[Clark Cox]

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).

 

[Salt_Peter]

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.

 

[Salt_Peter]

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]

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:

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.

 

[antonov84]

No.

 

[Howard]

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

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?)