Lab 02, Data Abstractions and Structures, CSE 274, Fall 2019
Linked Bag
In this lab, we will implement the Linked Bag. The bag will contain
a sequence of strings. First, you need to design the Node class
(Node.java). It will contain an integer data and a reference to the
next Node. The constructor of Node class receives an integer and
assigns it to the data field. It also has a default
constructor.
Then we will design another class named LinkedBag (LinkedBag.java).
LinkedBag class has an instance variable called firstNode of type
Node. It has the following methods:
1. public LinkedBag() The default constructor of class
LinkedBag.
2. public int getCurrentSize() Gets the current number of entries
in this bag.
3. public T[] toArray() Retrieves all entries that are in this
bag.
4. public boolean addToHead(T newEntry) Adds the specified new
entry to the start of the linked bag.
5. public boolean addToTail(T newEntry) Adds the specified new
entry to the end of the linked bag.
6. public T removeHead() Removes and returns the first item from
the bag. If the bag has no nodes, returns null.
7. public T removeTail() Removes and returns the last item from the
bag.
Implement all the methods in LinkedBag class.
Grading Rubric: Each method is worth 10 points. Total 100
points.
LinkedBag() 5 getCurrentSize() 5 toArray() 20 addToHead(T newEntry)
10 addToTailHead(T newEntry) 20 removeHead() 10 removeTail()
30
Data Next Node
Before getting started: ● Create a new project named Lab2LinkedBag
● Now download the LinkedBagTester class and addi t t o your
project. Run a nd test your code. You will have the following
output:
======================================== Adding A to the Head of
the bag: The bag contains 1 string(s), as follows: A
======================================== Adding B to the Head of
the bag: The bag contains 2 string(s), as follows: B A
======================================== Adding C to the Tail of
the bag: The bag contains 3 string(s), as follows: B A C
======================================== Adding D to the Tail of
the bag: The bag contains 4 string(s), as follows: B A C D
======================================== Removing an entry from the
head: The bag contains 3 string(s), as follows: A C D
======================================== Removing an entry from the
Tail: The bag contains 2 string(s), as follows: A C
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
/**
A class of bags whose entries are stored in a chain of linked
nodes.
The bag is never full.
*/
public class LinkedBag<T> implements
BagInterface<T>
{
private Node firstNode; // Reference to first
node
private int numberOfEntries;
public LinkedBag()
{
firstNode =null;
numberOfEntries =0;
} // end default constructor
/** Adds a new entry to the head of this bag.
@param newEntry The object to be
added as a new entry.
@return True, as adding a new entry
should always be successful. */
public boolean addToHead(T newEntry) //
OutOfMemoryError possible
{
} // end addToHead
/** Adds a new entry to the tail of this bag.
@param newEntry The object to be added as a new entry.
@return True, as adding a new entry should always be successful.
*/
public boolean addToTail(T newEntry) // OutOfMemoryError
possible
{
} // end addToTail
/** Removes the first entry from this bag, if possible.
@return Either the removed entry, if the removal
was successful, or null if not. */
public T removeHead()
{
} // end removeHead
/** Removes the last entry from this bag, if possible.
@return Either the removed entry, if the removal
was successful, or null if not. */
public T removeTail()
{
} // end removeHead
/** Retrieves all entries that are in this bag.
@return A newly allocated array of
all the entries in the bag. */
public T[] toArray()
{
@SuppressWarnings("unchecked")
T[] result = (T[])new
Object[numberOfEntries];
// Unchecked cast
int index = 0;
Node currentNode = firstNode;
while((index < numberOfEntries) &&
(currentNode != null))
{
}
;
} // end toArray
/** Gets the number of entries currently in this
bag.
@return The integer number of
entries currently in the bag. */
public int getCurrentSize()
{
return numberOfEntries;
} // end getCurrentSize
// A class of nodes for a chain of linked nodes.
private class Node
{
private T data;
// Entry in bag
private Node next;
// Link to next node
private Node(T dataPortion)
{
this(dataPortion, null);
}
// end constructor
private Node(T dataPortion, Node
nextNode)
{
data = dataPortion;
next = nextNode;
} // end Node
} // end LinkedBag
}
// LinkedBag.java
public class LinkedBag<T> implements BagInterface<T>{
private Node firstNode; // Reference to first node
private int numberOfEntries;
public LinkedBag()
{
firstNode =null;
numberOfEntries =0;
} // end default constructor
/** Adds a new entry to the head of this bag.
@param newEntry The object to be added as a new entry.
@return True, as adding a new entry should always be successful. */
public boolean addToHead(T newEntry) // OutOfMemoryError possible
{
Node node = new Node(newEntry);
// check if bag is empty
if(firstNode == null)
firstNode = node; // set node as firstnode
else // non-empty bag
{
// make the new node first node
node.next = firstNode;
firstNode = node;
}
numberOfEntries++; // increment the number of entries
return true;
} // end addToHead
/** Adds a new entry to the tail of this bag.
@param newEntry The object to be added as a new entry.
@return True, as adding a new entry should always be successful. */
public boolean addToTail(T newEntry) // OutOfMemoryError possible
{
Node node = new Node(newEntry);
if(firstNode == null) // if empty bag
firstNode = node; // set node as firstnode
else // if non-empty bag
{
Node temp = firstNode;
// get the last node
while(temp.next != null)
temp = temp.next;
temp.next = node; // make last node point to the new node
}
numberOfEntries++; // increment the number of entries
return true;
} // end addToTail
/** Removes the first entry from this bag, if possible.
@return Either the removed entry, if the removal
was successful, or null if not. */
public T removeHead()
{
if(firstNode == null) // empty bag
return null;
else
{
T item = firstNode.data; // get the data of firstnode
firstNode = firstNode.next; // remove the firstnode
numberOfEntries--; // decrement the number of entries
return item; // return the item at firstnode
}
} // end removeHead
/** Removes the last entry from this bag, if possible.
@return Either the removed entry, if the removal
was successful, or null if not. */
public T removeTail()
{
if(firstNode == null) // empty bag
return null;
else
{
Node temp = firstNode;
Node prev = null;
// loop to get the last node
while(temp.next != null)
{
prev = temp;
temp = temp.next;
}
T item = temp.data; // get the item at last node
if(prev == null) // check if bag contains only one node
{
firstNode = null; // make the bag empty
}else
prev.next = null; // remove the last node
numberOfEntries--; // decrement the number of entries
return item; //return the last item
}
} // end removeHead
/** Retrieves all entries that are in this bag.
@return A newly allocated array of all the entries in the bag. */
public T[] toArray()
{
@SuppressWarnings("unchecked")
T[] result = (T[])new Object[numberOfEntries];
// Unchecked cast
int index = 0;
Node currentNode = firstNode;
// loop to insert the items of the bag in the array
while((index < numberOfEntries) && (currentNode != null))
{
result[index] = currentNode.data;
index++;
currentNode = currentNode.next;
}
return result;
} // end toArray
/** Gets the number of entries currently in this bag.
@return The integer number of entries currently in the bag. */
public int getCurrentSize()
{
return numberOfEntries;
} // end getCurrentSize
// A class of nodes for a chain of linked nodes.
private class Node
{
private T data;
// Entry in bag
private Node next;
// Link to next node
private Node(T dataPortion)
{
this(dataPortion, null);
}
// end constructor
private Node(T dataPortion, Node nextNode)
{
data = dataPortion;
next = nextNode;
}
} // end Node
}//end LinkedBag
//end of LinkedBag.java
Get Answers For Free
Most questions answered within 1 hours.