Given a SingleLinkedList with integer data, add new nodes one by one to the SingleLinkedList. As the nodes are added, list should also be sorted in integer ascending order
| If the SingleLinkedList is initially empty, add the new node as the first node of the SingleLinkedList.
|
| If next new node’s integer data to be added to SingleLinkedList is smaller than the first node’s integer data, then point the new node’s next link to the firstNode and update firstNode reference to point to new node.
|
| Else, to insert new node in SingleLinkedList, start from first node of SingleLinkedList and traverse the SingleLinkedList nodes via “nextNode” links till you reach a node that’s integer value is greater than the integer value of new node to be inserted. Set this node to variable “currentNode” and its previous node to variable “previousNode”. Now the new node needs to be inserted between “previousNode” and “currentNode” to maintain ascending integer sort order of the SingleLinkedList.
|
| If while traversing the SingleLinkedList we do not come across any integer greater than the integer data value of the new node, in this case, the new node can be added to end of the existing SingleLinkedList.
|
Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it.
Be sure to try your own test cases to enhance your understanding !
You can also tweak the code to optimize or add enhancements and custom features.
public class SingleLinkedListInsertionSort {
public void addIntToSingleLinkListWithInsertionSort(SingleLinkedList singleLinkedList, int add) throws Exception{
if (singleLinkedList.getFirstNode()==null) {
singleLinkedList.addFirst(add);
return;
}
if (singleLinkedList.getFirstNode().getNodeData()>=add) {
singleLinkedList.addFirst(add);
return;
}
SingleLinkedListNode currNode=singleLinkedList.getFirstNode();
SingleLinkedListNode prevNode=null;
while (( currNode != null) && (currNode.getNodeData() < add)) {
prevNode=currNode;
currNode=currNode.getNextNode();
}
SingleLinkedListNode node=new SingleLinkedListNode();
node.setNodeData(add);
if (currNode != null) {
prevNode.setNextNode(node);
node.setNextNode(currNode);
return;
}
if (currNode == null){
singleLinkedList.addLast(add);
return;
}
}
public static void main(String[] args) {
try {
SingleLinkedListInsertionSort singleLinkedListInsertionSort=new SingleLinkedListInsertionSort();
SingleLinkedList singleLinkedList=singleLinkedListInsertionSort.new SingleLinkedList();
System.out.print("Add with Insertion sort");
singleLinkedListInsertionSort.addIntToSingleLinkListWithInsertionSort(singleLinkedList,9);
singleLinkedList.printSingleLinkList();
System.out.print("Add with Insertion sort");
singleLinkedListInsertionSort.addIntToSingleLinkListWithInsertionSort(singleLinkedList,15);
singleLinkedList.printSingleLinkList();
System.out.print("Add with Insertion sort");
singleLinkedListInsertionSort.addIntToSingleLinkListWithInsertionSort(singleLinkedList,3);
singleLinkedList.printSingleLinkList();
System.out.print("Add with Insertion sort");
singleLinkedListInsertionSort.addIntToSingleLinkListWithInsertionSort(singleLinkedList,12);
singleLinkedList.printSingleLinkList();
System.out.print("Add with Insertion sort");
singleLinkedListInsertionSort.addIntToSingleLinkListWithInsertionSort(singleLinkedList,44);
singleLinkedList.printSingleLinkList();
System.out.print("Add with Insertion sort");
singleLinkedListInsertionSort.addIntToSingleLinkListWithInsertionSort(singleLinkedList,23);
singleLinkedList.printSingleLinkList();
}catch (Exception exception) {
System.out.print("Exception: "+ exception);
}
}
class SingleLinkedList {
private SingleLinkedListNode firstNode=null;
public SingleLinkedListNode getFirstNode() {
return firstNode;
}
public void setFirstNode(SingleLinkedListNode firstNode) {
this.firstNode = firstNode;
}
public boolean addLast(int data){
SingleLinkedListNode node=new SingleLinkedListNode();
node.setNodeData(data);
if (firstNode==null) {
firstNode=node;
node.setNextNode(null);
return true;
}
else {
SingleLinkedListNode currentNode=firstNode;
while (currentNode.getNextNode()!=null) {currentNode=currentNode.getNextNode();}
currentNode.setNextNode(node);
node.setNextNode(null);
return true;
}
}
public boolean addFirst(int data){
SingleLinkedListNode node=new SingleLinkedListNode();
node.setNodeData(data);
if (firstNode==null) {
firstNode=node;
node.setNextNode(null);
return true;
}
else {
node.setNextNode(firstNode);
firstNode=node;
return true;
}
}
public boolean add(int data, int pos)
{
int size=getSize();
if ((pos<0) || (pos > size)) { return false;}
if (pos==0) {
addFirst(data);
return true;
}
if (pos==size) {
addLast(data);
return true;
}
SingleLinkedListNode node=new SingleLinkedListNode();
node.setNodeData(data);
SingleLinkedListNode currentNode=firstNode;
SingleLinkedListNode prevNode=null;
int idx=0;
while (currentNode !=null) {
if ((idx==pos)){
node.setNextNode(prevNode.getNextNode());
prevNode.setNextNode(node);
return true;
}
prevNode=currentNode;
currentNode=currentNode.getNextNode();
idx++;
}
return false;
}
public int getSize() {
SingleLinkedListNode currentNode=firstNode;
int idx=0;
while (currentNode !=null) {
currentNode=currentNode.getNextNode();
idx++;
}
return idx;
}
public boolean removeFirst() {
if (firstNode == null) { return false; }
if (firstNode.getNextNode()==null) {
firstNode=null;
return true;
}
firstNode=firstNode.getNextNode();
return true;
}
public boolean removeLast() {
if (firstNode == null) { return false; }
SingleLinkedListNode currentNode=firstNode;
SingleLinkedListNode prevNode=null;
while (currentNode !=null) {
if (currentNode.getNextNode()==null) {
if (prevNode==null) {
firstNode=null;
return true;
}
prevNode.setNextNode(null);
return true;
}
prevNode=currentNode;
currentNode=currentNode.getNextNode();
}
return false;
}
public boolean remove(int data){
SingleLinkedListNode currentNode=firstNode;
SingleLinkedListNode prevNode=null;
while (currentNode !=null) {
if (currentNode.getNodeData() == data) {
if (prevNode==null) {
removeFirst();
return true;
}
if (currentNode.getNextNode()==null) {
removeLast();
return true;
}
prevNode.setNextNode(currentNode.getNextNode());
return true;
}
prevNode=currentNode;
currentNode=currentNode.getNextNode();
}
return false;
}
public boolean removeAtPos(int pos){
SingleLinkedListNode currentNode=firstNode;
SingleLinkedListNode prevNode=null;
int idx=0;
while (currentNode !=null) {
if (idx==pos) {
if (prevNode==null) {
removeFirst();
return true;
}
if (currentNode.getNextNode()==null) {
removeLast();
return true;
}
prevNode.setNextNode(currentNode.getNextNode());
return true;
}
prevNode=currentNode;
currentNode=currentNode.getNextNode();
idx++;
}
return false;
}
public int get(int idx) {
SingleLinkedListNode currentNode=firstNode;
int currIdx=0;
while (currentNode !=null) {
if (currIdx==idx) {return currentNode.getNodeData();}
currentNode=currentNode.getNextNode();
currIdx++;
}
return Integer.MIN_VALUE;
}
public void traverse() {
SingleLinkedListNode currentNode=firstNode;
while (currentNode !=null) {
System.out.println(currentNode.getNodeData());
currentNode=currentNode.getNextNode();
}
}
// print SingleLinkList
public void printSingleLinkList() throws Exception {
// Case 1: The Linked list is empty !!
if (firstNode == null) { System.out.println("Linked list empty"); return; }
// Case 2: Print LinkedList node by node
SingleLinkedListNode currentNode=firstNode;
System.out.println();
System.out.println("*************************************************************************");
System.out.print("SingleLinkedList nodes: ");
do {
System.out.print(currentNode.getNodeData());
if (currentNode.getNextNode() != null) System.out.print(" -> ");
currentNode=currentNode.getNextNode();
} while( currentNode != null);
System.out.println();
System.out.println("*********************************************************************");
System.out.println();
Thread.sleep(2000);
;
return;
}
}
class SingleLinkedListNode {
private SingleLinkedListNode nextNode=null;
//This is the data stored by Linked list. Replace it by String, array , or any other datatype as per need
private int nodeData=0;
public SingleLinkedListNode getNextNode() {
return nextNode;
}
public void setNextNode(SingleLinkedListNode nextNode) {
this.nextNode = nextNode;
}
public int getNodeData() {
return nodeData;
}
public void setNodeData(int nodeData) {
this.nodeData = nodeData;
}
}
}