create methods to add functionality to a LinkedList. You will be implementing several different methods that require
Question:
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 window
- Type the name of the project in theProject name: textbox.
- Name your projectLinkedList
- Type the name of the project in theProject name: textbox.
- Download the starter code from Mimir. Put these files into the src folder. You will be adding methods to LinkedList.java.
- Now it's time to start coding:
- Create the following inside LinkedList.java:
- A static method calledaverage(returns a double) that takes a LinkedList as a parameter. This method computes the average (mean) of thevalue 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 inred)
// assume list contains these keys and values: // ie:6, bi:48, bi:73, bi:63 LinkedList.average(list); |
47.5
- A static method calledordered (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 thekey 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 thecompareTo method from the String class.
Example (result inred)
// assume list contains these keys and values: // ie:6, bi:48, bi:73, bi:63 LinkedList.ordered(list); |
false
Example (result inred)
// assume list contains these keys and values: // ao:101, bi:29, bi:14, fk:6 LinkedList.ordered(list); |
true
- A static method calledreversed 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 inred)
// 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 calledcompressList 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 existingfind 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 list.
Example (result inred)
// assume list contains these keys and values: // ie:6, bi:48, bi:73, bi:63 LinkedList.compressList(list); |
ie:6, bi:184,
Given classes
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 //////////////////////// /////////////////////////////////////////////////////////////// }
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); } }
International Marketing And Export Management
ISBN: 9781292016924
8th Edition
Authors: Gerald Albaum , Alexander Josiassen , Edwin Duerr