//
//	Doubly Linked List
//

public class DList
{
	private DListNode top;
	private DListNode end;
	private int length;
	public DList()
	{	length = 0;
		top = null;
		end = null;
	}
	public boolean isEmpty()
	{	return length==0;	}
	public void insertTop(String item)
	{	DListNode temp = new DListNode(item, null, null);
		if(isEmpty())
		{	top = temp;
			end = temp;
		}
		else
		{	temp.setNext(top);
			top.setBack(temp);
			top = temp;
		}
		length ++;
	}
	public void insertEnd(String item)
	{	DListNode temp = new DListNode(item, null, null);
		if(isEmpty())
		{	top = temp;
			end = temp;
		}
		else
		{	temp.setBack(end);
			end.setNext(temp);
			end = temp;
		}
		length ++;
	}
	public String deleteTop()
	{
		String str = " ";
		if(isEmpty())
				System.out.println("Error! Empty list.");
		else
		{	str = top.getData();
			if(top == end)	// only one node
			{	top = null;
				end = null;
			}
			else	// at least two nodes
			{	top = top.getNext();
				top.setBack(null);
			}
			System.out.println("\n" + str + " was deleted.");
		}
		return str;
	}
	public String deleteEnd()
	{
		String str = " ";
		if(isEmpty())
			System.out.println("Error! Empty list.");
		else
		{	str = end.getData();
			if(top == end)	// only one node
			{	top = null;
				end = null;
			}
			else	// at least two nodes
			{	end = end.getBack();
				end.setNext(null);
			}
			System.out.println("\n" + str + " was deleted.");
		}
		return str;
	}
	public void Print()
	{	DListNode temp = top;
		System.out.print("The list is: ");
		while(temp != null)
		{	System.out.print(temp.getData() + " ");
			temp = temp.getNext();
		}
		System.out.println();

	}
	public void revPrint() {}
	public void sort() {}	// to ascending order
	public boolean isPresent(String item) {return false;}
	public void deleteItem(String item)
	{	boolean find = false;
		DListNode temp = top;
		while(temp != null)
		{	if(temp.getData().equalsIgnoreCase(item))
			{	find = true;
				if(top == end) 	// only one node
				{	top = null;
					end = null;
				}
				else			// two or more
				{	if(temp == top)
					{	top = top.getNext();
						top.setBack(null);
					}
					else if(temp == end)
					{	end = end.getBack();
						end.setNext(null);
					}
					else
					{	DListNode last = temp.getBack();
						DListNode next = temp.getNext();
						last.setNext(next);
						next.setBack(last);
					}
					System.out.println("\n" + item + " was removed.");
				}
			}
			// move one node forward
			temp = temp.getNext();
		}
		if(!find)	System.out.println("\n" + item + " was not found.");
	}
}