Can someone help me create a public sort method or (sorting algorithm) which wil
ID: 3691551 • Letter: C
Question
Can someone help me create a public sort method or (sorting algorithm) which will sort the linked list of strings in alphabet or in lexicographical order?
-------------------------------------------------------------------------------------------------------
package binarysearch;
class SearchableLinkedList> extends LinkedList {
SearchableLinkedList() {
super();
}
/*
* Searching for a certain String elements in linkedlist Precondition: There
* is elements in linkedlist. Postcondition: The certain element in
* linkedlist had been found.
*
* @return mid: the index of the certain element being search
*
* @param list, key, start, end
*/
public int binarySearch(LinkedList list, int start, int end, String key) {
if (list.size() == 1) {
return 1;
}
int mid = (start + end) / 2;
if (list.get(mid).compareTo(key) > 0) {
return binarySearch(list, start, mid - 1, key);
} else if (list.get(mid).compareTo(key) < 0) {
return binarySearch(list, mid + 1, end, key);
} else
return mid;
}
}
package binarysearch;
public class LinkedList {
private Node head;
private int listCount;
public LinkedList() {
head = new Node(null);
listCount = 0;
}
public void getHead() {
head = new Node(null);
}
/*
* Appends the specified element to the end of this list. Precondition: The
* element had been created. Postcondition: The elements had been added into
* linkedlist.
*
* @param data: The elements being added.
*/
public void add(String data)
{
Node temp = new Node(data);
Node current = head;
while (current.getNext() != null) {
current = current.getNext();
}
current.setNext(temp);
listCount++;
}
/*
* Inserts the specified element at the specified position in this list.
* Precondition: The elements had been created. Postcondition: The elements
* had been added at the certain index of linkedlist.
*
* @param data: The elements being adding in linkedlist.
*
* @param index: The index in the linkedlist
*/
public void add(String data, int index)
{
Node temp = new Node(data);
Node current = head;
for (int i = 1; i < index && current.getNext() != null; i++) {
current = current.getNext();
}
temp.setNext(current.getNext());
current.setNext(temp);
listCount++;
}
/*
* Returns the element at the specified position in this list. Precondition:
* There is elements in the list. Postcondition: The elements had been found
* in list.
*
* @param index: The index of the element being look.
*
* @return The value of the elements being look for.
*/
public String get(int index)
{
if (index <= 0)
return null;
Node current = head.getNext();
for (int i = 1; i < index; i++) {
if (current.getNext() == null)
return null;
current = current.getNext();
}
return current.getData();
}
/*
* Removes the element at the specified position in this list.
*/
public boolean remove(int index)
{
if (index < 1 || index > size())
return false;
Node current = head;
for (int i = 1; i < index; i++) {
if (current.getNext() == null)
return false;
current = current.getNext();
}
current.setNext(current.getNext().getNext());
listCount--;
return true;
}
/*
* Returns the number of elements in this list. Precondition: There is
* elements in list. Postcondition: The size of the list had been
* determined.
*
* @return the number of elements in this list.
*/
public int size()
{
return listCount;
}
/*
* Going through the list. Precondition: There is elements in the list.
* Postcondition: The list had been transerved.
*
* @return output: The elements in the list.
*
*/
public String toString() {
Node current = head.getNext();
String output = "";
while (current != null) {
output += " " + current.getData().toString() + " ";
current = current.getNext();
}
return output;
}
/*
* Setting up the Node
*/
private class Node {
Node next;
String data;
public Node(String _data) {
next = null;
data = _data;
}
public Node(String _data, Node _next) {
next = _next;
data = _data;
}
public String getData() {
return data;
}
public void setData(String _data) {
data = _data;
}
public Node getNext() {
return next;
}
public void setNext(Node _next) {
next = _next;
}
}
}
package binarysearch;
public class MainDriver {
/*
* Executing the Linkedlist and SearchableLinkedList class.
*/
public static void main(String[] args) {
LinkedList list = new LinkedList();
SearchableLinkedList s = new SearchableLinkedList();
list.add("Bob");
list.add("Chris");
list.add("Evan");
list.add("David");
list.add("Zack");
list.add("Done");
list.add("Nine");
System.out.println(list.toString());
System.out.println("Size of the list element is: " + list.size());
System.out.println("Found Zack at: " + s.binarySearch(list, 1, 7, "Zack"));
}
}
Explanation / Answer
import java.util.ArrayList; import java.util.Collections; class SearchableLinkedList extends LinkedList { SearchableLinkedList() { super(); } /* * Searching for a certain String elements in linkedlist Precondition: There * is elements in linkedlist. Postcondition: The certain element in * linkedlist had been found. * * @return mid: the index of the certain element being search * * @param list, key, start, end */ public int binarySearch(LinkedList list, int start, int end, String key) { if (list.size() == 1) { return 1; } int mid = (start + end) / 2; if (list.get(mid).compareTo(key) > 0) { return binarySearch(list, start, mid - 1, key); } else if (list.get(mid).compareTo(key) < 0) { return binarySearch(list, mid + 1, end, key); } else return mid; } } class LinkedList { private Node head; private int listCount; public LinkedList() { head = new Node(null); listCount = 0; } public void getHead() { head = new Node(null); } public void sort(){ ArrayList strings = new ArrayList(); Node current = head.getNext(); while (current != null) { strings.add(current.data); current = current.getNext(); } Collections.sort(strings); System.out.println("Sorted list:"); for(String s : strings){ System.out.print(s + " "); } } /* * Appends the specified element to the end of this list. Precondition: The * element had been created. Postcondition: The elements had been added into * linkedlist. * * @param data: The elements being added. */ public void add(String data) { Node temp = new Node(data); Node current = head; while (current.getNext() != null) { current = current.getNext(); } current.setNext(temp); listCount++; } /* * Inserts the specified element at the specified position in this list. * Precondition: The elements had been created. Postcondition: The elements * had been added at the certain index of linkedlist. * * @param data: The elements being adding in linkedlist. * * @param index: The index in the linkedlist */ public void add(String data, int index) { Node temp = new Node(data); Node current = head; for (int i = 1; iRelated Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.