Three common implementation classes of Java List interface

List three common sets

ArrayList (key)

ArrayList is a typical implementation class and main implementation class of the List interface. In essence, ArrayList is a "variable length" array of object references.

summary

  • ArrayList class is an array that can be dynamically modified. The difference from ordinary arrays is that it has no fixed size limit. We can add or delete elements.

  • ArrayList inherits AbstractList, which is a subclass of the List interface. AbstractList is an abstract class, adapter design pattern.

  • ArrayList is a subclass of the List interface. This class is defined as follows:

public class ArrayList<E> extends AbstractList<E>
                implements List<E>, RandomAccess, Cloneable, Serializable

Jdk 1.8 and 1.7

Jdk1 of ArrayList 8. What is the difference between the previous and subsequent implementations?

  • JDK1.7: ArrayList is like a hungry man. It directly creates an array with an initial capacity of 10
  • JDK1.8: ArrayList is like a lazy man. At the beginning, create an array with a length of 0. When the first element is added for the first time, create an array with a starting capacity of 10. If a group of elements are added and the number of elements is large, create an array with just enough storage capacity.

common method

Add element

  • The add method of ArrayList is overloaded and can be added according to the index value. The elements behind the original index value are moved one bit to the right
import java.util.ArrayList;
import java.util.List;
public class ArrayListDemo01 {
    public static void main(String[] args) {
        // Instantiate the List object and specify the generic type
        List<String> all = new ArrayList<String>(); 
        // Add content. This method inherits from the Collection interface
        all.add("hello "); 
       // Add content. This method is defined separately by the List interface 
       all.add(0, "LAMP ");
       // Add content. This method inherits from the Collection interface
       all.add("world"); 
       // Print the all object and call the toString() method
       System.out.println(all); 
    }
}

Output results

[LAMP , hello , world]

The above operations add three elements to the collection, and the operations added at the specified position are separately defined by the List interface. When outputting later, the toString() method is actually called to complete the output.

It can be found that there is no limit on the length of the object array at this time. The length can be as long as the memory is large enough.

Delete element

  • The delete element method deletes several elements and outputs them in a circular manner.
  • Only the List interface is defined according to the method of fetching the content from the specified location, and no other interface has any definition.
import java.util.ArrayList;
import java.util.List;
public class ArrayListDemo02 {
    public static void main(String[] args) {
        List<String> all = new ArrayList<String>(); // Instantiate the List object and specify the generic type
        all.add("hello "); // Add content. This method inherits from the Collection interface
        all.add(0, "LAMP ");// Add content. This method is defined separately by the List interface
        all.add("world"); // Add content. This method inherits from the Collection interface
        all.remove(1); // Delete content according to the index. This method is defined separately by the List interface
        all.remove("world");// Deletes the specified object
        System.out.print("The contents of the collection are:");
        for (int x = 0; x < all.size(); x++) { // The size() method inherits from the Collection interface
            System.out.print(all.get(x) + ","); // This method is defined separately by the List interface
        }
    }
}

Operation results

The contents of the collection are: LAMP ,

Access element

import java.util.ArrayList;

public class RunoobTest {
    public static void main(String[] args) {
        ArrayList<String> sites = new ArrayList<String>();
        sites.add("Google");
        sites.add("Runoob");
        sites.add("Taobao");
        sites.add("Weibo");
        System.out.println(sites.get(1));  // Access the second element
    }
}

Output results

Runoob

Modify element

import java.util.ArrayList;

public class RunoobTest {
    public static void main(String[] args) {
        ArrayList<String> sites = new ArrayList<String>();
        sites.add("Google");
        sites.add("Runoob");
        sites.add("Taobao");
        sites.add("Weibo");
        sites.set(2, "Wiki"); // The first parameter is the index position and the second is the value to be modified
        System.out.println(sites);
    }
}

Output results

[Google, Runoob, Wiki, Weibo]

Traversal set

  • Iterator traversal (two types)
    • iterator
    • listIterator
  • for loop traversal (two types)
    • For (int i = 0; I < set. length; i + +)
    • for(Object o: Set)

Focus (vector 2.3)

Vector overview

Vector is a veteran class of Java. It is the earliest operation class that provides dynamic object array. It has been used since JDK 1.0, but later the Java class collection framework was introduced after JDK 1.2. However, in order to take care of many users who are used to using vector, the vector class has been upgraded after JDK 1.2 to implement an additional List interface, so that this class can continue to be retained.

characteristic

Like ArrayList, Vector itself is a subclass of the List interface. This class is defined as follows:

public class Vector<E> extends AbstractList<E>
                implements List<E>, RandomAccess, Cloneable, Serializable
  • Like the ArrayList class, this class is a subclass of AbstractList. Therefore, as long as the operation is a subclass of the List interface, it will operate according to the List.

  • Vector is an ancient collection, jdk1 0. Most operations are the same as ArrayList, except that vector is thread safe.

  • Among various list s, it is best to take ArrayList as the default choice. Use LinkedList when inserting and deleting frequently; Vector is always slower than ArrayList, so try to avoid using it.

Examples

import java.util.List;
import java.util.Vector;
public class VectorDemo01 {
    public static void main(String[] args) {
        List<String> all = new Vector<String>(); // Instantiate the List object and specify the generic type
        all.add("hello "); // Add content. This method inherits from the Collection interface
        all.add(0, "LAMP ");// Add content. This method is defined separately by the List interface
        all.add("world"); // Add content. This method inherits from the Collection interface
        all.remove(1); // Delete content according to the index. This method is defined separately by the List interface
        all.remove("world");// Deletes the specified object
        System.out.print("The contents of the collection are:");
        for (int x = 0; x < all.size(); x++) { // The size() method inherits from the Collection interface
            System.out.print(all.get(x) + ","); // This method is defined separately by the List interface
        }
    }
}

The above operation results are no different from using ArrayList itself. Because the operation takes the interface as the operation standard.

‚Äč

LinkedList (understanding)

LinkedList overview

  1. This class inherits AbstractList, so it is a subclass of List. However, this class is also a subclass of the Queue interface, which defines the following methods:
public class LinkedList<E> extends AbstractSequentialList<E>
                    implements List<E>, Deque<E>, Cloneable, Serializable

  1. LinkedList is a two-way linked list. It does not declare an array inside, but defines the first and last of Node type, which are used to record the first and last elements. At the same time, the internal class Node is defined as the basic structure for saving data in the LinkedList. In addition to saving data, Node also defines two variables:
  • The prev variable records the position of the previous element

  • The next variable records the position of the next element

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

Example: verify LinkedList subclass

import java.util.LinkedList;
import java.util.Queue;
public class TestDemo {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<String>();
        queue.add("A");
        queue.add("B");
        queue.add("C");
        //Take out the size of the queue first, otherwise every time you remove an element, there will be one less element, then the queue Size () is getting smaller, so you can't loop queue Size () times.
        int len=queue.size();
        for (int x = 0; x <len; x++) {
            System.out.println(queue.poll());
        }
        System.out.println(queue);
    }
}

Common interview questions

  1. The difference between Vector class and ArrayList class

Although these two classes are subclasses of the List interface, they have the following differences in use:

  1. What are the similarities and differences between ArrayList/LinkedList/Vector? Talk about your understanding? What is the bottom layer of ArrayList? Capacity expansion mechanism? What is the biggest difference between Vector and ArrayList?
  • Similarities and differences between ArrayList and LinkedList

    Both are thread unsafe. Compared with thread safe Vector, the execution efficiency is high. ArrayList is a data structure based on dynamic array, and LinkedList is a data structure based on linked list. For random access to get and set, ArrayList feels better than LinkedList because LinkedList moves the pointer. LinkedList has an advantage over add and remove operations, because ArrayList moves data.

  • The difference between ArrayList and Vector

    Vector and ArrayList are almost identical. The only difference is that vector is a synchronized class and belongs to a strongly synchronized class. Therefore, the overhead is larger and the access is slower than ArrayList. Under normal circumstances, most Java programmers use ArrayList instead of vector, because synchronization can be completely controlled by the programmer himself.

  • Capacity expansion mechanism

    Vector requests twice its size for each expansion, while ArrayList is 1.5 times. Vector also has a subclass Stack.

Tags: Java data structure linked list

Posted by techcone on Sun, 22 May 2022 10:18:32 +0300