While using java.util.LinkedList is fine for many applications, developing our own linked list data structure is excellent practice for understanding dynamic data structures. Our goal for this assignment is to create our own functional Linked List class that we can use in our applications

Requirements:

1) You must follow the code we provided at step 4

2) You are not allowed to use Iterators

3) Your list cannot be doubly linked.

-------------------------

Assignment Steps:

Step 1: Create a new Java project named LinkedListProject

---------

Step 2: Create a new Java class in your project named LinkedStringList

---------

Step 3:

Add an inner Node class as demonstrated in step 4

---------

Step 4:

You are given code for the following methods in LinkedListStarterCode.java. You should include these in your project:

LinkedStringList() (an empty constructor)

addFirst() (adds an element in the first position)

setFirstValue() (sets the value of the element in the first position)

setCurrentValue() (sets the value of the element in the current position)

moveNext() (moves the current reference to the next element)

moveFirst() (moves the current reference to the first position)

isEmpty() (returns whether the list is empty)

getLength() (returns the length of the list)

displayList() (displays all elements in the list)

//

// LinkedListStarterCode.java

import java.util.NoSuchElementException;

public class LinkedStringList {

private Node first;

private Node currentNode;

private int length;

class Node

{

private String data;

private Node next;

public void printNodeData()

{

System.out.println("Node data: " + data);

}

public Node getNext()

{

return next;

}

}

public LinkedStringList()

{

first = null;

currentNode = null;

length = 0;

}

public void addFirst(String value)

{

//create the Node and set its value

Node newNode = new Node();

newNode.data = value;

// if newNode is the first node, this will be null

// otherwise it will point to the former "first" now

newNode.next = first;

//set our "first" Node to the Node we just created

first = newNode;

currentNode = newNode;

length++;

}

public void setFirstValue(String value)

{

first.data = value;

}

public void setCurrentValue(String value)

{

currentNode.data = value;

}

public void moveNext()

{

if (currentNode.next == null)

{

throw new NoSuchElementException();

}

else

{

currentNode = currentNode.next;

}

}

public void moveFirst()

{

currentNode = first;

}

public boolean isEmpty()

{

return (first == null);

}

public int getLength()

{

return length;

}

public String getFirstValue()

{

if (first == null)

{

throw new NoSuchElementException();

}

else

{

return first.data;

}

}

public String getCurrentValue()

{

if (currentNode == null)

{

throw new NoSuchElementException();

}

else

{

return currentNode.data;

}

}

public void displayList()

{

Node currentNode = first;

System.out.println("List contents:");

while (currentNode != null)

{

currentNode.printNodeData();

currentNode = currentNode.getNext();

}

}

}

Step 5:

Add the following methods on your own:

add(String value) - add an element in the current position

getCurrentValue() - returns the value of the current element

removeFirst() - remove the first element

remove() - remove the current element

indexOf(String value) - return the position of value, or -1 if not found

sortAscending() - sort your linked list in ascending order using a Selection Sort as shown in SelectSortStarterCode.java.

// SelectSortStarterCode.java

import java.util.Arrays;

public class SelectSortStarterCode {

public static void swap(int [] arr, int a, int b)

{

int tempSwap = arr[a];

arr[a] = arr[b];

arr[b] = tempSwap;

}

public static int getMin(int [] arr, int startPos)

{

int min = arr[startPos];

int minPos = startPos;

for (int i= startPos+1 ; i < arr.length; i++)

{

if (arr[i] < min)

{

min = arr[i];

minPos = i;

}

}

return minPos;

}

public static void performSelectionSort(int [] arr)

{

for (int i = 0; i < arr.length - 1; i++)

{

int min = getMin(arr, i);

if (arr[min] < arr[i])

{

swap(arr, min, i);

}

}

}

public static void main(String[] args) {

int [] arr = { 32, 10, 5, 132, 54, 2, 43, 56, 76, 23, 5, 6, 90, 22 };

performSelectionSort(arr);

System.out.println(Arrays.toString(arr));

---------

Step 6:

In your main method:

Create an instance of your LinkedStringList class named list.

Call your add() method 3 times to add the values First, Second, and Third to list.

Use moveFirst(), moveNext(), and setCurrentValue() to replace those values with Red, Green, and Blue (respectively).

Use your indexOf() method to display the position of the Green string.

Use displayList() to display the contents of list.

Use your sortAscending() method to sort the list in ascending order.

Use displayList() to display the contents of mySortedList.

Call your remove() method twice on mySortedList.Use displayList() to display the contents of mySortedList (again).