CC-16 : Simulate RingBuffer using a CircularSingleLinkedList.
Description:
Write and test code for a Ring buffer of size 5:
As ring buffer is of size 5, maximum 5 data values/ nodes can be stored in it.
Last node of Ring buffer points back to first node.
Ring buffer with 3 items : “11->44->97”. First node is node with data value “11”.
Ring buffer with 5 items “11->44->97->31->66”. First node is node with data value “11”.
Ring buffer when 6th data value “45” is added “44->97->31->66->45”. Node with value “11” has been removed from the Ring buffer.
Ring buffer when 7th data value “57” is added “45->97->31->66->57”. Node with value “44” has been removed from the Ring buffer.
Test cases and expected outputs:
| Input Parameters |
Expected outputs |
| Add these nodes one by one to RingBuffer and check its contents after each add operation:
1->2->3->4->5->6->7->8
|
Ring Buffer:1< last node points to first node>
Ring Buffer:1->2 (last node points to first node)
Ring Buffer:1->2->3 (last node points to first node)
Ring Buffer:1->2->3->4 (last node points to first node)
Ring Buffer:1->2->3->4->5 (last node points to first node)
Ring Buffer:2->3->4->5->6 (last node points to first node)
Ring Buffer:3->4->5->6->7 (last node points to first node)
Ring Buffer:4->5->6->7->8 (last node points to first node)
|
Pseudocode:
| Initialize a CircularSingleLinkedList to implement the Ring Buffer.
|
| If CircularSingleLinkedList size is <5, add node to end of CircularSingleLinkedList.
|
| If CircularSingleLinkedList size is =5:
Add node to end of CircularSingleLinkedList.
Remove linkage to original firstNode of CircularSingleLinkedList.
Add linkage to original second node of CircularSingleLinkedList.
Set the second original node as “firstNode” of CircularSingleLinkedList (this means original first node of CircularSingleLinkedList has been removed from the RingBuffer.
|
| Note: Ring Buffer size should never exceed 5 nodes.
|
Code:
public class CircularSingleLinkedListRingBuffer {
CircularSingleLinkedList circularSingleLinkedList=this.new CircularSingleLinkedList();
public void circularSingleLinkedListRingBuffer(int addToBuffer) throws Exception{
int nodeCount=0;
SingleLinkedListNode currentNode=circularSingleLinkedList.getFirstNode();
if (currentNode!=null) {nodeCount=1;}
while ((currentNode !=null) && (currentNode.getNextNode()
!= circularSingleLinkedList.getFirstNode())) {
nodeCount++;
currentNode=currentNode.getNextNode();
}
if ((nodeCount>=0)&&(nodeCount<5)) {
circularSingleLinkedList.addLast(addToBuffer);
}
if (nodeCount==5) {
circularSingleLinkedList.removeFirst();
circularSingleLinkedList.addLast(addToBuffer);
}
}
}
Click here to download and run code and test cases !
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 CircularLinkedList and SingleLinkedListNode as internal classes. Ideally both these classes should be separate public classes.
public class CircularSingleLinkedListRingBuffer {
CircularSingleLinkedList circularSingleLinkedList=this.new CircularSingleLinkedList();
public void circularSingleLinkedListRingBuffer(int addToBuffer) throws Exception{
int nodeCount=0;
SingleLinkedListNode currentNode=circularSingleLinkedList.getFirstNode();
if (currentNode!=null) {nodeCount=1;}
while ((currentNode !=null) && (currentNode.getNextNode()
!= circularSingleLinkedList.getFirstNode())) {
nodeCount++;
currentNode=currentNode.getNextNode();
}
if ((nodeCount>=0)&&(nodeCount<5)) {
circularSingleLinkedList.addLast(addToBuffer);
}
if (nodeCount==5) {
circularSingleLinkedList.removeFirst();
circularSingleLinkedList.addLast(addToBuffer);
}
}
public static void main(String[] args) {
try {
CircularSingleLinkedListRingBuffer circularSingleLinkedListRingBuffer=new CircularSingleLinkedListRingBuffer();
circularSingleLinkedListRingBuffer.circularSingleLinkedListRingBuffer(1);
circularSingleLinkedListRingBuffer.circularSingleLinkedList.printSingleLinkList("Ring Buffer:");
circularSingleLinkedListRingBuffer.circularSingleLinkedListRingBuffer(2);
circularSingleLinkedListRingBuffer.circularSingleLinkedList.printSingleLinkList("Ring Buffer:");
circularSingleLinkedListRingBuffer.circularSingleLinkedListRingBuffer(3);
circularSingleLinkedListRingBuffer.circularSingleLinkedList.printSingleLinkList("Ring Buffer:");
circularSingleLinkedListRingBuffer.circularSingleLinkedListRingBuffer(4);
circularSingleLinkedListRingBuffer.circularSingleLinkedList.printSingleLinkList("Ring Buffer:");
circularSingleLinkedListRingBuffer.circularSingleLinkedListRingBuffer(5);
circularSingleLinkedListRingBuffer.circularSingleLinkedList.printSingleLinkList("Ring Buffer:");
circularSingleLinkedListRingBuffer.circularSingleLinkedListRingBuffer(6);
circularSingleLinkedListRingBuffer.circularSingleLinkedList.printSingleLinkList("Ring Buffer:");
circularSingleLinkedListRingBuffer.circularSingleLinkedListRingBuffer(7);
circularSingleLinkedListRingBuffer.circularSingleLinkedList.printSingleLinkList("Ring Buffer:");
circularSingleLinkedListRingBuffer.circularSingleLinkedListRingBuffer(8);
circularSingleLinkedListRingBuffer.circularSingleLinkedList.printSingleLinkList("Ring Buffer:");
}catch (Exception exception) {
System.out.print("Exception: "+ exception);
}
}
class CircularSingleLinkedList {
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(firstNode);
return true;
}
else {
SingleLinkedListNode currentNode=firstNode;
while (currentNode.getNextNode()!=firstNode) {currentNode=currentNode.getNextNode();}
currentNode.setNextNode(node);
node.setNextNode(firstNode);
return true;
}
}
public boolean addFirst(int data){
SingleLinkedListNode node=new SingleLinkedListNode();
node.setNodeData(data);
if (firstNode==null) {
firstNode=node;
node.setNextNode(firstNode);
return true;
}
else {
SingleLinkedListNode currentNode=firstNode;
while (currentNode.getNextNode()!=firstNode) {currentNode=currentNode.getNextNode();}
currentNode.setNextNode(node);;
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;
}
if (firstNode==null) {return false;}
SingleLinkedListNode node=new SingleLinkedListNode();
node.setNodeData(data);
SingleLinkedListNode currentNode=firstNode;
SingleLinkedListNode prevNode=null;
int idx=0;
do {
if ((idx==pos)){
node.setNextNode(prevNode.getNextNode());
prevNode.setNextNode(node);
return true;
}
prevNode=currentNode;
currentNode=currentNode.getNextNode();
idx++;
} while (currentNode !=firstNode);
return false;
}
public int getSize() {
if (firstNode == null) { return 0; }
SingleLinkedListNode currentNode=firstNode;
int idx=0;
do {
currentNode=currentNode.getNextNode();
idx++;
}while (currentNode !=firstNode) ;
return idx;
}
public boolean removeFirst() {
if (firstNode == null) { return false; }
if (firstNode.getNextNode()==firstNode) {
firstNode=null;
return true;
}
SingleLinkedListNode currentNode=firstNode;
while (currentNode.getNextNode()!=firstNode) {
currentNode=currentNode.getNextNode(); }
currentNode.setNextNode(firstNode.getNextNode());
firstNode=firstNode.getNextNode();
return true;
}
public boolean removeLast() {
if (firstNode == null) { return false; }
SingleLinkedListNode currentNode=firstNode;
SingleLinkedListNode prevNode=null;
do {
if (currentNode.getNextNode()==firstNode) {
if (prevNode==null) {
firstNode=null;
return true;
}
prevNode.setNextNode(firstNode);
return true;
}
prevNode=currentNode;
currentNode=currentNode.getNextNode();
} while (currentNode !=firstNode);
return false;
}
public boolean remove(int data){
if (firstNode == null) { return false; }
SingleLinkedListNode currentNode=firstNode;
SingleLinkedListNode prevNode=null;
do {
if (currentNode.getNodeData() == data) {
if (prevNode==null) {
removeFirst();
return true;
}
if (currentNode.getNextNode()==firstNode) {
removeLast();
return true;
}
prevNode.setNextNode(currentNode.getNextNode());
return true;
}
prevNode=currentNode;
currentNode=currentNode.getNextNode();
} while (currentNode !=firstNode);
return false;
}
public boolean removeAtPos(int pos){
if (firstNode == null) { return false; }
SingleLinkedListNode currentNode=firstNode;
SingleLinkedListNode prevNode=null;
int idx=0;
do {
if (idx==pos) {
if (prevNode==null) {
removeFirst();
return true;
}
if (currentNode.getNextNode()==firstNode) {
removeLast();
return true;
}
prevNode.setNextNode(currentNode.getNextNode());
return true;
}
prevNode=currentNode;
currentNode=currentNode.getNextNode();
idx++;
} while (currentNode !=firstNode);
return false;
}
public int get(int idx) {
if (firstNode == null) { return Integer.MIN_VALUE; }
SingleLinkedListNode currentNode=firstNode;
int currIdx=0;
do {
if (currIdx==idx) {return currentNode.getNodeData();}
currentNode=currentNode.getNextNode();
currIdx++;
}while (currentNode !=firstNode);
return Integer.MIN_VALUE;
}
public void traverse() {
SingleLinkedListNode currentNode=firstNode;
do{
System.out.println(currentNode.getNodeData());
currentNode=currentNode.getNextNode();
}while (currentNode !=firstNode);
}
public void printSingleLinkList() throws Exception {
// Case 1: The Circular Linked list is empty !!
if (firstNode == null) { System.out.println("Circular Linked list empty"); return; }
// Case 2: Print CircularLinkedList node by node
SingleLinkedListNode currentNode=firstNode;
System.out.println();
System.out.println("**************************************************************************************************");
System.out.print("CircularSingleLinkedList nodes: ");
do {
System.out.print(currentNode.getNodeData());
if (currentNode.getNextNode() != firstNode) System.out.print(" -> ");
currentNode=currentNode.getNextNode();
} while( currentNode != firstNode);
System.out.print("<last node points to first node>");
System.out.println();
System.out.println("**************************************************************************************************");
System.out.println();
Thread.sleep(2000);
;
return;
}
public void printSingleLinkList(String labelText) throws Exception {
// Case 1: The Circular Linked list is empty !!
if (firstNode == null) { System.out.println("Circular Linked list empty"); return; }
// Case 2: Print CircularLinkedList node by node
SingleLinkedListNode currentNode=firstNode;
System.out.println();
System.out.println("**************************************************************************************************");
System.out.print(labelText);
do {
System.out.print(currentNode.getNodeData());
if (currentNode.getNextNode() != firstNode) System.out.print(" -> ");
currentNode=currentNode.getNextNode();
} while( currentNode != firstNode);
System.out.print("<last node points to first node>");
System.out.println();
System.out.println("**************************************************************************************************");
System.out.println();
Thread.sleep(2000);
;
return;
}
}
class SingleLinkedListNode {
private SingleLinkedListNode nextNode=null;
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;
}
}
}