public class LinkedList
{
private class Node
{
T data;
Node next;
}
private Node head; //No need to assign addresses now (‘new’ use) since it will be defined afterwards too
private Node tail;
private int size;
public void display()
{
Node temp=head; //
while(temp!=null)
{
System.out.print(temp.data+", ");
temp=temp.next;
}
System.out.println();
}
public boolean isEmpty()
{
if(size==0)
return true;
return false;
}
public void addLast(T item)
{
Node nn=new Node();
nn.data=item;
if(size>0)
tail.next=nn;
if(size==0)
head=tail=nn;
else
tail=tail.next;
size++;
}
public void addFirst(T item)
{
Node nn=new Node();
nn.data=item;
if(size>0)
nn.next=head;
if(size==0)
head=tail=nn;
else
head=nn;
size++;
}
public T getFirst() throws Exception
{
if(size==0)
throw new Exception("LL is empty");
return head.data;
}
public T getLast() throws Exception
{
if(size==0)
throw new Exception("LL is empty");
return tail.data;
}
public T getAt(int index) throws Exception
{
if(size==0)
throw new Exception("LL is empty");
if(index>size || index<1)
throw new Exception("INdex invalid");
Node temp=head;
for(int i=1;i<index;i++)
{
temp=temp.next;
}
return temp.data;
}
public Node getNodeAt(int index) throws Exception
{
if(size==0)
throw new Exception("LL is empty");
if(index>size || index<1)
throw new Exception("INdex invalid");
Node temp=head;
for(int i=1;i<index;i++)
{
temp=temp.next;
}
return temp;
}
public void addAt(int index,T item) throws Exception
{
if(index<1 || index>size+1)
throw new Exception("index invalid");
if(index==1)
addFirst(item);
if(index==size+1)
addLast(item);
Node nn=new Node();
nn.data=item;
Node temp=head;
for(int i=1;i<index-1;i++)
{
temp=temp.next;
}
nn.next=temp.next;
temp.next=nn;
}
public T removeFirst() throws Exception
{
if(size==0)
throw new Exception("LL is empty");
T save=head.data;
if(size==1)
head=tail=null;
else
head=head.next;
size--;
return save;
}
public T removeLast() throws Exception
{
if(size==0)
throw new Exception("LL is empty");
T save=tail.data;
if(size==1)
head=tail=null;
else
{
Node temp=head;
for(int i=1;i<size-1;i++)
{
temp=temp.next;
}
temp.next=null;
tail=temp;
}
size--;
return save;
}
public T removeAt(int index) throws Exception
{
if(size==0)
throw new Exception("LL is empty");
if(index==1)
return removeFirst();
else if (index==size)
return removeLast();
else
{
Node temp=head;
for(int i=1;i<index-1;i++)
{
temp=temp.next;
}
T save=temp.next.data;
temp.next=temp.next.next;
size--;
return save;
}
}
public void reverse() throws Exception
{
int left=1;
int right=size;
while(left<right)
{
Node ln=getNodeAt(left);
Node rn=getNodeAt(right);
T save=ln.data;
ln.data=rn.data;
rn.data=save;
left++; right--;
}
}
public T midNode() throws Exception
{
if(size%2==0)
return getAt(size/2);
else
return getAt(size/2 +1);
}
}