By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
457,954 Members | 1,248 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 457,954 IT Pros & Developers. It's quick & easy.

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

P: n/a
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.

May 19 '07 #1
Share this Question
Share on Google+
11 Replies


P: n/a
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.
May 19 '07 #2

P: n/a
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.
May 19 '07 #3

P: n/a
On May 18, 8:48 pm, hotice <xuxin2...@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.
What you describe is not a linked list anymore.
Show your own code.

May 19 '07 #4

P: n/a
* Salt_Peter:
On May 18, 8:48 pm, hotice <xuxin2...@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.

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?
May 19 '07 #5

P: n/a
On 2007-05-18 18:51:47 -0700, Salt_Peter <pj*****@yahoo.comsaid:
On May 18, 8:48 pm, hotice <xuxin2...@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.

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

May 19 '07 #6

P: n/a
On May 19, 12:05 am, Clark Cox <clarkc...@gmail.comwrote:
On 2007-05-18 18:51:47 -0700, Salt_Peter <pj_h...@yahoo.comsaid:
On May 18, 8:48 pm, hotice <xuxin2...@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.
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
clarkc...@gmail.com

May 19 '07 #7

P: n/a
On May 19, 12:05 am, Clark Cox <clarkc...@gmail.comwrote:
On 2007-05-18 18:51:47 -0700, Salt_Peter <pj_h...@yahoo.comsaid:
On May 18, 8:48 pm, hotice <xuxin2...@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.
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.
May 19 '07 #8

P: n/a
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.
May 19 '07 #9

P: n/a
* 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?
May 19 '07 #10

P: n/a
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 '=' ;]

May 19 '07 #11

P: n/a

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

May 21 '07 #12

This discussion thread is closed

Replies have been disabled for this discussion.