-------------------- IntLinkList : public class IntLinkList { private IntNode to
ID: 3918535 • Letter: #
Question
--------------------
IntLinkList :
public class IntLinkList {
private IntNode top; //The reference to the first Node
//=========== Solution code =============================
public IntLinkList(int[] data){
for (int i = 0; i<data.length; i++){
add(data[i]);
}
}
public boolean empty(){
if (top == null)
return true;
return false;
}
public int first(){
return top.getData();
}
public void removeFirst(){
if (top != null)
top = top.getLink();
}
public IntLinkList clone(){
IntLinkList a = new IntLinkList();
if (top != null){
IntNode p = top;
while (p != null){
a.add(p.getData());
p = p.getLink();
}
}
return a;
}
private static boolean equals(IntNode top1, IntNode top2){
//Your code here
return false; //Dummy statement for testing - remove it.
}
//=========== Supplied code =============================
public IntLinkList() {
//A constructor that creates an empty list.
top = null;
}
public void add(int newItem) {
//Add the newItem at the FRONT of the list.
top = new IntNode(newItem,top);
}//add
public String toString() {
String answer = "<<";
IntNode next = top;
while(next!=null){
answer += next.getData()+" ";
next = next.getLink();
}
return answer+">>";
}
public void ordInsert(int newItem) {
//Add the newItem so that the list remains sorted into
//ascending order. This will not work unless the list
//is currently in ascending order.
IntNode prev = null;
IntNode next = top;
while(next!=null && next.getData()<newItem){
prev = next;
next = next.getLink();
}
//This item belongs between prev and next
IntNode newNode = new IntNode(newItem,next);
if(prev==null)
top = newNode;
else
prev.setLink(newNode);
}
public boolean equals(IntLinkList other){
return equals(top,other.top);
}
}
---------------------------
IntNode :
/**
* One particular node in a linked list of nodes containing int data.
*/
public class IntNode {
private int data; //The data in this Node
private IntNode link; //The link to the next Node
public IntNode(int initData, IntNode initLink){
data = initData;
link = initLink;
}
public int getData() {return data;}
public IntNode getLink() {return link;}
public void setData(int o) {data = o;}
public void setLink(IntNode n) {link = n;}
}
Explanation / Answer
Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts. Thanks
// IntLinkList.java
public class IntLinkList {
private IntNode top; // The reference to the first Node
// =========== Solution code =============================
public IntLinkList(int[] data) {
for (int i = 0; i < data.length; i++) {
add(data[i]);
}
}
public boolean empty() {
if (top == null)
return true;
return false;
}
public int first() {
return top.getData();
}
public void removeFirst() {
if (top != null)
top = top.getLink();
}
public IntLinkList clone() {
IntLinkList a = new IntLinkList();
if (top != null) {
IntNode p = top;
while (p != null) {
a.add(p.getData());
p = p.getLink();
}
}
return a;
}
/**
* recursive method to check if two lists are same
*
* @param top1
* - pointer to the top node of list1
* @param top2
* - pointer to the top node of list2
* @return true if both are equal, else false
*/
private static boolean equals(IntNode top1, IntNode top2) {
if (top1 == null && top2 == null) {
/**
* base case, both nodes became null, it means the method has done
* iterating through all nodes successfully
*/
return true;
}
if (top1 == null || top2 == null) {
/**
* either top1 or top2 is null, meaning that the nodes are not equal
*/
return false;
}
/**
* top1 and top2 are not null
*/
if (top1.getData() == top2.getData()) {
// current nodes are equal, checking the next pair of nodes
return equals(top1.getLink(), top2.getLink());
}
// mismatch found
return false;
}
/**
* method to sort the list recursively
*/
public void InSort() {
// checking for base condition
if (top != null) {
// top is not null, getting the value at front
int value = top.getData();
// removing value at front
removeFirst();
// calling method recursively
InSort();
// adding the removed value in proper position
ordInsert(value);
}
}
// =========== Supplied code =============================
public IntLinkList() {
// A constructor that creates an empty list.
top = null;
}
public void add(int newItem) {
// Add the newItem at the FRONT of the list.
top = new IntNode(newItem, top);
}// add
public String toString() {
String answer = "<<";
IntNode next = top;
while (next != null) {
answer += next.getData() + " ";
next = next.getLink();
}
return answer + ">>";
}
public void ordInsert(int newItem) {
// Add the newItem so that the list remains sorted into
// ascending order. This will not work unless the list
// is currently in ascending order.
IntNode prev = null;
IntNode next = top;
while (next != null && next.getData() < newItem) {
prev = next;
next = next.getLink();
}
// This item belongs between prev and next
IntNode newNode = new IntNode(newItem, next);
if (prev == null)
top = newNode;
else
prev.setLink(newNode);
}
public boolean equals(IntLinkList other) {
return equals(top, other.top);
}
}
// Test.java (tester program)
public class Test {
public static void main(String[] args) {
/**
* creating IntLinkLists and testing the new methods
*/
IntLinkList list1 = new IntLinkList();
list1.add(123);
list1.add(222);
IntLinkList list2 = new IntLinkList();
list2.add(123);
list2.add(222);
System.out.println("List1: " + list1);
System.out.println("List2: " + list2);
System.out.println("List1 == List2: " + list1.equals(list2));
list2.add(456);
list2.add(73);
list2.add(1222);
System.out.println("List2: " + list2);
System.out.println("List1 == List2: " + list1.equals(list2));
list2.InSort();
System.out.println("Sorted List2: " + list2);
}
}
/*OUTPUT*/
List1: <<222 123 >>
List2: <<222 123 >>
List1 == List2: true
List2: <<1222 73 456 222 123 >>
List1 == List2: false
Sorted List2: <<73 123 222 456 1222 >>
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.