I need help with this java program, it is already been done need few changes to
ID: 3856650 • Letter: I
Question
I need help with this java program, it is already been done need few changes to it. i am providing the program needed for this.
Question needs to be solved:
Write code to remove duplicates from an unsorted linked list. You can reorder list. Order does not important.
You can implement bubble sort first.
Then
sort list using bubble sort and
remove duplicates from sorted linked list.
Programs Needed
----------------------------
Driver.java
//import ch06.lists.*;
//import support.*;
public class Driver
{
public static void main(String[] args)
{ //page 469 #51
System.out.println("page 469 #51 testing removeAll() ");
RefUnsortedList<String> myList;
myList = new RefUnsortedList<String>();
myList.add("3");
myList.add("4");
myList.add("3");
myList.add("5");
myList.add("3");
myList.add("6");
myList.add("3");
myList.add("3");
myList.add("7");
System.out.println("myList: "+myList);
myList.removeAll1("3");
System.out.println("myList: "+myList);
}
}
-------------------------------------------------------------------------------------------------------------------------------------------
LLNode.java
class LLNode<T>
{
private T info;
private LLNode<T> next;
public void setLink(LLNode<T> node)
{
next = node;
}
public LLNode<T> getLink()
{
return next;
}
public LLNode(T inf)
{
info = inf;
}
public T getInfo()
{
return info;
}
}
class RefUnsortedList<T>
{
protected int numElements;
protected LLNode<T> currentPos;
protected boolean found;
protected LLNode<T> location;
protected LLNode<T> previous;
protected LLNode<T> list;
public RefUnsortedList()
{
numElements = 0;
list = null;
currentPos = null;
}
public void add(T element)
{
LLNode<T> newNode = new LLNode<T>(element);
newNode.setLink(list);
list = newNode;
numElements++;
}
protected void find(T target)
{
location = list;
found = false;
while (location != null)
{
if (location.getInfo().equals(target))
{
found = true;
return;
}
else
{
previous = location;
location = location.getLink();
}
}
}
public int removeAll1(T target)
{
location = list;
found = false;
int cnt=0;
while (location.getLink() != null)
{
if (location.getLink().getInfo().equals(target))
{
location.setLink(location.getLink().getLink());
cnt++;
}
else
{
location = location.getLink();
}
}
if(list.getInfo().equals(target))
{
list = list.getLink();
cnt++;
}
return cnt;
}
public int size()
{
return numElements;
}
public boolean contains (T element)
{
find(element);
return found;
}
public boolean remove (T element)
{
find(element);
if (found)
{
if (list == location)
list = list.getLink();
else
previous.setLink(location.getLink());
numElements--;
}
return found;
}
public int removeAll(T ele)
{
int count =0;
while(remove(ele))
count++;
return count;
}
public T get(T element)
{
find(element);
if (found)
return location.getInfo();
else
return null;
}
public String toString()
{
LLNode<T> currNode = list;
String listString =" List:";
while (currNode != null)
{
listString = listString + " " + currNode.getInfo() + " ";
currNode = currNode.getLink();
}
return listString;
}
public void reset()
{
currentPos = list;
}
public T getNext()
{
T next = currentPos.getInfo();
if (currentPos.getLink() == null)
currentPos = list;
else
currentPos = currentPos.getLink();
return next;
}
}
Explanation / Answer
The answer is as follows:
The code is as follows:
//For the implementation of bubble sort it is good to have a setInfo(T item) method in the class LLNode<T>. The method is as follows:
public void setInfo(T item){
info = item;
}
public void bubblesort(){
LLNode<T> last;
LLNode<T> current;
T temp;
current = list;
while (current->next != null){ // for setting last to the last node in the list
current = current.next;
}
last = current;
while (last != list){ // last points to the start of sorted part of the linked list.Currently last is pointing to the last node
current = list;
while (current.next != last){ // this loop is for the iterations.Every iteration, last will be moving
// towards list (i.e start of the list)
if (current.getInfo() > current.next.getInfo()){
temp = current.getInfo();
current.setInfo(current.next.getInfo());
current.next.setInfo(temp);
}
current = current.next;
}
if (current.getInfo() > current.next.getInfo()){ // This is required for the comparison of last two nodes
temp = current.getInfo();
current.setInfo(current.next.getInfo());
current.next.setInfo(temp);
}
last = current;
}
}
For removing the duplicates the function is as follows:
public void removeDuplicates(){
LLNode<T> temp, current;
current = list;
while (current.next != null){ // will reach the last node
if (current.getInfo() == current.next.getInfo()){
temp = current.next;
while (temp != null){ // temp is traversing the node till we get a diferent value from the current node
if (temp.getInfo() == current.getInfo())
temp = temp.next()
else
break;
}
current.next = temp;
}
current = current.next;
if (current == null) // This case can happen if last two nodes have duplicate values
break;
}
}