Node class – A node is an
element which belongs to a linked list which has data and next element.
public class Node {
Node next;
int data;
public Node() {
}
public Node(int data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public String toString(){
return ""+data;
}
}
Linked List class with implementation methods
public class LinkedList {
Node start;
Node end;
int size;
/* List Empty or not */
public boolean empty() {
return start == null;
}
/* To Get size of Linked List */
public int getSize() {
return size;
}
/* Insertion at Start */
public void insertAtStart(int data) {
Node newNode = new Node(data);
size++;
if (start == null) {
start = newNode;
end = newNode;
} else {
newNode.setNext(start);
start = newNode;
}
}
/* Insertion at End */
public void insertAtEnd(int data) {
Node newNode = new Node(data);
size++;
if (start == null) {
start = newNode;
end = newNode;
} else {
Node last = start;
while (last.getNext() != null)
last = last.getNext();
last.setNext(newNode);
end = newNode;
end.setNext(null);
}
}
/* Insert at particular position */
public void insertAtPos(int data, int pos) {
Node newNode = new Node(data);
size++;
Node temp = start;
int position = pos - 1;
for (int i = 0; i < position; i++)
temp = temp.getNext();
newNode.setNext(temp.getNext());
temp.setNext(newNode);
}
/*Delete element at the start*/
public void deleteAtStart(){
if(start==null){
System.out.println("No element in the list to delete");
}else{
System.out.println("Node to be deleted is"+ start);
start=start.getNext();
size--;
}
}
/* Delete element at the end */
public void deleteAtEnd(){
if(start==null || end==null)
System.out.println("No element to be deleted");
else{
Node temp=start;
while(temp.getNext()!=end)
temp=temp.getNext();
System.out.println("Node to be deleted is"+ temp.getNext());
temp.setNext(null);
end=temp;
size--;
}
}
/* Delete element at position n*/
public void
deleteAtPos(int pos){
if(start==null || end==null)
System.out.println("No element to be deleted");
else{
Node temp = start,deletedNode=start;
int position = pos - 2;
int position1 = pos - 1;
for (int i = 0; i < position; i++)
temp = temp.getNext();
for (int i = 0; i < position1; i++)
deletedNode = deletedNode.getNext();
temp.setNext(deletedNode.getNext());
size--;
System.out.println("Node to be deleted is"+ deletedNode);
}
}
/*Middle of the list Normal way*/
public int middleElement(){
int middleLength=size/2;
Node middle=start;
for(int i=1;i<=middleLength;i++)
middle=middle.getNext();
return middle.getData();
}
/*Middle of the list using two pointers*/
public int middleElementUsingTwoPointers(){
Node slowPtr=start;
Node fastPtr=start;
while(fastPtr.getNext()!=null){
slowPtr=slowPtr.getNext();
if(fastPtr.getNext().getNext()!=null)
fastPtr=fastPtr.getNext().getNext();
else
fastPtr=fastPtr.getNext();
}
return slowPtr.getData();
}
/*Delete list
* In Java, automatic garbage collection
happens,
* so deleting a linked list is easy. We just
need to change head to null.
*/
void deleteList(){
start=null;
end=null;
size=0;
System.out.println("Linked List deleted");
}
/*Reverse a Linked List*/
void reverseLinkedList(){
Node prev=null;
Node current=start;
Node next=null;
while(current!=null){
next=current.getNext();
current.setNext(prev);
prev=current;
current=next;
}
start=prev;
}
/*A simple and tail recursive function to reverse a linked list.
* prev is passed as NULL initially. */
Node reverseUtil(Node curr, Node prev) {
/* If last node mark it head*/
if (curr.getNext() == null) {
start = curr;
/* Update next to prev node */
curr.setNext(prev);
return null;
}
/* Save curr->next node for recursive call */
Node next1 = curr.getNext();
/* and update next ..*/
curr.setNext(prev);
reverseUtil(next1, curr);
return start;
}
/* main() to run our Application */
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.insertAtStart(10);
list.insertAtEnd(20);
list.insertAtEnd(30);
list.insertAtEnd(40);
list.insertAtEnd(50);
list.insertAtEnd(60);
list.insertAtEnd(70);
System.out.println("List after Insertion operations "+list);
list.insertAtPos(25,3);
System.out.println("List after insertion at position 3"+ list);
list.deleteAtStart();
System.out.println("List after Deletion At Start "+list);
list.deleteAtEnd();
System.out.println("List after Deletion At End "+list);
list.deleteAtPos(3);
System.out.println("List after Deletion At postion 3"+list);
int middleElement=list.middleElement();
System.out.println("Middle Element is"+ middleElement);
int middleElementUsingTwoPointers=list.middleElementUsingTwoPointers();
System.out.println("Middle Element is"+ middleElementUsingTwoPointers);
System.out.println("Start node is "+ list.start +"And end node is"+
list.end +"Size is"+list.size);
list.reverseLinkedList();
System.out.println("List after LinkedList Reversal "+list);
/*System.out.println("Deleting Linked List ...");
list.deleteList();
System.out.println("Start
node is-->"+ list.start +" And end node is-->"+
list.end +"
And Size is-->"+list.size);
*/
}
public String toString(){
String str = "List:";
Node temp=start;
while(temp!=null){
str+=temp+"-->";
temp=temp.getNext();
}
return str+"null";
}
}
Output
List after Insertion operations
List:10-->20-->30-->40-->50-->60-->70-->null
List after insertion at position
3List:10-->20-->30-->25-->40-->50-->60-->70-->null
Node to be deleted is10
List after Deletion At Start
List:20-->30-->25-->40-->50-->60-->70-->null
Node to be deleted is70
List after Deletion At End
List:20-->30-->25-->40-->50-->60-->null
Node to be deleted is25
List after Deletion At postion
3List:20-->30-->40-->50-->60-->null
Middle Element is40
Middle Element is40
Start node is 20And end node is60Size is5
List after LinkedList Reversal
List:60-->50-->40-->30-->20-->null
No comments:
Post a Comment