In this article, we are going to discuss a very interesting topic, “how to get middle of a singly linked list”. Before that, we will see the different algorithms to get the middle of any linear data structure. There are two ways to get the middle of any linear data structure.
(Size of data structure) / 2 : This is the most common way to get the middle of any index based linear data structures. To get the middle element, divide the size of collection by 2 to get the middle element. If size of collection is even number , we can declare any two middle index as middle of the collection.Ex: if size=6 then we can say index=3 or index =2 can be the middle index. If size of collection is odd number, we will have only one middle index. Ex: if size=5 then middle index=2.
Algorithm:
- Suppose size of collection is N and index start from 0 to N-1.
- Divide size by 2 to get the integer index value .
- get the element by index.
This approach is useful when we have indexed linear data structure, because we can get the elements by index. But for non-indexed linear data structures, we need to traverse through the elements. Below is the optimal solution to get the middle of non-indexed linear data structure.
Pointer Movement: To understand this approach, assume we have 10 feet long road. Two men started walking from one end. Now, condition is, first man can take 2 feet long step but second man can take 1 foot long step. Both men will get the similar opportunity to step ahead one by one. Obviously, first man will reach early at other end of the road. Now, when first man will reach at other end of the road, what will be the position of second man ? Since step size of first man is double as compare to the second man, position of second man will be middle of the road when first man reaches at other end of the road.
Similar concept applies to get the middle of any linear data structure . [stextbox id=’info’]If fast moving pointer reaches at the end of the linear data structure, that time, position of slow moving pointer will be at middle. Speed of fast pointer = 2* (Speed of slow pointer).[/stextbox]
Refer the below algorithm and execution process to get middle of singly linked list.
Algorithm:
- Declare two node variables , fastPointer and slowPointer.
- Initialize fastPointer =root->next Node
- Initialize slowPointer=root
- Move fast pointer by 2 and slow pointer by 1 till fast pointer is not equal to null.To do so, repeat the steps 5 and 6 till fastPointer !=null
- fastPointer = fastPointer -> next Node
- if fastPointer !=null , move slow pointer and fast pointer one step ahead
- Finally, when fast pointer reaches at end of the linked list i.e fastPointer == null , slow pointer will be at middle of the linked list.
Execution Process :
See the below Java code implementation to get middle of a singly linked list.
package com.study.singlyLinkedList;
public class Node<T> {
private T data ;
private Node<T> node;
public Node(T data) {
this.data = data;
}
public Node<T> getNode() {
return node;
}
public void setNode(Node<T> node) {
this.node = node;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
@Override
public String toString() {
return data+"" ;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((data == null) ? 0 : data.hashCode());
result = prime * result + ((node == null) ? 0 : node.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (!(obj instanceof Node))
return false;
Node other = (Node) obj;
if (data == null) {
if (other.data != null)
return false;
} else if (!data.equals(other.data))
return false;
if (node == null) {
if (other.node != null)
return false;
} else if (!node.equals(other.node))
return false;
return true;
}
}
package com.study.singlyLinkedList;
import java.util.Stack;
public class SinglyLinkedList<T> {
private int size = 0;
private Node<T> node;
/**
* Returns the data at middle of the linked list
* @return
*/
public T getMiddle() {
return getMiddle(this.node).getData();
}
/**
*
* @param node
* @return
*/
private Node<T> getMiddle(Node<T> node) {
if(node ==null || node.getNode()==null) {
return node;
}
Node<T> fastPointer=node.getNode();
Node<T> slowPointer=node;
// Move fast pointer by two and slow pointer by one
// Finally slow pointer will point to middle node when fast
// pointer will reach at end of the linked list
while (fastPointer !=null) {
fastPointer=fastPointer.getNode();
if(fastPointer!=null) {
slowPointer=slowPointer.getNode();
fastPointer=fastPointer.getNode();
}
}
return slowPointer;
}
/**
* Reverse the linked list by reversing the pointers in reverse direction
*/
public void reverse() {
Node<T> current=this.node;
Node<T> previous=null;
Node<T> next=null;
while(current !=null) {
next = current.getNode();
current.setNode(previous);
previous=current;
current=next;
}
this.node=previous;
}
/**
* Reverse the linked list using stack
*/
public void reverseUsingStack() {
// Push all node to Stack starting from root
Stack<Node<T>> stack=new Stack<Node<T>>();
Node<T> currentNode=this.node;
while(currentNode !=null) {
stack.push(currentNode);
currentNode=currentNode.getNode();
}
// clear the linked list.
this.node = null;
this.size = 0;
//Pop the data from Stack and add it to linked list
if(!stack.empty()) {
Node<T> rootNode=stack.pop();
Node<T> previousNode=rootNode;
currentNode=rootNode;
while(!stack.empty()) {
currentNode = stack.pop();
previousNode.setNode(currentNode);
previousNode=currentNode;
}
previousNode.setNode(null);
this.node=rootNode;
}
}
/**
* Add element at last.
*
* @param data
*/
public void add(T data) {
if (data == null) {
return;
}
if (node == null) {
node = new Node<T>(data);
} else {
Node<T> newNode = new Node<T>(data);
Node<T> lastNode = getLastNode(node);
lastNode.setNode(newNode);
}
size++;
}
/**
* Add element at first. set the newly created node as root node
*
* @param data
*/
public void addAtFirst(T data) {
if (data == null) {
return;
}
Node<T> newNode = new Node<T>(data);
if (this.node != null) {
newNode.setNode(this.node);
this.node = newNode;
} else {
this.node = newNode;
}
size++;
}
/**
* Add the element at specified index. Index start from 0 to n-1 where n=size of
* linked list. If index is negative value, nothing will be added to linked
* list.
*
* if index =0 , element will be added at head and element become the first
* node.
*
* @param data
* @param index
* - index at which element to be added.
*/
public void add(T data, int index) throws IndexOutOfBoundsException {
if (data == null) {
return;
}
// If index=0 , we should add the data at head
if (index == 0) {
addAtFirst(data);
return;
}
// If index= size, we should add the data at last
if (index == this.size) {
add(data);
} else if (index < this.size) {
Node<T> newNode = new Node<T>(data);
// get the node at (index) from linked list and mark as rightNode.
// get the node at (index-1) from linked list and mark as leftNode.
// set node of newly created node as right node.
// set node of left nose as newly created Node.
Node<T> leftNode = getNode(index - 1);
Node<T> rightNode = getNode(index);
newNode.setNode(rightNode);
leftNode.setNode(newNode);
size++;
} else {
throw new IndexOutOfBoundsException("Index not available.");
}
}
public T get(int index) {
return getNode(index).getData();
}
/**
* Returns the index of data. Index starts from 0 to n. If data not found in
* list, return -1
*
* @param data
* @return
*/
public int indexof(T data) {
Node<T> pointerNode = this.node;
int index = 0;
while (pointerNode != null && pointerNode.getData() != null) {
if (pointerNode.getData().equals(data)) {
return index;
} else {
pointerNode = pointerNode.getNode();
index++;
}
}
return -1;
}
private Node<T> getNode(int index) {
if (index < 0 || index > this.size - 1) {
throw new IndexOutOfBoundsException("Index not available.");
}
// If index=0 , return head
if (index == 0) {
return this.node;
}
// If index= size, return last node
if (index == this.size - 1) {
return getLastNode(this.node);
}
int pointer = 0;
Node<T> pointerNode = this.node;
while (pointer <= index) {
if (pointer == index) {
return pointerNode;
} else {
pointerNode = next(pointerNode);
pointer++;
}
}
return null;
}
private Node<T> getLastNode(Node<T> node) {
Node<T> lastNode = node;
if (lastNode.getNode() != null) {
return getLastNode(lastNode.getNode());
} else {
return lastNode;
}
}
private Node<T> next(Node<T> node) {
if (node.getNode() != null) {
return node.getNode();
} else {
return null;
}
}
public int size() {
return this.size;
}
/**
* Delete the first occurrence of element from linked list if exists and returns
* true. If data not available , it returns false;
*
* @param data
* @return
*/
public boolean delete(T data) {
if (this.node == null) {
return false;
}
Node<T> pointerNode = this.node;
// If input data is the head of linked list.
if (pointerNode.getData().equals(data)) {
this.node = next(pointerNode);
size--;
return true;
}
int indexofData = indexof(data);
if(indexofData >0 ) {
return deleteByIndex(indexofData);
}
else {
return false;
}
}
/**
* Delete the data by index.
*
* @param index
* @return
*/
public boolean deleteByIndex(int index) {
if (this.node == null) {
return false;
}
if (index < 0 || index > this.size - 1) {
throw new IndexOutOfBoundsException("Index not available.");
}
// If index=0 , put head node = Node at index 1.
if (index == 0) {
if(this.node.getNode()!=null) {
this.node = getNode(index + 1);
}else {
this.node=null;
}
size--;
return true;
}
// If index= size -1 means need to delete last node, get the 2nd last node and
// set next node as null.
if (index == this.size - 1) {
getNode(index - 1).setNode(null);
size--;
return true;
}
// if index is in between 0 and size of linked list , set Node of leftNode as
// rightNode
Node<T> leftNode = getNode(index - 1);
Node<T> rightNode = getNode(index + 1);
leftNode.setNode(rightNode);
size--;
return true;
}
/**
* Clear the linked list
*/
public void clear() {
this.node = null;
this.size = 0;
}
@Override
public String toString() {
String represent = "[";
Node<T> nextNode = this.node;
while (nextNode != null) {
represent = represent + nextNode.toString();
nextNode = next(nextNode);
if (nextNode != null) {
represent = represent + ",";
}
}
represent = represent + "]";
return represent;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((node == null) ? 0 : node.hashCode());
result = prime * result + size;
return result;
}
/**
* Two linked list is equal when their size is equals and both have similar node structure
*/
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (!(obj instanceof SinglyLinkedList))
return false;
SinglyLinkedList other = (SinglyLinkedList) obj;
if (node == null) {
if (other.node != null)
return false;
} else if (!node.equals(other.node))
return false;
if (size != other.size)
return false;
return true;
}
}
package com.study.DTO;
public class Item {
private Integer itemId;
private String itemName;
private Double price;
public Item(Integer itemId, String itemName, Double price) {
super();
this.itemId = itemId;
this.itemName = itemName;
this.price = price;
}
public Integer getItemId() {
return itemId;
}
public void setItemId(Integer itemId) {
this.itemId = itemId;
}
public String getItemName() {
return itemName;
}
public void setItemName(String itemName) {
this.itemName = itemName;
}
public Double getPrice() {
return price;
}
public void setPrice(Double price) {
this.price = price;
}
@Override
public String toString() {
return "Item [itemId=" + itemId + ", itemName=" + itemName + ", price=" + price + "]";
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((itemId == null) ? 0 : itemId.hashCode());
result = prime * result + ((itemName == null) ? 0 : itemName.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (!(obj instanceof Item))
return false;
Item other = (Item) obj;
if (itemId == null) {
if (other.itemId != null)
return false;
} else if (!itemId.equals(other.itemId))
return false;
if (itemName == null) {
if (other.itemName != null)
return false;
} else if (!itemName.equals(other.itemName))
return false;
return true;
}
}
package com.study.singlyLinkedList;
import com.study.DTO.Item;
public class TestSinglyLinkedList {
public static void main(String[] args) {
SinglyLinkedList<Item> linkedList=new SinglyLinkedList<Item>();
linkedList.add(new Item(101, "IPhone-5S", 200.00));
linkedList.add(new Item(102, "IPhone-6S", 500.00));
linkedList.add(new Item(103, "IPhone-XX", 1000.00));
linkedList.add(new Item(104, "IPad", 500.00));
linkedList.add(new Item(105, "IPod", 500.00));
System.out.println("Original List: "+ linkedList);
System.out.println(" ");
Item middleItem=linkedList.getMiddle();
System.out.println("Middle Item : " + middleItem);
}
}
Output:
Original List: [Item [itemId=101, itemName=IPhone-5S, price=200.0],Item [itemId=102, itemName=IPhone-6S, price=500.0],Item [itemId=103, itemName=IPhone-XX, price=1000.0],Item [itemId=104, itemName=IPad, price=500.0],Item [itemId=105, itemName=IPod, price=500.0]]
Middle Item : Item [itemId=103, itemName=IPhone-XX, price=1000.0]
**************************************************************************************
There are many uses of getting the middle element of linear data structures like Binary search and Merge sort. In next post, we will discuss about sorting of Singly Linked list.
Hope you like this post. Please leave your comments/suggestions.
You may like –
- Singly Linked List Implementation using in java.
- Singly Linked List Implementation using generics in Java.
- Delete/Remove operations in Linked list
- Reverse a Singly Linked List.
- Merge sort for Linked List in Java.
- Remove duplicate node from linked list.
- Rotation of Linked List.
- Intersection of two linked lists.
- Iterator for singly linked list java.
