Lecture
Arrays can be used to store a large amount of data of the same type, but they are not always the ideal solution. First, the length of the array is set in advance and if the number of elements is not known in advance, you will have to either allocate memory “with a margin” or take complex steps to redefine the array. Secondly, the elements of an array have a rigidly defined placement in its cells, therefore, for example, removing an element from an array is not a simple operation.
In programming, data structures such as the stack, queue, list, set, etc., united by the common name collection, have long and effectively been used. A collection is a group of elements with the operations of adding, extracting and searching for an element. The mechanism of operation of operations varies significantly depending on the type of collection. For example, stack elements are ordered into a sequence, adding a new element can only occur at the end of this sequence, and only the element at the end (that is, the last one added) can be obtained. The queue , in contrast, allows you to get only the first element (elements are added to one end of the sequence, and “taken” from the other). Other collections (for example, a list ) allow you to get an element from any place in the sequence, and the set does not order the elements at all and allows (besides adding and deleting) only to find out if this element is contained in it.
The Java language provides a library of standard collections that are assembled in the java.util package, so there is no need to program them yourself.
When working with collections, it is important to avoid the mistakes of beginners - use the most versatile collection instead of the one needed to solve the problem - for example, a list instead of a stack. If the logic of the program is such that the data must be stored on the stack (appear and processed in reverse order), you should use the stack. In this case, you will not be able to violate the logic of data processing, turning directly to the middle of the sequence, which means that the chance of the appearance of difficult-to-find errors decreases sharply.
To select the collection that best suits the condition of the problem, you need to know the features of each of them. This knowledge is compulsory for any programmer, since any modern task is rarely done without the use of certain collections. Some of the information you can learn from the further presentation.
Collections in the java.util library are represented by a set of classes and interfaces.
Each class implements a certain collection with a specific set of operations for accessing elements. To use the collection in your program, you need to create an object of the appropriate class.
Elements of most collections are of type Object . This means that (as opposed to a regular array) you do not need to specify in advance the type of elements that will be placed in the collection. You can add objects of any class to it, since all classes are descendants of the Object class, moreover, objects of completely different classes can be stored in one collection.
Of course, this can lead to difficulties. If you want to perform some operations on a collection element (and you place objects in the collection just to extract and process them later), you cannot use its methods without bringing the object to its “real” class by explicitly casting .
For example, you have an object of class String (plain string) and you want to add it to the stack stack using the push(Object item) method:
String str = "Ценная строка"; stack.push(str); The collection storing elements of type Object immediately “forgets” that your object is a string, because when it was added, the automatic casting of the String type to the Object type was performed. You can retrieve your object with the pop() method, but to return it to the previous type (and without this you cannot use any of its methods), you will have to implement an explicit conversion with the operator (String) :
str = (String)stack.pop(); This is not a problem, you just need to remember which objects of the class you put into the collection and perform the appropriate type conversion on each element in the collection.
But if you try to cast the object to the wrong type, an error will occur in the program:
stack.push(new Dog("Шарик", 12)); // помещаем в стек собаку stack.push(new Dog("Шарик", 12)); // помещаем в стек собаку str = (Mouse)stack.pop(); // вынимаем собаку и пытаемся объявить ее мышью, но эти классы не связаны наследованием и программа выдаст ошибку во время выполнения str = (Mouse)stack.pop(); // вынимаем собаку и пытаемся объявить ее мышью, но эти классы не связаны наследованием и программа выдаст ошибку во время выполнения So, the opportunity to put any objects in the collection will most likely fail. Imagine that your program must “remember” that the first element of the list is a string, the second is a number, the third is a dog, and the fourth is a number again. And it will probably not be able to process them all in a cycle, since these objects do not have common methods. As a result, all the benefits of using the collection are lost. Therefore, in each collection should be placed objects of only one class (and derivatives of it).
Some collections in the java.utils package are not represented by independent classes. For example, a queue and a list. But for these useful data structures, the appropriate interfaces are defined, that is, you can use any class that implements such an interface.
An interface can be used as a data type in the same way as a class. The only difference is that interface type objects cannot be created directly - you must select a class that supports this interface and call its constructor.
Suppose, for example, you need a list, one of the most convenient and frequently used data structures. A list is an ordered sequence of elements, each of which can be obtained from its position. In addition, you can add elements to the required positions of the list and delete them, while (and this is the main convenience, unlike an array), the remaining elements are automatically “moved apart” or “shifted” so that the continuous connectivity of the list is preserved.
The list is presented in the java.util package by the List interface. You can create variables of this type and declare functions with this parameter. For example, the Game class in a checkers program (see task 16) has a checkers field of type List , which stores all black and white checkers (objects of type Checker ). When a checker is eaten, it simply needs to be removed from the list using one of the convenient methods defined in the List: interface List:
checkers.remove(check); // удаляем из списка checkers съеденную шашку check When the program needs to find out about all the remaining checkers (for example, to draw them on the screen), the Game class getCheckers() method will give it a list:
List ch = currentGame.getCheckers(); // здесь currentGame — объект класса Game Now the program can work with the variable ch as a list (for example, in turn get all its objects).
At the time of creating a new game (that is, in the Game class constructor), you must obviously create 24 checkers located on standard positions and add them to the checkers list. But the list also needs to be created, and we cannot use the design
checkers = new List(); because List not a class and does not have a constructor. We need to select any class that implements the List interface and create an object of this class. For example, the class Vector
checkers = new Vector(); or class ArrayList *:
checkers = new ArrayList(); Regardless of which class we choose, the checkers field will be of type List and our choice will not be affected by further work with it. We will add checkers to the list, remove them from it, return the checkers stored in the list, etc. through the methods of the List interface.
The Collection interface contains a set of common methods that are used in most collections. Consider the main ones.
add(Object item) - adds a new item to the collection. The method returns true if the addition was successful and false if not *. If the items in the collection are somehow ordered, the new item is added to the end of the collection.
clear() - removes all elements of the collection.
contains(Object obj) - returns true if the obj object is contained in the collection and false if not.
isEmpty() - checks if the collection is empty.
remove(Object obj) - removes the obj element from the collection. Returns false if no such item was found in the collection.
size() - returns the number of elements in the collection.
There are variations of these methods, which take any other collection as a parameter. For example, the addAll(Collection coll) method adds all the elements of another coll collection to the end of the given, the removeAll(Collection coll) method removes all elements from the collection that are also in the coll collection, and the retainAll(Collection coll) method does the opposite, removing all elements except those contained in coll .
The toArray() method returns all elements of the collection as an array.
The List interface describes an ordered list. The elements of the list are numbered, starting from zero and a specific element can be accessed by an integer index. The List interface is a successor of the Collection interface, therefore it contains all its methods and adds several of its own methods to them:
add(int index, Object item) - inserts the item item at the position index , while the list is moved apart (all elements, starting at the position index , increase their index by 1);
get(int index) - returns the object located in the index position;
indexOf(Object obj) - returns the index of the first appearance of the obj element in the list;
lastIndexOf(Object obj) - returns the index of the last occurrence of the obj element in the list;
add(int index, Object item) - replaces the element that is in the index position with the item object;
subList(int from, int to) - returns a new list that is a part of the given (starting from the position from up to the position to-1 inclusive).
The Set interface describes the set. The elements of the set are not ordered; the set cannot contain two identical elements. The Set interface is inherited from the Collection interface, but does not add any new methods. Only the meaning of the add(Object item) method add(Object item) - it will not add an item object if it is already present in the set.
The Queue interface describes a queue. Items can be added to the queue only from one end, and retrieved from the other (similar to the queue in the store). The Queue interface is also inherited from the Collection interface. Queue specific methods:
poll() - returns the first item and removes it from the queue.
peek() - returns the first element of the queue without deleting it.
offer(Object obj) - adds a new element to the end of the queue and returns true if the insertion was successful.
The element() and remove() methods work similarly to the poll() and peek() methods, but if the queue is empty, raise an exception.
Collection classes that implement the interfaces described above are descendants of the AbstractCollection abstract class. The hierarchy of these classes is shown in the figure (interfaces are shown in blue). We will consider those of them that are of the greatest practical interest.
Vector (vector) - a set of ordered elements, each of which can be accessed by index. In fact, this collection is a regular list.
A feature of the vector is that in addition to the current size, determined by the number of elements in it and returned by the size() method, it has the capacity returned by the capacity() method — the size of the memory allocated for the elements, which can be larger than the current size. It can be increased using the ensureCapacity(int minCapacity) method or trimToSize() with the size of the vector using the trimToSize() method. Every time you need to add a new element to a completely “filled” vector, the capacity increases with a margin.
There are four constructors in the Vector class:
Vector() - creates an empty vector with a capacity of 10 elements;
Vector(int capacity) - creates an empty vector of the specified capacity;
Vector(int capacity, int increment) - creates an empty vector of the specified capacity, and also sets the number by which the capacity will be increased if necessary;
Vector(Collection c) - creates a vector and fills it with elements of another collection.
The Vector class implements the List interface, the main methods of which are named above. Several more are added to these methods. For example, the firstElement() method allows to refer to the first element of the vector, the lastElement() method to its last element. The removeElementAt(int pos) method removes an element at a given position, and the removeRange(int begin, int end) method removeRange(int begin, int end) removes several consecutive elements. All these operations could be performed by a combination of the basic methods of the List interface, so the functionality does not fundamentally change.
The ArrayList class is an analogue of the Vector class. It is a list and can be used in the same situations. The main difference is that it is not synchronized and the simultaneous operation of several parallel processes with an object of this class is not recommended. In normal situations, it works faster. *
Stack - a collection that unites elements in the stack. The stack works on the principle of LIFO (the last to come - the first to leave). The elements are put on the stack “on top of each other”, and only the “top” element can be taken, i.e. the one that was last on the stack. The stack is characterized by operations implemented in the following methods of the Stack class:
push(Object item) - puts an item on top of the stack;
pop() - remove the top element from the stack;
peek() - returns the top element without removing it from the stack;
empty() - checks if the stack is empty;
search(Object item) - searches for the "depth" of the object in the stack. The top element has position 1, below it - 2, etc. If there is no object in the stack, returns -1.
The Stack class is an inheritor of the Vector class, so it has all its methods (and, of course, implements the List interface). However, if the program needs to model the stack, it is recommended to use only five of the above methods *.
The advantage of using arrays and collections is not only that you can put an arbitrary number of objects into them and retrieve them if necessary, but also that all these objects can be comprehensively processed. For example, display all the checkers contained in the checkers list. In the case of an array, we use a for loop:
for (int i = 1; i < array.length; i++){ // обрабатываем элемент array[i] } Dealing with the list, we can do the same, only instead of array[i] write array.get(i) . But we cannot do this with collections whose elements are not indexed (for example, by queue or set). And in the case of an indexed collection, one should be well aware of the features of its work: how to determine the number of elements, how to access an element by index, whether the collection can be sparse (i.e., there can be indices with which no elements are associated), etc. .
In programming, there are several time-tested and detailed techniques of the structural organization of the program, called design patterns (templates) . One of these patterns is called Iterator . The idea is that an object is “attached” to the collection, the only purpose of which is to give all the elements of this collection in a certain order, without revealing its internal structure.
The java.util package describes the Iterator interface embodying this design pattern. It has only three methods:
next() returns the next element of the collection to which the iterator is attached (and makes it current). The iteration order is determined by the iterator itself.
hasNext() returns true if the enumeration of elements is not yet complete.
remove() removes the current item
The Collection interface, in addition to the previously discussed methods, has an iterator() method, which returns an iterator for this collection, ready to bypass it. With this iterator, you can handle all the elements of any collection in the following simple way:
Iterator iter = coll.iterator(); // coll — коллекция, элементы которой мы хотим обработать Iterator iter = coll.iterator(); // coll — коллекция, элементы которой мы хотим обработать while (iter.hasNext()) { // обрабатываем объект, возвращаемый методом iter.next() } For collections whose elements are indexed, a more functional iterator is defined, allowing one to move both in the forward and in the opposite direction, as well as add elements to the collection. Such an iterator has a ListIterator interface inherited from the Iterator interface and supplementing it with the following methods:
previous() - returns the previous element (and makes it current);
hasPrevious() - returns true if the previous element exists (that is, the current element is not the first element for this iterator);
add(Object item) - adds a new item before the current item;
set(Object item) - replaces the current item;
nextIndex() and previousIndex() are used to obtain the indices of the next and previous elements, respectively.
The List interface defines a listIterator() method that returns a ListIterator iterator for traversing this list.
Write a Student class that provides information about the student's name with the getName() method and its course with the getCourse() method.
Write the method printStudents(List students, int course) , which gets the list of students and the course number and prints the names of those students who are enrolled in this course to the console. To bypass the list in this method, use an iterator.
Test your method (for this you will first have to create a dozen objects of the class Student and put them in the list).
LinkedList is a bidirectional list that implements the List and Queue interfaces.
The HashSet class implements the Set interface. It is used in cases when it is necessary to keep only one copy of each element. Identical objects are “computed” using the hashCode() method of the Object class, which must return different values for different objects.
The class LinkedHashSet is a set whose elements are stored in the form of a bidirectional list. Its successor, the TreeSet class TreeSet is an ordered set that is stored as a binary tree, which ensures the speed of searching for the desired element. TreeSet implements the SortedSet interface.
The SortedSet interface describes a set, whose elements can be ordered according to a certain principle, for example, according to the natural order of its elements. The elements of the set are not indexed, but there is the concept of a larger and smaller element.
first() and last() return the first and last elements of the set.
subSet(Object fromElement, Object toElement) returns a subset of an ordered set containing elements that are large fromElement (including itself) and less than toElement . This method has two simple variants headSet(Object toElement) and tailSet(Object fromElement) , which return a subset consisting of all elements smaller and larger than the given one, respectively.
The way the elements are organized describes the Comparator interface. It has two methods:
compare(Object obj1, Object obj2) - returns a negative number if obj1 is considered less than obj2 , zero if they are equal and a positive number if obj1 greater than obj2
equals(Object obj1, Object obj2) - returns true if objects are considered equal
You can create your own way of comparing elements by writing a class that implements the Comparator interface and overriding the compare() and equals() methods. The TreeSet class, for example, has a constructor with a parameter of the Comparator type, into which you can pass an object of this new class. As a result, the elements of the set will be sorted in the way we like.
Write the union(Set set1, Set set2) and intersect(Set set1, Set set2) that implement the union and intersection operations of two sets. Test the performance of these methods on two pre-populated sets. (You will need to write a helper method that outputs all the elements of the set to the console).
Start writing the main method of your program, on the outline of which you have already worked using arrays. This time you should get a “real” method that uses, where necessary, collection classes.
Comments
To leave a comment
OOP and Practical JAVA
Terms: OOP and Practical JAVA