JAVA

In this lab, you will create methods to add functionality to a LinkedList. You will be implementing several different methods that require you to traverse (and build) lists. You will be working with a very simplified version of a linked list class that is built from nodes that are public. The nodes have a pointer to the next node and two other fields, a String named key and an int named value. The list is a singly linked list. You should look at the details of the LinkedList class first to get an idea of how to access its functionality.

Objectives

Practice working with a class

Creating and using static methods

Practice with linked lists

Applying test cases to your program

Steps

Start Intellij

At the Welcome Window click Create New Project

In the New Project windowType the name of the project in the Project name: textbox.

Name your project LinkedList

Use the starter codes below. Put these files into the src folder. You will be adding methods to LinkedList.java.

LinkedList.java

public class LinkedList { public class Node{ String key; int value; Node next; public Node(String key, int value) { this.key = key; this.value = value; } } private Node head; private Node tail; public LinkedList() { head = null; tail = null; } public void addHead(String key, int val) { Node n = new Node(key, val); if(head == null) { head = n; tail = n; } else { n.next = head; head = n; } } public void addTail(String key, int val) { Node n = new Node(key, val); if(tail == null) { head = n; tail = n; } else { tail.next = n; tail = n; } } public String toString() { String ret = ""; Node curr = head; while(curr != null) { if(curr.next != null) ret += curr.key + ":" + curr.value + ", "; else ret += curr.key + ":" + curr.value; curr = curr.next; } return ret; } private Node find(String key) { Node curr = head; while(curr != null) { if(curr.key.equals(key)) return curr; curr = curr.next; } return null; } //////////////////////// YOUR CODE HERE //////////////////////// ///////////////////////////////////////////////////////////////

ListApp.java

import java.util.Random; public class ListApp { static LinkedList generateData(int numKeys, int numItems, int seed) { LinkedList l = new LinkedList(); Random rng; if (seed < 0) { rng = new Random(); } else { rng = new Random(seed); } String letters = "abcdefghijkloaeipr"; String[] keys = new String[ numKeys ]; String uniqueKeys = ""; for (int i = 0; i < numKeys; i++) { int letter1 = rng.nextInt(letters.length()); int letter2 = rng.nextInt(letters.length()); keys[ i ] = letters.substring(letter1, letter1 + 1) + letters.substring(letter2, letter2 + 1); uniqueKeys += keys[ i ] + " "; } System.err.println(keys.length + " unique keys: " + uniqueKeys); for (int i = 0; i < numItems; i++) { String key = keys[ rng.nextInt(keys.length)]; int val = rng.nextInt(100); l.addHead(key, val); } return l; } public static void main(String[] args) { LinkedList list; list = ListApp.generateData( 5, 9, 1 ); System.out.println("List: " + list); } }

Now its time to start coding:

Create the following inside LinkedList.java:

A static method called average (returns a double) that takes a LinkedList as a parameter. This method computes the average (mean) of the value field of all entries in the list. You should traverse the list beginning at the head, to sum up the total value of the list's nodes. You should use iteration (a loop) in this method. Do not change the list or any values in it.

Example (result in red)

// assume list contains these keys and values:

// ie:6, bi:48, bi:73, bi:63

LinkedList.average(list);

47.5

A static method called ordered (returns a boolean) that takes a LinkedList as a parameter. This method traverses the list (starting at the head) and checks whether the list is in order according to the key fields of each node. This means that for each node, the node following it should have a key which is greater than or equal. You will need to use the compareTo method from the String class.

Example (result in red)

// assume list contains these keys and values:

// ie:6, bi:48, bi:73, bi:63

LinkedList.ordered(list);

false

Example (result in red)

// assume list contains these keys and values:

// ao:101, bi:29, bi:14, fk:6

LinkedList.ordered(list);

true

A static method called reversed that takes a LinkedList as a parameter and returns a new LinkedList that is reversed. f; traverse through the input list (starting at the head). In order to reverse the ordering, you need to add the current node's key and value onto the head of the new list (addHead method). Do not change the input list or any values in it.

Example (result in red)

// assume list contains these keys and values:

// ie:6, bi:48, bi:73, bi:63

LinkedList.reversed(list);

bi:63, bi:73, bi:48, ie:6

A static method called compressList that takes a LInkedList as a parameter. This method should:

Create a new list from the old one such that all entries in the new list have unique keys. The nodes of the new list should be in the same order as the first occurrence of the ids in the original list.

set the value field of each entry in the new list to the sum of all the value fields that share that key in the original list.

NOTE: The existing find method will be helpful both in checking whether a key is already in the list you're creating and for modifying the value associated with that key if it's already in the new list you will be returning.

Example (result in red)

// assume list contains these keys and values:

// ie:6, bi:48, bi:73, bi:63

LinkedList.compressList(list);

ie:6, bi:184,