catalogue
1. Process of adding elements and capacity expansion mechanism
4. Traversal of list set (ArrayLIst as an example)
1. Overview of collections
In the process of program operation, the amount of data changes at any time, and the required storage structure also changes to solve some special needs, However, because the length of the array is constant and the type is fixed, we refer to the collection to meet the shortage of the array.
2. Collection (single column)
In java, the collection class uses generics by default. If the data type stored in the collection is not defined, the default data type is object.
Creation method:
Callection c = new ArrayList(); // Polymorphism: run to the right, compile to the left
c.add("a"); c.add(1); c.add(true);
Use generics:
Callection<T> c = new ArrayList<T>(); // T can use any type, such as String, Integer, Double, etc
Callection<String> c = new ArrayList<String>();
Using generics to specify the data type for the collection, type unification will not cause transformation problems.
Note: < E > parameterization of type or parameterization of parameter
common method
1. Single set method
Add elements (one at a time) c.add();
Empty (all elements) c.clear();
Whether to include specified elements (e.g. a) c.contains("a"); Return value boolean
Is it empty c.isEmpty(); Return value boolean
Deletes the specified element c.remove("a"); Return value boolean
Set length c.size(); Return value int
public class Demo1 {
public static void main(String[] args) {
// Collection c = new ArrayList();
Collection<String> c = new ArrayList<String>();
//Add elements to the collection
c.add("a");
c.add("b");
c.add("c");
c.add("d");
/*c.add(1);
c.add(true);*/
//Empty collection
//c.clear();
//Whether to include the specified element
System.out.println(c.contains("c"));//true return value: boolean
//Judge whether it is empty
System.out.println(c.isEmpty());//false
//Deletes the specified element
System.out.println(c.remove("a"));//true
//Set length
System.out.println(c.size());//3
System.out.println(c);//[b, c, d]
//Add all elements of the c1 collection (including duplicate elements)
}
}
2. Between multiple sets
Add elements from c2 set to c1 set (duplicate elements can be added)
c1.addAll(c2);
Does the c1 set contain the elements in the c2 set
c1.containsAll(c2);
Delete the elements in c1 set and c2 set
c1.removeAll(c2);
Intersection between c1 and c2 sets (if the content is changed to true, true will be returned if there is no intersection; if the content is unchanged, false will be returned; if the elements in c1 set are completely equal to those in c2 set, false will be returned.)
c1.retainAll(c2);
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
public class Demo2 {
public static void main(String[] args) {
Collection<String> c1 = new ArrayList<String>();
c1.add("a");
c1.add("b");
c1.add("c");
c1.add("d");
Collection<String> c2 = new ArrayList<String>();
c2.add("g");
c2.add("e");
c2.add("f");
//Add the element in c2 to c1, which can be repeated.
c1.addAll(c2);
System.out.println(c1);//[a, b, c, d, g, e, f]
//Does the c1 set contain elements from c2
System.out.println(c1.containsAll(c2)); //true
System.out.println(c1);//[a, b, c, d, g, e, f]
//Delete c2 element in c1
System.out.println(c1.removeAll(c2)); //true
System.out.println(c1);//[a, b, c, d]
//The intersection of c1 and c2 sets
System.out.println(c1.retainAll(c2)); //true
System.out.println(c1);//[]
}
}
3. Set to array
Default to array: object type
object[] obj = c1.toArray();
String[] str = c1.toArray(new String[c1.size()]); String type
//Set to array
c1.add("a");
c1.add("b");
c1.add("c");
c1.add("d");
Object[] obj = c1.toArray();
System.out.println(Arrays.toString(obj));//[a, b, c, d]
System.out.println(obj.length);//4
String[] str = c1.toArray(new String[c1.size()]);
System.out.println(Arrays.toString(str));//[a, b, c, d]
System.out.println(str.length);//43. List collection overview
ArrayList
Array list (continuous storage, variable length)
Features: fast query, low efficiency of intermediate insertion and deletion, and can store duplicate elements.
LinkedList
Linked list
Features: the query is slow. The query starts from the beginning node or the end node, but the insertion and deletion operation in the middle is efficient
Vector
Array list, thread safety (using synchronization lock)
Features: fast query, low efficiency of intermediate insertion and deletion, and can store duplicate elements
1. ArrayList
ArrayList<String> alist = new ArrayList<String>();
When creating an object, an array will not be created. When adding an object for the first time, an array with a capacity of 10 will be created by default.
ArrayList<String> alist = new ArrayList<String>(20);
When an object is created, an array of the specified capacity is created
transient object[] elementDate; An array of underlying stored data
1. Process of adding elements and capacity expansion mechanism
add(E e) Add an element to the end
summary:
ArrayList does not create arrays when creating objects. When adding elements for the first time, an array with a capacity of 10 will be created (created by default, or an array with a specified capacity can be created when creating objects) Before adding, you will judge whether the element can be put down after adding it. If you can, you can directly enter the array. If not, you will create a new array, and the capacity of the new array is 1.5 times that of the original array (use grow()).
Source code:
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Detection capacity
elementData[size++] = e;
return true;
}
If (mincapacity - elementdata. Length > 0) added length - array length > 0
grow(minCapacity); Array expansion method
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
Int newcapacity = oldcapacity + (oldcapacity > > 1); / / capacity expansion is 1.5 times of the original
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
If (newcapacity - max_array_size > 0) max int max - 8
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
2. Common methods
- Add an element to the specified location (the specified location is less than or equal to alist.size()) alist.add(1, "D");
- Determines whether the specified element exists in the collection alist.contains("a");
- Specifies where the element first appears in the collection alist.indexOf("b");
- Specifies where the element last appeared alist.lastIndexOf("b");
- Determine whether the collection is empty alist.isEmpty();
- Deletes the element at the specified location alist.remove(2);
- Deletes the specified element alist.remove("a");
- Replace the specified index with the specified element alist.set(3, "F");
- Gets the contents of the specified index alist.get(2));
- Length of collection size alist.size();
- Set to array String[] str = alist.toArray(new String[alist.size()]);
public class Demo {
public static void main(String[] args) {
// ArrayList<String> alist = new ArrayList();
ArrayList<String> alist = new ArrayList<String>(9);
alist.add("a");
alist.add("b");
alist.add("c");
alist.add("d");
alist.add("b");
alist.add("a");
System.out.println(alist);//[a, b, c, d, b, a]
//Add content to the specified location
alist.add(1, "D");
System.out.println(alist);//[a, D, b, c, d, b, a]
//Determines whether the specified element exists in the collection
System.out.println(alist.contains("a"));//true
//Specifies where the element first appears in the collection
System.out.println(alist.indexOf("b"));//2
//Specifies where the element last appeared
System.out.println(alist.lastIndexOf("b"));//5
// Determine whether the collection is empty
System.out.println(alist.isEmpty());//false
//Deletes the element at the specified location
alist.remove(2);
System.out.println(alist);//[a, D, c, d, b, a]
//Deletes the specified element
alist.remove("a");
System.out.println(alist);//[D, c, d, b, a]
//Replace the specified index with the specified element
alist.set(3, "F");
System.out.println(alist);//[D, c, d, F, a]
//Gets the contents of the specified index
System.out.println(alist.get(2));//d
//Length of collection size
System.out.println(alist.size());//5
System.out.println(alist);//[D, c, d, F, a]
//Set to array
String[] str = alist.toArray(new String[alist.size()]);
System.out.println(Arrays.toString(str));//[D, c, d, F, a]
}
}3. Removelange() method
Deletes the collection element of the specified interval
public class MyArrayList<E> extends ArrayList{
public static void main(String[] args) {
MyArrayList<String> alist = new MyArrayList<String>();
alist.removeRange(0, 5);//Protected methods are accessed in different subclasses
}
}
4. Comparator
(1) new + interface () An anonymous inner class object is created, and the Comparator passes a Comparator.
alist.sort(new Comparator<User>() {
@Override
public int compare(User o1, User o2) {
return o1.getId() - o2.getId();
}
});(2) Custom comparator (example: user comparator)
//User class
public class User {
private int id;
private String name;
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
@Override
public String toString() {
return "Usre{" +
"id=" + id +
", name='" + name + '\'' +
'}';
}
public User(int id, String name) {
this.id = id;
this.name = name;
}
}
import java.util.Comparator;
//User comparator:
public class UserComparator<U> implements Comparator<User>{
@Override
public int compare(User o1,User o2) {
return o1.getId() - o2.getId();
}
}
//Test class
public class Test {
public static void main(String[] args) {
ArrayList<User> alist = new ArrayList<>();
User user1 = new User(1,"Zhang San 1");
User user2 = new User(2,"Zhang San 2");
User user3 = new User(3,"Zhang San 3");
User user4 = new User(4,"Zhang San 4");
User user5 = new User(5,"Zhang San 5");
alist.add(user5);
alist.add(user3);
alist.add(user1);
alist.add(user4);
alist.add(user2);
//The new + interface () creates an anonymous inner class object, and the Comparator passes a Comparator
/* alist.sort(new Comparator<User>() {
@Override
public int compare(User o1, User o2) {
return o1.getId() - o2.getId();
}
});*/
alist.sort(new UserComparator());
}
}
2. LinkedList
Features: store duplicate elements and discharge them in the order of addition
Create: LinkedList < string > llist = new LinkedList < > ();
Node node E item; data Node<E> next; Rear pointer Node<E> prev; Front pointer
Source code:
Node<E> node(int index) {
// assert isElementIndex(index);
If (index < (size > > 1)) {/ / if the index is less than half the length, look back from the beginning node
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
}else {/ / look forward from the tail node
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
3. Vorter
The bottom layer is also an array implementation, which is thread safe (using synchronous lock), and the method is similar to ArrayList.
Source code:
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
establish:
Vector<String> v = new Vector<String>();
4. Traversal of list set (ArrayLIst as an example)
1. for loop
Support to delete elements in the collection during traversal operation. Pay attention to all changes (array out of bounds will occur)
import java.util.ArrayList;
public class Demo {
public static void main(String[] args) {
ArrayList<String> alist = new ArrayList<>();
alist.add("a");
alist.add("b");
alist.add("c");
alist.add("d");
alist.add("a");
alist.add("a");
/*
First: for loop
Support to delete elements in the collection during traversal operation. Pay attention to all changes (array out of bounds will occur)
*/
for (int i = 0; i < alist.size(); i++) {
System.out.print(alist.get(i) + " ");
}
System.out.println();//a b c d a a
}
}
2. Enhanced for loop
It is not supported to delete the elements in the collection when traversing the collection, otherwise a concurrent modification exception will be thrown
(concurrentModificationException)
Note: only one deletion is allowed. Use break to end the cycle at the same time
import java.util.ArrayList;
public class Demo {
public static void main(String[] args) {
ArrayList<String> alist = new ArrayList<>();
alist.add("a");
alist.add("b");
alist.add("c");
alist.add("d");
alist.add("a");
alist.add("a");
/*
The second is to enhance the for loop
It is not supported to delete the elements in the collection when traversing the collection, otherwise a concurrent modification exception will be thrown
(concurrentModificationException)
*/
for (String item: alist
) {
System.out.print(item);
}
}
}
3. Iterator
1. Call Iterator() to return an iterator object
package javacollection.day3;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.ListIterator;
public class Demo1 {
public static void main(String[] args) {
ArrayList<String> alist = new ArrayList<>();
alist.add("a");
alist.add("b");
alist.add("c");
alist.add("d");
alist.add("a");
alist.add("a");
/*
The third type: iterator
Iterator<E>(Traversal from front to back (delete operation) and listiterator < E >
(Traversal (deletion) from back to front
*/
Iterator<String> it = alist.iterator();
//Call the Iterator() method to return an iterator object
while (it.hasNext()){
String its = it.next();
if(its.equals("a")){
it.remove();//Deletes the element specified by the current pointer
}
}
System.out.println(alist);//[b, c, d]
ListIterator<String> iter = alist.listIterator(alist.size());
//Given the length of the set, the elements in the set are output in reverse order. The ListIterator can only traverse the set under the List interface
while (iter.hasPrevious()){
String its = iter.previous();
if(its.equals("b")){
iter.remove();
}
}
System.out.println(alist);//[c, d]
}
}
two Given the length of the set, the elements in the set are output in reverse order. The ListIterator can only traverse the set under the List interface
package javacollection.day3;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.ListIterator;
public class Demo1 {
public static void main(String[] args) {
ArrayList<String> alist = new ArrayList<>();
alist.add("a");
alist.add("b");
alist.add("c");
alist.add("d");
alist.add("a");
alist.add("a");
ListIterator<String> iter = alist.listIterator(alist.size());
//Given the length of the set, the elements in the set are output in reverse order. The ListIterator can only traverse the set under the List interface
while (iter.hasPrevious()){
String its = iter.previous();
if(its.equals("b")){
iter.remove();
}
}
System.out.println(alist);//[a, c, d, a, a]
}
}