Objectives

This assignment will help you to:

Understand how linked list data structure works

Write java programs implementing single linked list and using single linked list

Description

Modify the given class SimpleLinkedList2 (GIVEN BELOW) in the following ways.

Add the following methods:

public int getHowMany()

Find currently how many integers are in the current linked list and return the count.

public boolean belongs(int item)

Find out if the integer item is in the current linked list. Returns true if yes, false otherwise.

public int get(int index)

Get the integer at the specified position: index and return the integer value. If the index is not valid, print an error message.

public boolean add(int index, int item)

Try to insert the specified integer: item at the specified position: index in the current linked list. If there is an integer currently at that position, do not replace it and this is the case of failure to insert. If the specified position is greater than the current size of the linked list, display an error message and do not insert the item. Returns true if the insertion is successful, false otherwise.

public void copy(SimpleLinkedList2 list2)

Make the current linked list an EXACT COPY of the specified list list2. Discard all existing integers in the current linked list.

Note: after the copy method, the current linked list must be an EXACT COPY of the specified list, NOT the SAME single list. So the implementation is not just a simple assignment operation.

public boolean equals(Object list2)

Check if the list of integers stored in the current linked list equals to the list of integers stored in the specified list list2. Returns true if yes, false otherwise. Note: this overrides whats in the class Object.

(Bonus) public boolean removeByValue(int item)

Remove the specified integer item from the current linked list. If success, return true.

Otherwise, return false. Assume that there are no duplicate values in the list.

(Bonus) public boolean removeyByIndex(int index)

Remove the integer at the specified position index from the current linked list. Return true if success, false otherwise. If the index is not valid, print an error message.

(Bonus if you complete add method at 4^th bullet) public boolean add2(int index, int item)

Try to insert the specified integer: item at the specified position: index in the current linked list. If there is an integer, say intA, currently at that position, do not replace it. Instead insert the new item before intA, which effectively increases the indices of intA and subsequent integers by 1. If the specified position is greater than the current size of the linked list, display an error message and do not insert the item. Returns true if the insertion is successful, false otherwise.

Note: do NOT add or remove data fields to SimpleLinkedList2 class. Do not change the definition of Node class.

Modify the given class SimpleLinkedList2Test in the following ways.

Create 3 empty linked list of integers using class SimpleLinkedList2, named positiveList, negativeList, integerList.

Ask user to enter a list of integers. For each integer entered, if the integer is positive, insert it into positiveList and integerList. IF the integer is negative, insert it into negativeList and integerList. If the integer is 0, do not insert into any list.

Display the contents in all three lists

Check if positiveList and negativeList are equal and display the result

Create a 4^th empty linked list of integers using class SimpleLinkedList2, named newList.

Copy integerList to newList.

Display the contents in newList.

/*

* File SimpleLinkedList2.java

*/

/**

* The class SimpleLinkedList2 is the simplest linked list structure.

* An object of this class is a single linked list of integers.

* @author N/A

*/

public class SimpleLinkedList2 {

/** the head pointer to point to the first node in the list */

private Node head;

/**constructor to create an empty list */

public SimpleLinkedList2() {

head = null;

}

/**insert the new integer value stored in newItem to the end of the list */

public void add(int newItem) {

//create a new node for the integer value in newItem

Node newNode = new Node(newItem);

//the link to current node in the list

Node current;

//search for the last node in the list

if (head == null) { //if the list is empty

head = newNode;

}

else {

//search for the last node in the list

current = head;

while (current.next != null) {

current = current.next;

}

//make the new node as the last in the list

current.next = newNode;

}

}

/**Insert the new integer value stored in variable newItem to the list.

* The new value will be the immediate following neighbor after the node referenced by here.

*/

private void add(int newItem, Node here) {

Node temp = new Node(newItem);

temp.next = here.next;

here.next = temp;

}

@Override

public String toString() {

String result = "";

Node current = head;

while (current != null) {

result += current.dataItem + "==>";

current = current.next;

}

return result;

}

/**

* Static nested class representing a data node in the linked list

* The class is placed inside the class SimpleLinkedList2

* The class cannot directly access instance methods like toString(...), add(...) in the

* enclosing class SimpleLinkedList.

*

* @author Cindy

*/

private static class Node {

/**The data item (an integers) stored in the node */

private int dataItem;

/**the link to the immediate following neighbor */

private Node next;

/**Create a node for the item (an integer) */

public Node(int item) {

dataItem = item;

next = null;

}

}

}

/*

* File SimpleLinkedList2Test.java

*/

/**

* The class SimpleLinkedList2Test is the driver of class SimpleLinkedList.

* It tests the implementation of class SimpleLinkedList2.

* @author N/A

*/

public class SimpleLinkedList2Test {

/**

* @param args the command line arguments

*/

public static void main(String[] args) {

//create an empty list

SimpleLinkedList2 myList = new SimpleLinkedList2();

//add three integers 10, 20, 30 to the list

myList.add(10);

myList.add(20);

myList.add(30);

//print the integer values in the list

System.out.println(myList.toString());

}

}