22.7. The Vector and Stack Classes
20.2. Lists
A list is a popular data structure for storing data in sequential order. For example, a list of students, a list of available rooms, a list of cities, and a list of books can all be stored using lists. The operations listed below are typical of most lists:
-
Retrieve an element from a list.
-
Insert a new element to a list.
-
Delete an element from a list.
-
Find how many elements are in a list.
-
Find whether an element is in a list.
-
Find whether a list is empty.
There are two ways to implement a list. One is to use an array to store the elements. Arrays are dynamically created. If the capacity of the array is exceeded, create a new, larger array and copy all the elements from the current array to the new array. The other approach is to use a linked structure . A linked structure consists of nodes. Each node is dynamically created to hold an element. All the nodes are linked together to form a list. Thus you can declare two classes for lists. For convenience, let's name these two classes MyArrayList and MyLinkedList . These two classes have common operations but different data fields. The common operations can be generalized in an interface or an abstract class. As discussed in §11.6.8, "Interfaces vs. Abstract Classes," a good strategy is to combine the virtues of interfaces and abstract classes by providing both an interface and an abstract class in the design so that the user can use either of them, whichever is convenient . Such an abstract class is known as a convenience class .
Let us name the interface MyList and the convenience class MyAbstractList . Figure 20.1 shows the relationship of MyList , MyAbstractList , MyArrayList , and MyLinkedList . The methods in MyList and the methods implemented in MyAbstractList are shown in Figure 20.2. Listing 20.1 gives the source code for MyList .
Figure 20.1. MyList defines a common interface for MyAbstractList , MyArrayList , and MyLinkedList .
Figure 20.2. MyList supports many methods for manipulating a list. MyAbstractList provides a partial implementation of the MyList interface.
(This item is displayed on page 662 in the print version)
Listing 20.1. MyList.java
(This item is displayed on pages 661 - 662 in the print version)
1 public interface MyList { 2 /** Add a new element o at the end of this list */ 3 public void add(Object o); 4 5 /** Add a new element o at the specified index in this list */ 6 public void add( int index, Object o); 7 8 /** Clear the list */ 9 public void clear(); 10 11 /** Return true if this list contains the element o */ 12 public boolean contains(Object o); 13 14 /** Return the element from this list at the specified index */ 15 public Object get( int index); 16 17 /** Return the index of the first matching element in this list. 18 * Return -1 if no match. */ 19 public int indexOf(Object o); 20 21 /** Return true if this list contains no elements */ 22 public boolean isEmpty(); 23 24 /** Return the index of the last matching element in this list 25 * Return -1 if no match. */ 26 public int lastIndexOf(Object o); 27 28 /** Remove the first occurrence of the element o from this list. 29 * Shift any subsequent elements to the left. 30 * Return true if the element is removed. */ 31 public boolean remove(Object o); 32 33 /** Remove the element at the specified position in this list 34 * Shift any subsequent elements to the left. 35 * Return the element that was removed from the list. */ 36 public Object remove( int index); 37 38 /** Replace the element at the specified position in this list 39 * with the specified element and return the new set. */ 40 public Object set( int index, Object o); 41 42 /** Return the number of elements in this list */ 43 public int size (); 44 } |
MyAbstractList declares variable size to indicate the number of elements in the list. The methods isEmpty and size can be implemented in the class in Listing 20.2.
Listing 20.2. MyAbstractList.java
(This item is displayed on pages 662 - 663 in the print version)
1 public abstract class MyAbstractList implements MyList { 2 protected int size = ; // The size of the list 3 4 /** Create a default list */ 5 protected MyAbstractList() { 6 } 7 8 /** Create a list from an array of objects */ 9 protected MyAbstractList(Object[] objects) { 10 for ( int i = ; i < objects.length; i++) 11 this .add(objects[i]); 12 } 13 14 /** Add a new element o at the end of this list */ 15 public void add(Object o) { 16 add(size, o); 17 } 18 19 /** Return true if this list contains no elements */ 20 public boolean isEmpty() { 21 return size == ; 22 } 23 24 /** Return the number of elements in this list */ 25 public int size() { 26 return size; 27 } 28 29 /** Remove the first occurrence of the element o from this list. 30 * Shift any subsequent elements to the left. 31 * Return true if the element is removed. */ 32 public boolean remove(Object o) { 33 if (indexOf(o) >= ) { 34 remove(indexOf(o)); 35 return true ; 36 } 37 else 38 return false ; 39 } 40 } |
The following sections give the implementation for MyArrayList and MyLinkedList , respectively.
20.2.1. Array Lists
Array is a fixed-size data structure. Once an array is created, its size cannot be changed. Nevertheless, you can still use arrays to implement dynamic data structures. The trick is to create a larger new array to replace the current array if the current array cannot hold new elements in the list. This section shows how to use arrays to implement MyArrayList .
Initially, an array, say data of Object[] type, is created with a default size. When inserting a new element into the array, first make sure that there is enough room in the array. If not, create a new array twice as large as the current one. Copy the elements from the current array to the new array. The new array now becomes the current array. Before inserting a new element at a specified index, shift all the elements after the index to the right and increase the list size by 1, as shown in Figure 20.3.
Figure 20.3. Inserting a new element to the array requires that all the elements after the insertion point be shifted one position to the right so that the new element can be inserted at the insertion point.
(This item is displayed on page 664 in the print version)
Note
| | The data array is of type Object[] . Each cell in the array actually stores the reference of an object. |
To remove an element at a specified index, shift all the elements after the index to the left by one position and decrease the list size by 1, as shown in Figure 20.4.
Figure 20.4. Deleting an element from the array requires that all the elements after the deletion point be shifted one position to the left.
(This item is displayed on page 664 in the print version)
MyArrayList uses an array to implement MyAbstractList , as shown in Figure 20.5. Its implementation is given in Listing 20.3.
Figure 20.5. MyArrayList implements a list using an array.
Listing 20.3. MyArrayList.java
(This item is displayed on pages 664 - 666 in the print version)
1 public class MyArrayList extends MyAbstractList { 2 public static final int INITIAL_CAPACITY = 16 ; 3 private Object[] data = new Object[INITIAL_CAPACITY]; 4 5 /** Create a default list */ 6 public MyArrayList() { 7 } 8 9 /** Create a list from an array of objects */ 10 public MyArrayList(Object[] objects) { 11 data = objects; 12 size = objects.length; 13 } 14 15 /** Add a new element o at the specified index in this list */ 16 public void add( int index, Object o) { 17 ensureCapacity(); 18 19 // Move the elements to the right after the specified index 20 for ( int i = size - 1 ; i >= index; i ” ”) 21 data[i + 1 ] = data[i]; 22 23 // Insert new element to data[index] 24 data[index] = o; 25 26 // Increase size by 1 27 size++; 28 } 29 30 /** Create a new larger array, double the current size */ 31 private void ensureCapacity() { 32 if (size >= data.length) { 33 Object[] newData = new Object[data.length * 2 ]; 34 System.arraycopy(data, , newData, , data.length); 35 data = newData; 36 } 37 } 38 39 /** Clear the list */ 40 public void clear() { 41 data = new Object[INITIAL_CAPACITY]; 42 } 43 44 /** Return true if this list contains the element o */ 45 public boolean contains(Object o) { 46 for ( int i = ; i < size; i++) 47 if (o.equals(data[i])) return true ; 48 49 return false ; 50 } 51 52 /** Return the element from this list at the specified index */ 53 public Object get( int index) { 54 return data[index]; 55 } 56 57 /** Return the index of the first matching element in this list. 58 * Return -1 if no match. */ 59 public int indexOf(Object o) { 60 for ( int i = ; i < size; i++) 61 if (o.equals(data[i])) return i; 62 63 return -1 ; 64 } 65 66 /** Return the index of the last matching element in this list 67 * Return -1 if no match. */ 68 public int lastIndexOf(Object o) { 69 for ( int i = size - 1 ; i >= ; i ” ”) 70 if (o.equals(data[i])) return i; 71 72 return -1 ; 73 } 74 75 /** Remove the element at the specified position in this list 76 * Shift any subsequent elements to the left. 77 * Return the element that was removed from the list. */ 78 public Object remove( int index) { 79 Object o = data[index]; 80 81 // Shift data to the left 82 for ( int j = index; j < size - 1 ; j++) 83 data[j] = data[j + 1 ]; 84 85 // Decrement size 86 size ” ”; 87 88 return o; 89 } 90 91 /** Replace the element at the specified position in this list 92 * with the specified element. */ 93 public Object set( int index, Object o) { 94 Object old = data[index]; 95 data[index] = o; 96 return old; 97 } 98 99 /** Override toString() to return elements in the list */ 100 public String toString() { 101 StringBuffer result = new StringBuffer( "[" ); 102 103 for ( int i = ; i < size; i++) { 104 result.append(data[i]); 105 if (i < size - 1 ) result.append( ", " ); 106 } 107 108 return result.toString() + "]" ; 109 } 110 } |
The constant INITIAL_CAPACITY (line 2) is used to create an initial array data of type Object (line 3).
The add(int index, Object o) method (lines 16 “28) adds element o at the specified index in the array. This method first invokes ensureCapacity() (line 17), which ensures that there is a space in the array for the new element. It then shifts all the elements after the index one position to the right before inserting the element (lines 20 “21). After the element is added, size is incremented by 1 (line 27). Note that variable size is defined as protected in MyAbstractList , so it can be accessed in MyArrayList .
The ensureCapacity() method (lines 31 “37) checks whether the array is full. If so, create a new array that doubles the current array size, copy the current array to the new array using the System.arraycopy method, and set the new array as the current array.
The clear() method (lines 40 “42) creates a brand-new array with initial capacity.
The contains(Object o) method (lines 45 “50) checks whether element o is contained in the array by comparing o with each element in the array using the equals method.
The get(int index) method (lines 53 “55) simply returns data[index] . The implementation of this method is simple and efficient.
The indexOf(Object o) method (lines 59 “64) compares element o with the elements in the array starting from the first one. If a match is found, the index of the element is returned; otherwise , it returns “1 .
The lastIndexOf(Object o) method (lines 68 “73) compares element o with the elements in the array starting from the last one. If a match is found, the index of the element is returned; otherwise, it returns “1 .
The remove(int index) method (lines 78 “89) shifts all the elements before the index one position to the left and decrements size by 1.
The set(int index, Object o) method (lines 93 “97) simply assigns o to data[index] to replace the element at the specified index with element o .
The toString() method (lines 100 “107) overrides the toString method in the Object class to return a string representing all the elements in the list.
Listing 20.4 gives an example that creates a list using MyArrayList . It uses the add method to add strings to the list and the remove method to remove strings from the list. A sample run of the program is shown in Figure 20.6.
Figure 20.6. The program uses a list to store and process strings.
Listing 20.4. TestList.java
(This item is displayed on pages 667 - 668 in the print version)
1 public class TestList { 2 public static void main(String[] args) { 3 // Create a list 4 MyList list = new MyArrayList(); 5 6 // Add elements to the list 7 list.add( "America" ); // Add it to the list 8 System.out.println( "(1) " + list); 9 10 list.add( , "Canada" ); // Add it to the beginning of the list 11 System.out.println( "(2) " + list); 12 13 list.add( "Russia" ); // Add it to the end of the list 14 System.out.println( "(3) " + list); 15 16 list.add( "France" ); // Add it to the end of the list 17 System.out.println( "(4) " + list); 18 19 list.add( 2 , "Germany" ); // Add it to the list at index 2 20 System.out.println( "(5) " + list); 21 22 list.add( 5 , "Norway" ); // Add it to the list at index 5 23 System.out.println( "(6) " + list); 24 25 list.add( , "Netherlands" ); // Same as list.addFirst("Daniel") 26 System.out.println( "(7) " + list); 27 28 // Remove elements from the list 29 list.remove( "Australia" ); // Same as list.remove(0) in this case 30 System.out.println( "(8) " + list); 31 32 list.remove( 2 ); // Remove the element at index 2 33 System.out.println( "(9) " + list); 34 35 list.remove(list.size() - 1 ); // Remove the last element 36 System.out.println( "(10) " + list); 37 } 38 } |
MyArrayList is implemented using arrays. Although an array is a fixed-size data structure, MyArrayList is a dynamic data structure. The user can create an instance of MyArrayList to store any number of elements. The internal array in MyArrayList is encapsulated. The user manipulates the list through the public methods in MyArrayList .
The list can hold any objects. A primitive data type value cannot be directly stored in a list. However, you can create an object for a primitive data type value using the corresponding wrapper class. For example, to store number 10 , use one of the following methods:
list.add( new Integer( 10 )); list.add( 10 ); // JDK 1.5 autoboxing
20.2.2. Linked Lists
Since MyArrayList is implemented using an array, the methods get(int index) and set(int index, Object o) for accessing and modifying an element through an index and the add(Object o) for adding an element at the end of the list are efficient. However, the methods add(int index, Object o) and remove(int index) are inefficient because they require shifting a potentially large number of elements. You can use a linked structure to implement a list to improve efficiency for adding and removing an element anywhere in a list.
A linked list consists of nodes, as shown in Figure 20.7. Each node contains an element, and each node is linked to its next neighbor. Thus a node can be defined as a class, as follows :
class Node { Object element; Node next; public Node(Object o) { element = o; } }
Figure 20.7. A linked list consists of any number of nodes chained together.
The variable first refers to the first node in the list, and the variable last refers to the last node in the list. If the list is empty, both are null . For example, you can create three nodes to store three circle objects (radius 1, 2, and 3) in a list:
Node first, last; // Create a node to store the first circle object first = new Node( new Circle( 1 )); last = first; // Create a node to store the second circle object last.next = new Node( new Circle( 2 )); last = last.next; // Create a node to store the third circle object last.next = new Node( new Circle( 3 )); last = last.next;
The process of creating a new linked list and adding three nodes is shown in Figure 20.8.
Figure 20.8. Three nodes are added to a new linked list.
MyLinkedList uses a linked structure to implement a dynamic list. It extends MyAbstractList . In addition, it provides the methods addFirst , addLast , removeFirst , removeLast , getFirst , and getLast , as shown in Figure 20.9. Its implementation is given in Listing 20.5.
Figure 20.9. MyLinkedList implements a list using a linked list of nodes.
Listing 20.5. MyLinkedList.java
(This item is displayed on pages 670 - 672 in the print version)
1 public class MyLinkedList extends MyAbstractList { 2 private Node first, last; 3 4 /** Create a default list */ 5 public MyLinkedList() { 6 } 7 8 /** Create a list from an array of objects */ 9 public MyLinkedList(Object[] objects) { 10 super (objects); 11 } 12 13 /** Return the first element in the list */ 14 public Object getFirst() { 15 if (size == ) return null ; 16 else return first.element; 17 } 18 19 /** Return the last element in the list */ 20 public Object getLast() { 21 if (size == ) return null ; 22 else return last.element; 23 } 24 25 /** Add an element to the beginning of the list */ 26 public void addFirst(Object o) { 27 Node newNode = new Node( o ); 28 newNode.next = first; 29 first = newNode; 30 size++; 31 32 if (last == null ) 33 last = first; 34 } 35 36 /** Add an element to the end of the list */ 37 public void addLast(Object o) { 38 if (last == null ) { 39 first = last = new Node( o ); 40 } 41 else { 42 last.next = new Node( o ); 43 last = last.next; 44 } 45 46 size++; 47 } 48 49 /** Adds a new element o at the specified index in this list 50 * The index of the first element is 0 */ 51 public void add( int index, Object o) { 52 if (index == ) addFirst(o); 53 else if (index >= size) addLast(o); 54 else { 55 Node current = first; 56 for ( int i = 1 ; i < index; i++) 57 current = current.next; 58 Node temp = current.next; 59 current.next = new Node(o); 60 (current.next).next = temp; 61 size++; 62 } 63 } 64 65 /** Remove the first node and 66 * return the object that is contained in the removed node. */ 67 public Object removeFirst() { 68 if (size == ) return null ; 69 else { 70 Node temp = first; 71 first = first.next; 72 size ” ”; 73 if (first == null ) last = null ; 74 return temp.element; 75 } 76 } 77 78 /** Remove the last node and 79 * return the object that is contained in the removed node. */ 80 public Object removeLast() { 81 // Implementation left as an exercise 82 return null ; 83 } 84 85 /** Removes the element at the specified position in this list. 86 * Returns the element that was removed from the list. */ 87 public Object remove( int index) { 88 if ((index < ) (index >= size)) return null ; 89 else if (index == ) return removeFirst(); 90 else if (index == size - 1 ) return removeLast(); 91 else { 92 Node previous = first; 93 94 for ( int i = 1 ; i < index; i++) { 95 previous = previous.next; 96 } 97 98 Node current = previous.next; 99 previous.next = current.next; 100 size ” ”; 101 return current.element; 102 } 103 } 104 105 /** Override toString() to return elements in the list */ 106 public String toString() { 107 StringBuffer result = new StringBuffer( "[" ); 108 109 Node current = first; 110 for ( int i = ; i < size; i++) { 111 result.append(current.element); 112 current = current.next; 113 if (current != null ) 114 result.append( "," ); // Separate two elements with a comma 115 else 116 result.append( "]" ); // Insert the closing ] in the string 117 } 118 119 return result.toString(); 120 } 121 121 /** Clear the list */ 121 public void clear() { 122 first = last = null ; 123 } 124 125 /** Return true if this list contains the element o */ 126 public boolean contains(Object o) { 127 // Implementation left as an exercise 128 return true ; 129 } 130 131 /** Return the element from this list at the specified index */ 132 public Object get( int index) { 133 // Implementation left as an exercise 134 return null ; 135 } 136 137 /** Returns the index of the first matching element in this list. 138 * Returns -1 if no match. */ 139 public int indexOf(Object o) { 140 // Implementation left as an exercise 141 return ; 142 } 143 144 /** Returns the index of the last matching element in this list 145 * Returns -1 if no match. */ 146 public int lastIndexOf(Object o) { 147 // Implementation left as an exercise 148 return ; 149 } 150 151 /** Replace the element at the specified position in this list 152 * with the specified element. */ 153 public Object set( int index, Object o) { 154 // Implementation left as an exercise 155 return null ; 156 } 157 158 private static class Node { 159 Object element; 160 Node next; 161 162 public Node(Object o) { 163 element = o; 164 } 165 } 166 } |
The variables first and last (line 2) refer to the first and last nodes in the list, respectively. The getFirst() and getLast() methods (lines 14 “23) return the first and last elements in the list, respectively.
Since variable size is defined as protected in MyAbstractList , it can be accessed in MyLinkedList . When a new element is added to the list, size is incremented by 1 , and when an element is removed from the list, size is decremented by 1 . The addFirst(Object o) method (line 26 “34) creates a new node to store the element and insert the node to the beginning of the list. After the insertion, first should refer to this new element node (line 29), as shown in Figure 20.10.
Figure 20.10. A new element o is added to the beginning of the list.
The addLast(Object o) method (lines 37 “47) creates a node to hold element o and inserts the node at the end of the list. After the insertion, last should refer to this new element node (line 43), as shown in Figure 20.11.
Figure 20.11. A new element o is added at the end of the list.
The add(int index, Object o) method (lines 51 “63) adds an element o to the list at the specified index. Consider three cases: (1) if index is 0, invoke addFirst(o) to insert the element at the beginning of the list; (2) if index is greater than or equal to size , invoke addLast(o) to insert the element at the end of the list; (3) create a new node to store the new element and locate where to insert it. As shown in Figure 20.12, the new node is to be inserted between the nodes current and temp . The method assigns the new node to current.next and assigns temp to the new node's next .
Figure 20.12. A new element is inserted in the middle of the list.
The removeFirst() method (lines 67 “76) removes the first node from the list by pointing first to the second node, as shown in Figure 20.13.
Figure 20.13. The first node is deleted from the list.
The remove(int index) method (lines 87 “103) finds the node at the specified index and then removes it. Consider four cases: (1) if index is beyond the range of the list (i.e., index < 0 index >= size ), return null ; (2) if index is , invoke removeFirst() to remove the first node; (3) if index is size - 1 , invoke removeLast() to remove the last node; (4) locate the node at the specified index , let current denote this node and previous denote the node before this node, as shown in Figure 20.14, and assign current.next to previous.next to eliminate the current node.
Figure 20.14. A node is deleted from the list.
The implementation of methods removeLast() , clear() , contains(Object o) , get(int index) , indexOf(Object o) , lastIndexOf(Object o) , and set(int index, Object o) is omitted and left as an exercise.
To test MyLinkedList , simply replace MyArrayList in line 7 by MyLinkedList in TestList in Listing 20.4. The output should be the same as shown in Figure 20.6.
EAN: N/A
Pages: 503