Monday, February 8, 2021

How to find middle element of LinkedList without using inbuilt method or extra loop

 

1) List Interface Implementation

public interface List<T extends Comparable<T>> { public Node<T> getMiddleNode(); public void insert(T data); public void remove(T data); public void traverse(); public int size(); public void reverse(); }

2) Linked List's Node Implementation

public class Node<T extends Comparable<T>> { private Node<T> nextNode; T data; public Node(T data){ this.data = data; } public Node<T> getNextNode() { return nextNode; } public void setNextNode(Node<T> nextNode) { this.nextNode = nextNode; } public T getData() { return data; } public void setData(T data) { this.data = data; } @Override public String toString() { return data+"-> "; } }

3) Linked List Implementation

public class LinkedList<T extends Comparable<T>> implements List<T> { private Node<T> head; int sizeCounter=0; @Override public Node<T> getMiddleNode() { ==> Example to find middle node of LinkedList Node<T> slow = head; Node<T> fast = head; while(fast.getNextNode() != null && fast.getNextNode().getNextNode() != null) { slow = slow.getNextNode(); fast = fast.getNextNode().getNextNode(); } return slow; } @Override public void insert(T data) { sizeCounter++; if(head==null) { head = new Node<T>(data); }else { insertBiginning(data); } } private void insertBiginning(T data) { Node<T> node = new Node<T>(data); node.setNextNode(head); head = node; } @Override public void remove(T data) { if(head == null) return; if(head.getData().compareTo(data) == 0) { head = head.getNextNode(); }else { remove(data,head, head.getNextNode()); } } private void remove(T data, Node<T> previousNode, Node<T> actualNode) { while(actualNode != null) { if(actualNode.getData().compareTo(data)==0) { ==> This is the reason we use generic type which extends Comparable sizeCounter--; previousNode.setNextNode(actualNode.getNextNode()); actualNode=null; return; } previousNode = actualNode; actualNode = actualNode.getNextNode(); } } @Override public void traverse() { ==> Example to traverse linked list r if(head==null) return; Node<T> actualNode = head; while(actualNode != null) { System.out.print(actualNode); actualNode = actualNode.getNextNode(); } } @Override public int size() { return sizeCounter; } @Override public void reverse() { ==> Example to reverse LinkedList Node<T> prev = null; Node<T> next = null; Node<T> current = head; while(current != null) { next = current.getNextNode(); current.setNextNode(prev); prev = current; current = next; } head = prev; } }

4) Linked List uses example

public class AppRunner { public static void main(String[] args) { LinkedList<String> names = new LinkedList<>(); names.insert("narayan"); names.insert("Pawan"); names.insert("Karan"); names.insert("Sonu"); names.insert("Ram"); names.traverse(); ==> Traversing Linked List System.out.println(""); System.out.println("Middle node is :- "+names.getMiddleNode());==> Finding middle element without using extra loop names.reverse(); ==> Reversing linkedList without inbuilt function System.out.println(""); names.traverse(); } }

5) Output:-

Before Reverse:- Tarun-> Nishant-> Gajendra-> Sonpal-> Ravi-> Anurag-> Narayan-> After ReversingNarayan-> Anurag-> Ravi-> Sonpal-> Gajendra-> Nishant-> Tarun-> Middle node is :- Sonpal->

No comments:

Post a Comment

How to find middle node of LinkedList without using extra memory in java

To find the middle node of a LinkedList without using extra memory in Java, you can use the "tortoise and hare" algorithm. This al...