1: /** LinkedBag.java 2: A class of bags whose entries are stored in a chain of linked nodes. 3: The bag is never full. 4: @author Frank M. Carrano 5: @author Timothy M. Henry 6: @version 4.0 7: */ 8: public final class LinkedBag<T> implements BagInterface<T> 9: { 10: private Node firstNode; 11: private int numberOfEntries; 13: public LinkedBag() 14: { 15: firstNode = null; 16: numberOfEntries = 0; 17: } 19: /** 20: Tests whether this bag is empty. 21: @return True if this bag is empty, or false if not. 22: */ 23: public boolean isEmpty() 24: { 25: return numberOfEntries == 0; 26: } 28: /** 29: Gets the capacity of this bag. 30: @return The integer number of entries that this bag can hold. 31: */ 32: public int getCapacity() 33: { 34: return Integer.MAX_VALUE; 35: } 37: /** 38: Gets the number of entries currently in this bag. 39: @return The integer number of entries currently in this bag. 40: */ 41: public int getCurrentSize() 42: { 43: return numberOfEntries; 44: } 46: /** 47: Adds a new entry to this bag. 48: @param newEntry The object to be added as a new entry 49: @return true if the addition is successful, or false if not. 50: */ 51: public boolean add(T newEntry) //OutOfMemoryError possible 52: { 53: //Add to beginning of chain: 54: Node newNode = new Node(newEntry); 55: newNode.next = firstNode; //Make new node reference rest of chain 56: //(firstNode is null if chain is empty) 57: firstNode = newNode; //New node is at beginning of chain 58: numberOfEntries++; 59: return true; 60: } 62: /** 63: Retrieves all entries that are in this bag. 64: @return A newly allocated array of all the entries in this bag. 65: */ 66: public T[] toArray() 67: { 68: //The cast is safe because the new array contains null entries 69: @SuppressWarnings("unchecked") 70: T[] result = (T[]) new Object[numberOfEntries]; //Unchecked cast 71: int index = 0; 72: Node currentNode = firstNode; 73: while ((index < numberOfEntries) && (currentNode != null)) 74: { 75: result[index] = currentNode.data; 76: index++; 77: currentNode = currentNode.next; 78: } 79: return result; 80: } 82: /** 83: Counts the number of times a given entry appears in this bag. 84: @param anEntry The entry to be counted. 85: @return The number of times anEntry appears in this bag. 86: */ 87: public int getFrequencyOf(T anEntry) 88: { 89: int frequency = 0; 90: int counter = 0; 91: Node currentNode = firstNode; 92: while ((counter < numberOfEntries) && (currentNode != null)) 93: { 94: if (anEntry.equals(currentNode.data)) 95: { 96: frequency++; 97: } 98: counter++; 99: currentNode = currentNode.next; 100: } 101: return frequency; 102: } 104: /** 105: Tests whether this bag contains a given entry. 106: @param anEntry The entry to locate. 107: @return true if the bag contains anEntry, or false otherwise. 108: */ 109: public boolean contains(T anEntry) 110: { 111: boolean found = false; 112: Node currentNode = firstNode; 113: while (!found && (currentNode != null)) 114: { 115: if (anEntry.equals(currentNode.data)) 116: { 117: found = true; 118: } 119: else 120: { 121: currentNode = currentNode.next; 122: } 123: } 124: return found; 125: } 127: //Locates a given entry within this bag. 128: //Returns a reference to the node containing the entry, if located, 129: //or null otherwise. 130: private Node getReferenceTo(T anEntry) 131: { 132: boolean found = false; 133: Node currentNode = firstNode; 134: while (!found && (currentNode != null)) 135: { 136: if (anEntry.equals(currentNode.data)) 137: { 138: found = true; 139: } 140: else 141: { 142: currentNode = currentNode.next; 143: } 144: } 145: return currentNode; 146: } 148: /** 149: Removes all entries from this bag. 150: */ 151: public void clear() 152: { 153: while (!isEmpty()) 154: { 155: remove(); 156: } 157: } 159: /** 160: Removes one unspecified entry from this bag, if possible. 161: @return Either the removed entry, if removal was successful, or null. 162: */ 163: public T remove() 164: { 165: T result = null; 166: if (firstNode != null) 167: { 168: result = firstNode.data; 169: firstNode = firstNode.next; //Remove first node from chain 170: numberOfEntries--; 171: } 172: return result; 173: } 175: /** 176: Removes one occurrence of a given entry from this bag, if possible. 177: @param anEntry The entry to be removed. 178: @return true if the removal was successful, or false otherwise. 179: */ 180: public boolean remove(T anEntry) 181: { 182: boolean result = false; 183: Node nodeN = getReferenceTo(anEntry); 184: if (nodeN != null) 185: { 186: //Replace located entry with entry in first node 187: //then remove first node and adjust numberOfEntries. 188: nodeN.data = firstNode.data; 189: firstNode = firstNode.next; 190: numberOfEntries--; 191: result = true; 192: } 193: return result; 194: } 196: private class Node 197: { 198: private T data; //Entry in bag 199: private Node next; //Link to next Node 201: public Node(T dataPortion) 202: { 203: this(dataPortion, null); 204: } 206: public Node 207: ( 208: T dataPortion, 209: Node nextNode 210: ) 211: { 212: data = dataPortion; 213: next = nextNode; 214: } 215: } 216: }