Java Programming

Hi everyone,

I'm working on a lab for a computer science class I'm taking. I have to create a singly-linked list with a head and a tail, and include methods for inserting and removing nodes from the front and the end of the list, all in constant time. My problem is that I cannot figure out how to remove a node from the end of the list in constant time. The only node in my list that has a reference to the previous node is my tail. If I could somehow get a hold of the node before the one before my tail, I could do this easily, but I can't figure out how to do this without resorting to looping through the whole list (which would result in a linear time operation). My nodes contain one integer value and one reference to the next node in the list, and they have all the get and set methods you could need.

I don't need the code, but could anyone tell me how to remove a node from the end of a singly-linked list in constant time? Actually, I'd need to know how to do this by 11:59 PM tonight. That's the deadline to submit the source code to my instructor. I didn't realize before tonight that we needed to make all the basic operations of the list constant time. If I can't finish this one method in time, I'll just submit what I have now (removing from the end in linear time) and see what happens.

Thanks for any help in advance. (And please hurry! :P)

EDIT: Time's up. I had to submit what I had, but I still want to know how to solve this problem. If anyone knows how to implement it, please enlighten me.

Thanks.

Edited by: Josh7289 on Oct 1, 2007 11:54 PM EST