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->
Monday, February 8, 2021
How to find middle element of LinkedList without using inbuilt method or extra loop
Subscribe to:
Post Comments (Atom)
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...
-
public class ReverseArrayWithoutExtraMemory { public static void main(String[] args) { int arr[] = {1,2,3,4,5,6}; int swapArray[] =...
-
1) List Interface Implementation public interface List<T extends Comparable<T>> { public Node<T> getMi...
-
function data_change(field) { var check = true; var value = field.value; //get characters //check that all ch...
No comments:
Post a Comment