Insertion and deletion at the beginning of a linked list are very fast. They involve changing only one or two references, which takes 0(1) time. Finding, deleting, or insertion next to a specific item requires searching through, on the average, half the items in the list. This requires O(n) comparisons. An array is also O(n) for these operations, but the linked list is nevertheless faster because nothing needs to be moved when an item is inserted or deleted.
Of course, another important advantage of linked lists over arrays is that the linked list uses exactly as much memory as it needs, and can expand to fill all of the available memory. The size of an array is fixed when it’s created; this usually leads to inefficiency because the array is too large, or to running out of room because the array is too small Vectors, which are expandable arrays, may solve this problem to some extent, but they usually expand in fixed-sized increments (such as doubling the size of the array whenever it’s about to overflow). This is still not as efficient a use of memory as a linked list.
import java.io.*;
class node
{
public int v;
public node nxt;
public node(int x)
{
v=x;
}
public void dispval1()
{
System.out.println(v);
}
}
class LinkList
{
private node first,p,q;
public LinkList()
{
first=null;
}
public void insertval(int x)
{
node p=new node(x);
p.nxt=null;
if(first==null)
{
first=p;
q=p;
}
else
{
q.nxt=p;
q=p;
}
}
public void delfirst()
{
q=first;
first=first.nxt;
q=null;
}
public void displayList()
{
node r= first;
while(r !=null)
{
r.dispval1();
r=r.nxt;
}
}
}
class DeletingFirstElement
{
public static void main(String args[]) throws IOException
{
LinkList k=new LinkList();
int i;
for(i=1;i<=5;i++)
{
k.insertval(i);
}
System.out.println("Data in linked list is");
k.displayList();
k.delfirst();
System.out.println("Data in linked list after deleting first element is");
k.displayList();
}
}