Given a DoubleLinkedList with integer data with size N nodes, node at index i and N-1-i are index twins. Find the index twins with maximum sum in the DoubleLinkedList.
| Input Parameters |
Expected outputs |
| 8->44->7->3->11->2->17->15->12->19
|
Maximum twin sum is : 56
|
| 8->44->8->44
|
Maximum twin sum is : 52
|
| 8->7
|
Maximum twin sum is : 15
|
| 8
|
Twin sum not possible
|
| Check that the DoubleLinkedList has even number of nodes before progressing with these rest of the implementation.
|
| Define variable of maxSum as maximumSum of twins that are found in DoubleLinkedList.
|
| Define variable forwNode as firstNode of DoubleLinkedList and variable revNode as lastNode of the DoubleLinkedList.
|
| Next set of twins can be found by forwNode.nextNode and revNode.prevNode.
|
| Repeat below steps for twins in the DoublLinkedList:
forwNode and revNode are twins, store the sum of their node data in currSum.
If currSum > maxSum, then set maxSum to currSum.
|
| After all twins are compared maxSum will contain the maximum possible sum of twins in the DoubleLinkedList.
|
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.
Note: For easier code execution and easier reference, the class below contains code for DoubleLInkedList and DoubleLinkedListNode as internal classes. Ideally both these classes should be separate public classes.
public class DoubleLinkedListMaximumSumTwin {
public int doubleLinkedListMaximumSumTwin(DoubleLinkedList doubleLinkedList) throws Exception{
if (doubleLinkedList.getFirstNode()==null) { return Integer.MIN_VALUE;}
int cnt= doubleLinkedList.getSize(); int idx=0;
int currSum=0; int maxSum=0;
if (cnt % 2 != 0) { return Integer.MIN_VALUE;}
DoubleLinkedListNode forwNode=doubleLinkedList.getFirstNode();
DoubleLinkedListNode revNode=doubleLinkedList.getLastNode();
while (idx <= cnt/2-1) {
currSum=forwNode.getNodeData()+revNode.getNodeData();
if (currSum > maxSum) {
maxSum=currSum;
}
idx++;
forwNode=forwNode.getNextNode();
revNode=revNode.getPreviousNode();
}
return maxSum;
}
public static void main(String[] args) {
int retVal;
try {
DoubleLinkedListMaximumSumTwin doubleLinkedListMaximumSumTwin=new DoubleLinkedListMaximumSumTwin();
DoubleLinkedList doubleLinkedList=doubleLinkedListMaximumSumTwin.new DoubleLinkedList();
doubleLinkedList.addLast(8);
doubleLinkedList.addLast(44);
doubleLinkedList.addLast(7);
doubleLinkedList.addLast(3);
doubleLinkedList.addLast(11);
doubleLinkedList.addLast(2);
doubleLinkedList.addLast(17);
doubleLinkedList.addLast(15);
doubleLinkedList.addLast(12);
doubleLinkedList.addLast(19);
doubleLinkedList.printDoubleLinkListForwardDirection();
retVal=doubleLinkedListMaximumSumTwin.doubleLinkedListMaximumSumTwin(doubleLinkedList);
System.out.println("Maximum twin sum is : "+ retVal);
doubleLinkedList=doubleLinkedListMaximumSumTwin.new DoubleLinkedList();
doubleLinkedList.addLast(8);
doubleLinkedList.addLast(44);
doubleLinkedList.addLast(8);
doubleLinkedList.addLast(44);
doubleLinkedList.printDoubleLinkListForwardDirection();
doubleLinkedListMaximumSumTwin=new DoubleLinkedListMaximumSumTwin();
retVal=doubleLinkedListMaximumSumTwin.doubleLinkedListMaximumSumTwin(doubleLinkedList);
System.out.println("Maximum twin sum is : "+ retVal);
doubleLinkedList=doubleLinkedListMaximumSumTwin.new DoubleLinkedList();
doubleLinkedList.addLast(8);
doubleLinkedList.addLast(7);
doubleLinkedList.printDoubleLinkListForwardDirection();
doubleLinkedListMaximumSumTwin=new DoubleLinkedListMaximumSumTwin();
retVal=doubleLinkedListMaximumSumTwin.doubleLinkedListMaximumSumTwin(doubleLinkedList);
System.out.println("Maximum twin sum is : "+ retVal);
doubleLinkedList=doubleLinkedListMaximumSumTwin.new DoubleLinkedList();
doubleLinkedList.addLast(8);
doubleLinkedList.printDoubleLinkListForwardDirection();
doubleLinkedListMaximumSumTwin=new DoubleLinkedListMaximumSumTwin();
retVal=doubleLinkedListMaximumSumTwin.doubleLinkedListMaximumSumTwin(doubleLinkedList);
System.out.println("Maximum twin sum is : "+ retVal);
}catch (Exception exception) {
System.out.print("Exception: "+ exception);
}
}
class DoubleLinkedList {
private DoubleLinkedListNode firstNode=null;
public DoubleLinkedListNode getFirstNode() {
return firstNode;
}
public void setFirstNode(DoubleLinkedListNode firstNode) {
this.firstNode = firstNode;
}
public DoubleLinkedListNode getLastNode() {
DoubleLinkedListNode currentNode=firstNode;
DoubleLinkedListNode prevNode=null;
while (currentNode !=null) {
prevNode=currentNode;
currentNode=currentNode.getNextNode();
}
return prevNode;
}
public boolean addLast(int data){
DoubleLinkedListNode node=new DoubleLinkedListNode();
node.setNodeData(data);
if (firstNode==null) {
firstNode=node;
node.setNextNode(null);
node.setPreviousNode(null);
return true;
}
else {
DoubleLinkedListNode currentNode=firstNode;
while (currentNode.getNextNode()!=null) {currentNode=currentNode.getNextNode();}
node.setPreviousNode(currentNode);
currentNode.setNextNode(node);
node.setNextNode(null);
return true;
}
}
public boolean addFirst(int data){
DoubleLinkedListNode node=new DoubleLinkedListNode();
node.setNodeData(data);
if (firstNode==null) {
firstNode=node;
node.setNextNode(null);
node.setPreviousNode(null);
return true;
}else {
node.setNextNode(firstNode);
firstNode.setPreviousNode(node);
firstNode=node;
node.setPreviousNode(null);
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;
}
DoubleLinkedListNode node=new DoubleLinkedListNode();
node.setNodeData(data);
DoubleLinkedListNode currentNode=firstNode;
DoubleLinkedListNode prevNode=null;
int idx=0;
while (currentNode !=null) {
if ((idx==pos)){
node.setNextNode(prevNode.getNextNode());
prevNode.setNextNode(node);
//setup previous node linkages
node.getNextNode().setPreviousNode(node);
node.setPreviousNode(prevNode);
return true;
}
prevNode=currentNode;
currentNode=currentNode.getNextNode();
idx++;
}
return false;
}
public int getSize() {
DoubleLinkedListNode 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();
firstNode.setPreviousNode(null);
return true;
}
public boolean removeLast() {
if (firstNode == null) { return false; }
DoubleLinkedListNode currentNode=firstNode;
DoubleLinkedListNode prevNode=null;
while (currentNode !=null) {
if (currentNode.getNextNode()==null) {
if (prevNode==null) {
firstNode=null;
return true;
}
prevNode.setNextNode(null);
currentNode.setPreviousNode(null);
return true;
}
prevNode=currentNode;
currentNode=currentNode.getNextNode();
}
return false;
}
public boolean remove(int data){
DoubleLinkedListNode currentNode=firstNode;
DoubleLinkedListNode 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());
prevNode.getNextNode().setPreviousNode(prevNode);
return true;
}
prevNode=currentNode;
currentNode=currentNode.getNextNode();
}
return false;
}
public boolean removeAtPos(int pos){
DoubleLinkedListNode currentNode=firstNode;
DoubleLinkedListNode 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) {
DoubleLinkedListNode currentNode=firstNode;
int currIdx=0;
while (currentNode !=null) {
if (currIdx==idx) {return currentNode.getNodeData();}
currentNode=currentNode.getNextNode();
currIdx++;
}
return Integer.MIN_VALUE;
}
public void traverseForward() {
DoubleLinkedListNode currentNode=firstNode;
while (currentNode !=null) {
System.out.println(currentNode.getNodeData());
currentNode=currentNode.getNextNode();
}
}
// print DoubleLinkList forward direction
public void printDoubleLinkListForwardDirection() throws Exception {
// Case 1: The Linked list is empty !!
if (firstNode == null) { System.out.println("Double Linked list empty"); return; }
// Case 2: Print Double LinkedList node by node (first to last)
DoubleLinkedListNode currentNode=firstNode;
System.out.println();
System.out.println("****************************************************************************");
System.out.print("DoubleLinkedList nodes (first node to last node): ");
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;
}
// print DoubleLinkList backward direction
public void printDoubleLinkListBackwardDirection() throws Exception {
// Case 1: The Linked list is empty !!
if (firstNode == null) { System.out.println("Double Linked list empty"); return; }
// Case 2: Print Double LinkedList node by node (last to first)
// This while loop executes till we reach last node in the LinkedList
DoubleLinkedListNode currentNode=firstNode;
while (currentNode.getNextNode()!=null) {currentNode=currentNode.getNextNode();}
//currentNode is at end of LinkedList
System.out.println();
System.out.println("****************************************************************************");
System.out.print("DoubleLinkedList nodes (last node to first node): ");
do {
System.out.print(currentNode.getNodeData());
if (currentNode != firstNode) System.out.print(" -> ");
currentNode=currentNode.getPreviousNode();
} while( currentNode != null);
System.out.println();
System.out.println("****************************************************************************");
System.out.println();
Thread.sleep(2000);
;
return;
}
}
class DoubleLinkedListNode {
private DoubleLinkedListNode nextNode=null;
private DoubleLinkedListNode previousNode=null;
private int nodeData=0;
public DoubleLinkedListNode getNextNode() {
return nextNode;
}
public void setNextNode(DoubleLinkedListNode nextNode) {
this.nextNode = nextNode;
}
public DoubleLinkedListNode getPreviousNode() {
return previousNode;
}
public void setPreviousNode(DoubleLinkedListNode previousNode) {
this.previousNode = previousNode;
}
public int getNodeData() {
return nodeData;
}
public void setNodeData(int nodeData) {
this.nodeData = nodeData;
}
}
}