list

Class IntList

java.lang.Object

list.IntList

public class IntList
extends java.lang.Object

Lab04
In this lab you will practice implementing classes, using APIs, and handling memory references.

You will implement a linked list for storing primitive int values. This class uses the IntListEntry class, which has been written for you. Part of the IntList class has also been written for you.

The first step of this lab is to read the API documentation for the IntListEntry class, as well as the API documentation for methods IntList(), getLength(), get(), prepend(), and toString() in the IntList class. This documentation is available in the doc folder of the project directory, or through the class schedule web-page.

The next step is to look at the main() method of ScratchPad.java to see typical usage of IntList objects, in particular the five methods listed in the previous paragraph. Complete the task described in the last comment of ScratchPad.java.

Now you are ready to implement the remaining methods of IntList. Follow the directions in the comments below (starting at Part 1), which are also included in the API documentation.

Author:

Your Name Here

Constructor Summary

Constructors

Constructor and Description
IntList() Initializes an empty list. The size is zero, and the first entry is null.

Method Summary

Methods

Modifier and Type	Method and Description
void	append(int data) Append a new entry at the back of this list. This method is like a combination of get() and prepend(). Similarly to get(), you can loop a "current" variable until it contains the address of the final list entry.
void	bump(int index) Increments the data at a particular entry in this list You can implement this method with a call to get() followed by a call to set().
static IntList	dupList(int size, int data) Like zeros and ones, but the caller chooses the initial value. For example, dupList(5, 2) should return the list [2, 2, 2, 2, 2]
boolean	equals(IntList other) Returns true if this list is identical to some other list. The lists must be non-null, the same size, and contain identical values at each index.
int	findIndex(int data) Finds the index of the first entry containing the specified value. If the value does not exist in the list, return the size of the list. This should be similar to get() - you can use a reference variable to store the address of the current list entry, and then loop through the list by calling current.getNext().
int	get(int index) Gets the data at a particular entry in this list. For example, if myList is [1, 2, 5, 3] then myList.get(0) returns 1, and myList.get(2) returns 5.
int	getLength() Gets the length of this list. For example, if myList is [1, 2, 5, 3] then myList.getLength() is 4.
static void	histogram(int numSides, int numRolls) Generate a histogram for many rolls of a many-sided die. For example, roll a 100-sided die 10,000,000 times.
void	insert(int index, int data) Insert a new entry anywhere in the list. For example, with input parameters index = 3, data = 7, the list [1, 4, 2, 6, 10] should change to [1, 4, 2, 7, 6, 10]
static IntList	ones(int size) Create a new list with each entry initialized to one.
void	plot() "Plots" the list in the console, using the '?' character. The number of '*'s in each row is given by the corresponding entry. For example, the list [2, 7, 1, 5] should result in the following console output: ## ####### # ##### where '#' would be replaced by the solid block character ('?'). (Ignore the "br" tags, these are just for formatting the documentation)
IntList	plus(IntList other) Compute the entry-wise sum of the current list with another list. For example, adding the lists [0, 1, 2, 3] [1, 5, 5, 3] Should return the list [1, 6, 7, 6] You can do this with a call to the constructor, followed by a loop with calls to get() and prepend().
IntList	prepend(int data) Inserts a new entry at the front of this list. For example, if myList is [1, 2, 5, 3] after calling myList.prepend(10), myList will have changed to [10, 1, 2, 5, 3]
int	prod() Compute the product of the values stored in the list
static IntList	range(int start, int stop) Create a new list with each entries in the specified range For example, input parameters start = 3, stop = 7 should return [3, 4, 5, 6, 7]
static int	rollBiasedDie(int numSides) Perform one "roll" of a biased many-sided die.
static int	rollFairDie(int numSides) Perform one "roll" of a fair many-sided die.
void	set(int index, int newData) Sets the data at a particular entry in this list. For example, if myList is [1, 2, 6, 3, 4] then after calling myList.set(3, 9) it will be changed to [1, 2, 6, 9, 4]
int	sum() Computes the sum of the values stored in the list Use a loop, getLength(), and get()
java.lang.String	toString() Returns a String representation of this list. For example, "[1, 2, 6, 3]"
static IntList	zeros(int size) Create a new list with each entry initialized to zero.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

IntList

public IntList()

Initializes an empty list.
The size is zero, and the first entry is null.

Method Detail

getLength

public int getLength()

Gets the length of this list.
For example, if myList is
[1, 2, 5, 3]
then myList.getLength() is 4.

Returns:

the current number of entries

prepend

public IntList prepend(int data)

Inserts a new entry at the front of this list.
For example, if myList is
[1, 2, 5, 3]
after calling myList.prepend(10), myList will have changed to
[10, 1, 2, 5, 3]

Parameters:

data - the int value to be stored in the new entry

Returns:

A reference to this list with the value prepended

get

public int get(int index)

Gets the data at a particular entry in this list.
For example, if myList is
[1, 2, 5, 3]
then myList.get(0) returns 1, and myList.get(2) returns 5.

Parameters:

index - the position in this list containing the data

Returns:

the int value stored at the given index

toString

public java.lang.String toString()

Returns a String representation of this list.
For example,
"[1, 2, 6, 3]"

Overrides:

toString in class java.lang.Object

Returns:

The String representation

sum

public int sum()

Computes the sum of the values stored in the list
Use a loop, getLength(), and get()

Returns:

the sum of the values stored in the list

prod

public int prod()

Compute the product of the values stored in the list

Returns:

the product of the values stored in the list

plot

public void plot()

"Plots" the list in the console, using the '?' character.
The number of '*'s in each row is given by the corresponding entry.
For example, the list
[2, 7, 1, 5]
should result in the following console output:
##
#######
#
#####
where '#' would be replaced by the solid block character ('?').
(Ignore the "br" tags, these are just for formatting the documentation)

equals

public boolean equals(IntList other)

Returns true if this list is identical to some other list.
The lists must be non-null, the same size, and contain
identical values at each index.

Parameters:

other - The other IntList to compare with

Returns:

true if the two lists are identical, false otherwise.

zeros

public static IntList zeros(int size)

Create a new list with each entry initialized to zero.

Parameters:

size - the size of the new list

Returns:

a new list with the given size containing all zeros.

ones

public static IntList ones(int size)

Create a new list with each entry initialized to one.

Parameters:

size - the size of the new list

Returns:

a new list with the given size containing all ones.

dupList

public static IntList dupList(int size,
              int data)

Like zeros and ones, but the caller chooses the initial value.
For example, dupList(5, 2) should return the list
[2, 2, 2, 2, 2]

Parameters:

size - the size of the new list

data - the constant value to be used at every entry

Returns:

a new list with the given size and value at every entry

range

public static IntList range(int start,
            int stop)

Create a new list with each entries in the specified range
For example, input parameters start = 3, stop = 7 should return
[3, 4, 5, 6, 7]

Parameters:

start - the first entry in the list

stop - the last entry in the list

Returns:

a new list containing the specified range

set

public void set(int index,
       int newData)

Sets the data at a particular entry in this list.
For example, if myList is
[1, 2, 6, 3, 4]
then after calling myList.set(3, 9) it will be changed to
[1, 2, 6, 9, 4]

Parameters:

index - the position in this list to overwrite

newData - the new value to be stored

bump

public void bump(int index)

Increments the data at a particular entry in this list
You can implement this method with a call to get() followed by a call to set().

Parameters:

index - the position in this list to increment

plus

public IntList plus(IntList other)

Compute the entry-wise sum of the current list with another list.
For example, adding the lists
[0, 1, 2, 3]
[1, 5, 5, 3]
Should return the list
[1, 6, 7, 6]
You can do this with a call to the constructor, followed by a loop with calls to get() and prepend().

Parameters:

other - the other list to be added to the current one

Returns:

A new list containing the entry-wise sums

findIndex

public int findIndex(int data)

Finds the index of the first entry containing the specified value.
If the value does not exist in the list, return the size of the list.
This should be similar to get() - you can use a reference variable to store the address of the current list entry, and then loop through the list by calling current.getNext(). However this time you want to loop until you find the value you're looking for, or you've checked the entire list.

Parameters:

data - the value to search for

Returns:

the index of the first entry containing the value

append

public void append(int data)

Append a new entry at the back of this list.
This method is like a combination of get() and prepend().
Similarly to get(), you can loop a "current" variable until it contains the address of the final list entry. At that point, you can construct a new IntListEntry, as done in prepend(). Then use current's setNext() method to assign the new IntListEntry to the end of the list.

Parameters:

data - the int value to be stored in the new entry

insert

public void insert(int index,
          int data)

Insert a new entry anywhere in the list.
For example, with input parameters index = 3, data = 7, the list
[1, 4, 2, 6, 10]
should change to
[1, 4, 2, 7, 6, 10]

Parameters:

index - the position at which to insert the new entry

data - the value to insert

rollFairDie

public static int rollFairDie(int numSides)

Perform one "roll" of a fair many-sided die. This is implemented for you.

Parameters:

numSides - the number of "sides" on the "die" being rolled

Returns:

a random integer in the range [0, numSides-1].

rollBiasedDie

public static int rollBiasedDie(int numSides)

Perform one "roll" of a biased many-sided die. This is implemented for you. Similarly to lab02, the biases are given by 1: with probability 0.5 2: with probability 0.25 3: with probability 0.125 4: with probability 0.0625 ... N: with probability 1.0/Math.pow(2, N)

Parameters:

numSides - the number of "sides" on the "die" being rolled

Returns:

a random integer in the range [0, numSides-1].

histogram

public static void histogram(int numSides,
             int numRolls)

Generate a histogram for many rolls of a many-sided die.
For example, roll a 100-sided die 10,000,000 times. Count the number of 1's, 2's, 3's, ..., 99's, and 100's. You can maintain these counts in an IntList with 100 entries.
The counts should be printed to the console using plot().