trypots.nethomeA Bag data structure
This is an implementation of a Bag ADT using a singly linked list. A Bag is simply a collection of elements without any implicit order, with a few simple methods such as add(), remove(), isFull(), and isEmpty(). This bag has only an add() method. I have saved this code mainly as an example of implementing a singly linked list with an inner class Node. With this approach, you can allow your users to create structures with any data type, keeping the Node implementation within the linked list hidden (encapsulated). Also we see here how to implement an Iterator for the structure. This code is from the book Algorithms by Robert Sedgewick and Kevin Wayne (Fourth edition, page 155). It also illustrates using a linked list by simply creating a node and letting it thereby serve as the first node of the list.
Notice how in the test run we can create a bag of Thing objects, as well as a Bag of String objects. This shows how in the Bag class the use of <Item> as a generic type is simply a stand-in for the type that will be declared when the Bag is instantiated.
Bag Data Structure:
import java.util.Iterator;
public class Bag<Item> implements Iterable<Item> {
private Node first;
private class Node {
Item item;
Node next;
}
public void add(Item item) {
Node oldfirst = first;
first = new Node();
first.item = item;
first.next = oldfirst;
}
public Iterator<Item> iterator() {
return new ListIterator();
}
private class ListIterator implements Iterator<Item> {
private Node current = first;
public boolean hasNext() {
return current != null;
}
public void remove() { }
public Item next() {
Item item = current.item;
current = current.next;
return item;
}
}
}
A Thing object:
public class Thing{
private int value;
public Thing (int value) {
this.value = value;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public String toString() {
return ("" + value);
}
}
Demonstration:
import java.util.Iterator;
public class Test {
public static void main(String[] args) {
Test test = new Test();
test.testDrive();
}
public void testDrive() {
/* create a Bag and add Thing objects to it */
Bag<Thing> bag = new Bag<Thing>();
for(int i = 0; i<10; ++i){
Thing thing = new Thing(i);
bag.add(thing);
}
Iterator it = bag.iterator();
while(it.hasNext()) {
System.out.println(it.next());
}
System.out.println("-------------");
/* careful - Nodes in the Bag are accessible if we still have the reference */
bag = new Bag<Thing>();
for(int i = 0; i<10; ++i){
Thing thing = new Thing(i);
bag.add(thing);
thing.setValue(thing.getValue()*2);
}
it = bag.iterator();
while(it.hasNext()) {
System.out.println(it.next());
}
System.out.println("-------------");
/* let's put something else in a Bag (Strings instead of Things) */
Bag<String> anotherBag = new Bag<String>();
for(int i = 0; i<10; ++i){
anotherBag.add("" + (i*100));
}
it = anotherBag.iterator();
while(it.hasNext()) {
System.out.println(it.next());
}
}
}