• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Adding an element to the end of a linked list

 
Shaggy Rogers
Greenhorn
Posts: 26
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello all, I am writing a program that requires me to add and view items from both the left and right (front and back) sides of a linked list. I have the left side figured out, but the right side is giving me trouble. I'm not really sure what to set my rightEnd equal to in the constructor.
Thanks for the help.
Here is my code:




public abstract class LinkedDeque implements DequeInterface {
private DNode leftEnd;
private DNode rightEnd;
private int size;

LinkedDeque()
{
leftEnd = new DNode(null);
rightEnd = new DNode(leftEnd);

size = 0;

}
// add to left end
public void addLeft(Disk obj)
{
leftEnd = new DNode(obj);
size++;
}
public void addRight(Disk obj)
{

}
public int getSize()
{
return size;
}

public DNode peekLeft()
{
if(size ==0)
{
throw new IllegalArgumentException("List is empty!");
}

return leftEnd;
}
public DNode peekRight()
{
if(size ==0)
{
throw new IllegalArgumentException("List is empty!");
}
return rightEnd;

}
}
 
David McCombs
Ranch Hand
Posts: 212
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The "right end" would point to the last node in the list. If the list is empty, then null I suppose. If there is one node in the list but head and tail would point to the same node

You don't need to add a tail to the linked list to insert at the end. With a tail node, then you have 2 references to mess around with. Unless the list gets very large the gain in having quick access to the end of the list is very minor.
 
Burkhard Hassel
Ranch Hand
Posts: 1274
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi ranchers,

I would also say like David, if the linked list is constructed , left end and right end should point to the same element. But wouldn' the size then be 1?
eg constructor like

But I'm not sure about this, as I don't know what new DNode(null); will do.



David also cites that
"C++ is history repeated as tragedy. Java is history repeated as farce." -Scott McKay
You can put these two together as:
"The history of all hitherto existing society is the history of class struggles." - Karl Marx, Communist Manifesto


Yours,
Bu.
 
David McCombs
Ranch Hand
Posts: 212
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
With a dummy head node, both would initially point to the same node, but the size would still be 0.

I hope that quote doesn't offend anyone, I didn't add it to my sig for the purpose of offending anyone or ripping on Java. I just find it amusing that people can turn langauge preference into something akin to a holy war. Sure, we all have languages we don't like but few languages are so flawed to the point of uselessness.

The quotes came from this page, especially amusing are the opinions of the creator of Eiffel, Bertrand Meyer.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic