You get a bonus - 1 coin for daily activity. Now you have 1 coin

Collection and container in programming. Java collections example

Lecture



A programming collection is a program object containing, in one way or another, a set of values ​​of the same or different types, and allowing access to these values.

The collection allows you to record values ​​in yourself and retrieve them. The purpose of the collection is to serve as a repository of objects and provide access to them. Usually collections are used to store groups of similar objects that are subject to stereotypical processing. Different methods can be used to refer to a specific element of the collection, depending on its logical organization. An implementation may allow for individual operations on collections as a whole. The presence of operations on collections in many cases can significantly simplify programming.

Collections and containers

A collection or container groups some variable (possibly zero) number of data elements that have some common meaning to solve the problem. Operations are performed on them in some way. Typically, data elements are of the same type or, in languages ​​that support inheritance, types will be derived from some common ancestor type. A collection is a concept that applies to abstract data types and does not prescribe a specific implementation through a specific data structure, although there is often a well-established choice. Containers in type theory are abstractions that allow collections of various structures, such as lists and trees, to be represented in some uniform way. The (unary) container is defined by the indices S and the family of types at positions P indexed by S: the function from the types of indices to the type of elements is given. Containers can be considered as canonical classes for collections of various types. Lists are indexed by natural numbers (including zero). For lists, a maximum index is defined. Natural numbers as indices are isomorphic to lists. For trees, the tree structure can be expressed through indexes without specific information about the contents of the nodes. Indexes of structure elements in memory are isomorphic to paths from the root of a tree to its nodes.

Classification

By general characteristics

  • The collection can have a constant or dynamically changing size. In the first case, only a strictly defined number of objects can be written into the collection, in the second, the collection allows the placement of as many objects as necessary (of course, within the limits set by technical limitations). In most cases, speaking of the collection, they mean a dynamic collection, that is, a collection of the second type, although, for example, a regular static array is also a collection.
  • A collection can only store objects of the same or different types. In the second case, talking about a heterogeneous collection.

According to the logic of the organization

Depending on how logically organized access to collection data is, the following main types are distinguished:

  • Vector - the elements of the collection are ordered, each has its own number, called an index , which can be accessed at any time. As a rule, consecutive integers or the values ​​given to them are used as indices. To refer to a vector element, use the vector name and index value. When a new element is added, it is added either to the end of the vector, or to the position with the specified index. Removing an element from a vector results in an empty element.
  • Matrix - the elements have two ordered indices, each of which is an integer or a value that is convertible to an integer. To access an element, you need to specify the name of the matrix and both indexes. A new item can only be added to a position with a given pair of indexes. Deletion results in an empty item.
  • A multidimensional array is a logical development of the idea of ​​a vector and a matrix to a greater (generally, arbitrary) number of indices.
  • List - the elements of the collection are ordered, the elements have no identifiers. List - a collection with sequential access. At any time, the first item in the collection is available (usually the last one is also available). From any element of the collection, you can access the next in order, so you can consistently walk from the first element of the list to any desired. The implementation allowing backward passage is possible (to the previous element from the known one). A new item can be added to the beginning or to the end of the list. When an element is removed from the beginning of the list, the first element becomes the next one, when removed from the end, the previous one, from the middle, the previous and next elements become, respectively, the previous one and the next one for the other.
  • Stack - a collection that implements the principle of storage “LIFO” (“the last one came, the first came out”). The stack is always available only one item - the one that was added last. A new item can be added to the stack, it will become current. The current item can always be removed (“take”) from the stack, after which the item that was added directly in front of it becomes available.
  • The queue is a collection that implements the storage principle “FIFO” (“first came, first came out”). Only one item is constantly available in the queue - the one that was added to the very first of the existing ones. When you add a new item, it enters the queue. The current item can be deleted - then the item added by the first one remaining will become current.
  • An associative array (dictionary) is an unordered collection that stores key-value pairs. Access to the elements is made by key. Values ​​of different types can be used as keys, the only restriction is that the key type must allow comparison for equality. Any pair can be removed at any time. Only a pair can be added (with a certain key). A ban on duplication of keys in the collection may be introduced. If there is no such restriction, then when accessing a duplicate key, either the nth value found (where n is either permanently or determined by the form of the request) or all values ​​with this key can be returned.
  • A set is an unordered collection that stores a set of unique values ​​and supports the operations of adding, deleting, and defining an entry for them. As a rule, operations similar to operations with mathematical sets are supported for sets: union, intersection, symmetric set difference, and asymmetric set difference.
  • A multiset is an unordered collection, similar to a set, but allowing the presence of two or more identical values ​​in a collection at the same time.

By implementation

At the implementation level, a collection can be one of the following data structures:

  • Array
  • Singly linked list
  • Doubly linked list
  • Stack
  • Hash table
  • Bitmap

Collection operations

Depending on the logical type of the collection and on the implementation, various operations on the collections as a whole may be supported. In all cases, operations can be performed only on pairs of collections of the same type (and, if the collections are not heterogeneous, with one type of elements). The following operations may also be supported:

  • For all types of collections - the union. The result of such an operation is a collection of the same type as the operands, containing all the elements contained in the operands.
  • For vectors and matrices containing numerical values ​​- typical mathematical operations on objects of the same name: addition, subtraction, multiplication, transposition.
  • For vectors, retrieve a range of indices. The result of such an operation will be a vector of the same type, containing only those elements of the source that fall within a certain specified range.
  • For vectors and lists - sorting.
  • For sets, union, intersection, difference, and symmetric difference.

Java Collections Framework Overview

Java collections

Java Collections are one of the pillars of the Java Core. They are used in almost every application, so we simply must be able to use the Java Collections Framework effectively.

What are Collections?

Collections are containers, groups of elements that constitute a unit.

For example: a candy pot, a list of names, etc. Collections are used in almost every programming language and Java is no exception. As soon as the collections appeared in Java, there were only a few classes: Vector, Stack, Hashtable, Array. But already in Java 1.2, a full-fledged Java Collections Framework appeared, with which we will get acquainted today.

Java collections consist of several parts.

  • Interfaces: In collections, interfaces provide an abstract data type for representing the java.util.Collection collection - the framework root interface. It is at the top of the collections hierarchy. It contains the most important methods: size() , iterator() , add() , remove() , clear() . Each collection must implement these methods. There are also other important interfaces java.util.List, java.util.Set, java.util.Queue and java.util.Map . Map is the only interface that does not inherit the Collection interface, but is an integral part of collections. All framework interfaces are in the java.util package.
  • Implementation: Java provides ready-made classes with the implementation of the above collections. We can use them to create new types of collections in our program. With the ArrayList, LinkedList, HashMap, TreeMap, HashSet, TreeSet you can solve a huge number of tasks, but if we need a special implementation of a particular collection, we can inherit it and work with our implementation. In Java 1.5, thread-safe collections were invented that allowed us to change the contents of the collection while iterating over the elements. The most popular are: CopyOnWriteArrayList, ConcurrentHashMap, CopyOnWriteArraySet . These classes are in the java.util.concurrent package. All collection classes are in the java.util and java.util.concurrent packages.
  • Algorithms: Algorithms are useful methods that solve trivial tasks, for example: searching, sorting and shuffling elements of a collection.
  • The class diagram below shows the Java Collections Framework hierarchy. For simplicity, I have included only frequently used interfaces and classes.

Collection and container in programming.  Java collections example

Benefits of the Java Collections Framework

The Java Collections Framework has the following benefits:

  • Requires less effort. The framework has many common types of collections and useful methods for manipulating data. Thus, we can focus on business logic, rather than developing our APIs.
  • Excellent quality - the use of well-proven collections increases the quality of our program.
  • Reuse and compatibility

Collection interfaces

Interfaces are the foundation of the Java Collections Framework. Note that all interfaces are Generic, for example, public interface Collection . The use of is an indication of the type of object that the collection may contain. This helps to reduce runtime errors by checking the types of objects at compile time.

It should be noted that the Java platform does not provide separate interfaces for each type of collection. If an operation is not supported, then the collection implementation throws UnsupportedOperationException.

Briefly for each collection

Iterator Interface (Iterator)

The iterator provides methods for iterating over elements of any collection. We can get an instance of an iterator from the collection using the iterator method. Iterators allow you to remove items from the base collection while iterating.

Set Interface

A collection is a collection that cannot contain duplicate elements. This interface represents a mathematical abstraction for representing sets in the form of a deck of cards.

The Java platform contains three Set implementations: HashSet, TreeSet and LinkedHashSet.И And the Set interface does not allow random access to an item in the collection. We can use an iterator or loop for each element to iterate over the elements.

Interface List (List)

The list is an ordered set of elements and may contain duplicate elements. You can access any item by index. The list is a dynamic array. The list is one of the most used types of collections. ArrayList and LinkedList classes are implementations of the List interface.

Here is a small example of use:

Java
1
2
3
4
5
6
7
8
9
List strList = new ArrayList<>();
//добавить в конец
strList.add(0, "0");
//добавить элемент в определенное место
strList.add(1, "1");
//заменить элемент
strList.set(1, "2");
//удалить элемент
strList.remove("1");

Interface Queue

A queue is a collection that is used to store multiple items.

In the queue, usually, but not necessarily, the elements are arranged according to the FIFO principle (first-in, first-out = first entered, first left). In the FIFO queue, all new items are inserted at the end of the queue.

Interface dequeue

The Dequeue collection supports inserting an element and deleting an element both at the beginning and at the end of the collection. The name Deque is an abbreviation for “double-end” and, as a rule, is pronounced “deck”. Most of the implementations of DEQUE do not set limits on the number of elements.

This interface defines methods for accessing elements at the ends of the deck. Methods are provided for inserting, deleting, retrieving an item.

Map Interface

A map is an object that contains keys and values. Map cannot contain duplicate keys: Each key can have only one value.

The Java platform contains three Map implementations: HashMap, TreeMap and LinkedHashMap.

Interface listiterator

ListIterator (an iterator for lists) allows the programmer to go through the list in any direction, change the list in the iteration, and get the current position of the iterator in the list.

SortedSet interface

SortedSet is a set in which elements are stored in ascending order.

SortedMap interface

SortedMap contains items in ascending order of keys. This Map is an analogue of SortedSet. SortedMap is used for naturally ordered key / value pairs, such as dictionaries and telephone directories.

Classes implementing Java collections

The Java Collections framework provides a large number of classes with implementation of collection interfaces. The most used and common implementations are ArrayList , HashMap and HashSet . Typically, classes that implement collections are not thread-safe.

Later in this article we will examine the most used classes in the Java Collections framework.

HashSet Class

This is the basic implementation of the Set interface, which is based on a HashMap .

This class offers the same execution time for basic operations (add, remove , contains и size ) . We can set the initial capacity and load factor for this collection.

Class treeset

NavigableSet is based on TreeMap. Elements can be ordered in the order they are added or using a comparator.

This implementation provides log (n) execution time for basic operations ( add, remove and contains ).

Class ArrayList

ArrayList - the implementation of the List interface as a variable-length array. Implements all list operations. Plus, ArrayList provides methods for manipulating the size of the array, which is used to store the list. (This class roughly corresponds to a vector, but is not synchronized ).

LinkedList class

LinkedList - the implementation of the List and Deque interfaces in the form of a doubly linked list. Performs all additional operations with the list.

Class HashMap

HashMap is an implementation of the Map interface. This implementation provides all additional Map operations and allows null values ​​and keys with a null value. The HashMap class is roughly equivalent to Hashtable , except that it is not synchronized and allows null . This class makes no guarantees for the orderly placement of items.

Class treemap

TreeMap is a red-black tree based on NavigableMap. Map sorted by comparator.

This implementation provides log (n) execution time for the containsKey, get, put and remove operations.

PriorityQueue class

Queuing elements are given in the FIFO order, but sometimes we want to add elements based on their priority. In this case, we can use PriorityQueue, while providing a implementation of the comparator for PriorityQueue elements. It should be noted that PriorityQueue does not allow storing null

Collections class

This class consists solely of static methods that work or return collections. It contains polymorphic algorithms that are used when working with collections.

This class contains the methods of the basic algorithms of the framework framework, namely the methods of binary search, sorting, mixing, as well as a method that returns the reverse order of elements and many others.

Synchronized shells

Synchronized shells add automatic synchronization (thread-safe) to a specific collection. Each of the six main collection interfaces ( Collection, Set, List, Map, SortedSet , and SortedMap ) has a static factory synchronization method.

Java
1
2
3
4
5
6
public static Collection synchronizedCollection(Collection c);
public static Set synchronizedSet(Set s);
public static List synchronizedList(List list);
public static Map synchronizedMap(Map m);
public static SortedSet synchronizedSortedSet(SortedSet s);
public static SortedMap synchronizedSortedMap(SortedMap m);

Each of these methods returns a synchronized (thread-safe) collection.

Immutable shells

Immutable wrappers / wrappers do not allow changing the collection, intercepting all operations that change collections and throw an UnsupportedOperationException in the event that someone wants to do this. These methods are:

Java
1
2
3
4
5
6
public static Collection unmodifiableCollection(Collection c);
public static Set unmodifiableSet(Set s);
public static List unmodifiableList(List list);
public static Map unmodifiableMap(Map m);
public static SortedSet unmodifiableSortedSet(SortedSet s);
public static SortedMap unmodifiableSortedMap(SortedMap m);

Which collection to choose?

This question is often asked by programmers when choosing between the many collections represented in the Java Collections Framework. Below is a table that contains all the most significant characteristics of the collections:

Collection Okay

chivy

Random access Key value Duplicate Items Zero element Potoko

security

ArrayList Yes Yes Not Yes Yes Not
Linkedlist Yes Not Not Yes Yes Not
Hashset Not Not Not Not Yes Not
Treeset Yes Not Not Not Not Not
Hashmap Not Yes Yes Not Yes Not
Treemap Yes Yes Yes Not Not Not
Vector Yes Yes Not Yes Yes Yes
Hashtable Not Yes Yes Not Not Yes
Properties Not Yes Yes Not Not Yes
Stack Yes Not Not Yes Yes Yes
CopyOnWriteArrayList Yes Yes Not Yes Yes Yes
ConcurrentHashMap Not Yes Yes Not Not Yes
CopyOnWriteArraySet Not Not Not Not Yes Yes

In this review, we learned the basic components of the Java Collections Framework. In the following articles, we will analyze popular collections and learn how to use each collection as intended.


Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Structures and data processing algorithms.

Terms: Structures and data processing algorithms.