we have have already learn about Data Structure and Linked List . Those who are from Java Background also know about Collection Framework.But even though most of the time interviewer asked about the Implementation of Linked List or Ask you To implement the Linear Data Structure like stack, queue, LinkedList Etc.
above Class is implementation of all possible operation used in Linked list like addFirst,removeLast,add ,getElementAt etc..
if you have any question regarding the codes which you don't understand you can ask ..
now, we have done with implementation now its time to test our Linked List is working or not.
to Test this i am going to write one demo class which import mycollection.LinkedList and perform all operation.
here in demo class i am trying to perform all operation and checking whether the list is working fine or not.
that all for today try it by your own . if you face any query you can comment and ask. soon i am posting the implementation of ResizableArray,Stack and Queue. hope you like this..
please share , like and show your support.
Here I am
not going to discuss the about what is linked list or what is advantage of it
or its algorithm. Simple we are going to see how we can implement single Linked
list through Java coding.
Here is code which implements all the operational
method and creation of Linked List .. This code also have two inner class which
are used by outer class.
let start..
|
/*
* Copyright (c) 2019
Java Guru and/or its affiliates. All rights reserved.
* Java Guru
PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*/
package
mycollection;
//import
mycollection.EmptyListException;
/**
* Linked List
Implementaion using Java . It Is single Linked List.
* This
Implementation includes all neccessary Operation perform on LinkedList ,
permit Integer Type Element
* in the List
(including {@code null}).
*
*
*<P>This Class
is member of <a herf="">MyCollection</a>
* @author Pawan
* @see Queue
* @see Stack
* @since 1.2
*/
public class
LinkedList
{ /**
* pointer to first Node.
* invariant : (head!=null
&& head.next=null )
* when this pointer is null
then list is empty.
*/
private static Node head;
/**
* This variable count the
number of node present in the list.
*/
private static int numNodes;
/**
* This constructor makes the
empty Linked List object. with no node
*/
public LinkedList()
{
head=null;
numNodes=0;
}
/**
* This method used to add a
node before the First node(head pointing node).
*if list is empty then This
new node become the First node and head pointing to it .
* @param element is data which is inserted
*/
public void addFirst(int
element)
{
//check
whether list is empty or not;
if (isEmpty())
{
head=new
Node(element);
numNodes++;
}
else
{
Node
temp = head;
head=
new Node(element);
head.next=temp;
numNodes++;
}
}
/**
* This method used to add a
node after the last node.
*if list is empty then This
new node become the First node and head pointing to it .
* @param element is data which is inserted
*/
public void addLast(int
element)
{
//check
whether list is empty or not;
if (isEmpty())
{
head=new
Node(element);
numNodes++;
}
else
{
Node
temp =head;
while(temp.next!=null)
{
temp=temp.next;
}
temp.next=
new Node(element);
numNodes++;
}
}
/**
* This method check whether
the list has element or it is empty list.
* @ Return true when the list
is empty else false.
*/
public boolean isEmpty()
{
if
(head==null)
return
true;
return false;
}
/**
* This method give number of
element present in the List .
* @ Return integer value which
represent the size of List or number of element in List.
*/
public int getSize()
{
return
numNodes;
}
/**
* This method is used to clear
the list and remove all element from the list.
*/
public void clear()
{
head=null;
numNodes=0;
}
/**
* This method is used to add
element in the list at particular index.
* @param index at which the
element need to added.
* @param element which is to
be added.
*/
public void addAt(int
index,int element)
{
if (index==0)
{
addFirst(element);
}
else
if(index>numNodes)
{
addLast(element);
}
else{
Node
temp=head;
Node
holder;
for
(int i=0;i<index-1;i++ ) // traveser in the list upto that index
{
temp=temp.next;
}
holder=temp.next;
temp.next=
new Node(element);
temp.next.next=holder;
numNodes++;
}
}
/**
* this method is
general method used to add elements in list.
* @param element
which is to be added.
*/
public void add(int element)
{
this.addLast(element);
}
/**
* This method is used to
remove the element from the List from
the particular index.
* @param index is the index
from which element is removed.
* @return element which is
removed from the list.
*/
public int removeAt(int index)
{
int data=0;
if(isEmpty())
{
throw
new EmptyListException("List is Empty How can you remove Element from
Empty List");
}
else
{
Node
temp=head;
for
(int i=1;i<index-1;i++ )
{
temp=temp.next;
}
data=temp.next.data;
temp.next=temp.next.next;
numNodes--;
}
return data;
}
/**
* to remove the element from
the last.
*@return its return the
removed element.
*/
public int removeLast()
{
return
this.removeAt(numNodes);
}
/**
* To remove element from the
first .
*/
public int removeFirst()
{
int data=0;
if (isEmpty())
{
throw
new EmptyListException("List is Empty How can you remove Element from
Empty List");
}
else
{
data=head.data;
head=head.next;
numNodes--;
}
return data;
}
// below are methods which
retrive elements from the list
/**
* this method is
used to retrive the last element of the list.
*/
public int getFirst()
{
return
head.data;
}
/**
* this method is
used to retrive the last element of the list.
*/
public int getLast()
{
Node
temp=head;
for (int
i=1;i<numNodes-1 ;i++ )
{
temp=temp.next;
}
return
temp.next.data;
}
/**
* this method is
used to retrive the element present at particular index.
* @param index is
that index at which element you want to retrive.
*/
public int getElementAt(int
index)
{
Node
temp=head;
for (int
i=1;i<=index-1;i++ )
{
temp=temp.next;
}
return
temp.data;
}
// override the
toString method.
public String toString()
{
String
s="[";
Node
temp=head;
int count=1;
while(temp!=null)
{
s=s+temp.data;
if(count<numNodes)
s+=",";
temp=temp.next;
count++;
}
s=s+"]";
return s;
}
// inner static class Node
private static class Node
{
private int
data;
private Node
next;
public
Node(int data)
{
this.data=data;
}
} // end of node class
private static class EmptyListException
extends RuntimeException
{
EmptyListException(String
s)
{
super(s);
}
}
}
|
above Class is implementation of all possible operation used in Linked list like addFirst,removeLast,add ,getElementAt etc..
if you have any question regarding the codes which you don't understand you can ask ..
now, we have done with implementation now its time to test our Linked List is working or not.
to Test this i am going to write one demo class which import mycollection.LinkedList and perform all operation.
here in demo class i am trying to perform all operation and checking whether the list is working fine or not.
|
import
mycollection.LinkedList;
public class demo
{
public static void
main(String[] args)
{
LinkedList l =
new LinkedList();
// adding
element to the list
l.addLast(30);
l.add(45);
l.add(62);
l.add(55);
l.add(454);
l.addFirst(15);
l.addAt(8,18);
System.out.println(l);
// displaying list
l.removeFirst(); // removing
fist element from list
System.out.println(l);
l.removeLast(); //
removing last element
System.out.println(l);
System.out.println(l.removeAt(3));
// removing the element at 3rd index
System.out.println(l);
// getting
element from the various point in list using get function
System.out.print("first
: "+l.getFirst()+"last: "+l.getLast()+"element at :
"+l.getElementAt(2));
//check where
the list is empty or not
System.out.println("list
empty :"+isEmpty());
// getting
size of list or number of element present in list
System.out.println("No
of element Present in the list are "+l.getSize());
// clear all
element of the list than check it is empty or not
l.clear();
System.out.println("list
empty :"+isEmpty());
}
}
|
that all for today try it by your own . if you face any query you can comment and ask. soon i am posting the implementation of ResizableArray,Stack and Queue. hope you like this..
please share , like and show your support.
