1. ArrayList
1.ArrayListIntroduction
In the collection framework, ArrayList is an ordinary class that implements the List interface. The specific framework diagram is as follows:
【
Description]
1. ArrayList is implemented in a generic manner and must be instantiated before use.
2. ArrayList implements the RandomAccess interface, indicating that ArrayList supports random access
3. ArrayList implements the Cloneable interface, indicating that ArrayList can be cloned
4. ArrayList implements the Serializable interface, indicating that ArrayList supports serialization.
5. Unlike Vector, ArrayList is not thread-safe and can be used in a single thread. In multi-threads, you can choose Vector or CopyOnWriteArrayList.
6. The bottom layer of ArrayList is a continuous space and can be dynamically expanded. It is a dynamic type sequence list.
2. Sequence table
The sequence table is a paragraph
Storage units with continuous physical addresses store the linear structure of data elements in sequence, and generally use array storage. Complete the addition, deletion, checking and modification of data on the array.
3.ArrayList expansion mechanism
Interception of ArrayList source code
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
// Get the old space size
int oldCapacity = elementData.length;
// Expected to expand capacity by 1.5 times
int newCapacity = oldCapacity + (oldCapacity >> 1);
// If the user needs to expand the capacity by more than 1.5 times the original space, expand the capacity according to the size required by the user.
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// If the required expansion size exceeds MAX_ARRAY_SIZE, recalculate the capacity size
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// Call copyOf to expand the capacity
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
// If minCapacity is less than 0, throw OutOfMemoryError exception
if (minCapacity < 0)
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
【
Summary]
1. Check whether expansion is really needed, and if so, call grow to prepare for expansion.
2. Estimate the required storage capacity
Preliminary estimate is to expand the capacity by 1.5 times.
If the size required by the user exceeds 1.5 times the estimated size, the capacity will be expanded according to the size required by the user.
Before actual expansion, check whether the expansion can be successful to prevent the expansion from being too large and causing the expansion to fail.
3. Use copyOf for expansion
4.Defects of ArrayList
Since the bottom layer is a continuous space, when
at
ArrayList
When inserting or deleting elements at any position, you need to move the subsequent elements forward or backward
Moving, the time complexity is
O(n), the efficiency is relatively low, so
ArrayList
Not suitable for scenarios where there are a lot of insertions and deletions at any location. Therefore: LinkedList, the linked list structure, is introduced in java collections.
2. LinkedList
LInkedList is essentially a linked list! ! !
2.1 The concept and structure of linked lists
The linked list is a physically non-contiguous storage structure. The logical sequence of the data elements is through the reference links< in the linked list. /strong>Achieved sequentially.
2.2 What isLinkedList
The bottom layer of LinkedList is a doubly linked list structure (described later on the linked list). Since the linked list does not store elements in a continuous space, the elements are stored in separate nodes, and then the nodes are connected through references, so inserting or deleting at any position When using elements, there is no need to move the elements, so the efficiency is relatively high.
【illustrate】
1. LinkedList implements the List interface
2. The underlying layer of LinkedList uses a doubly linked list
3. LinkedList does not implement the RandomAccess interface, so LinkedList does not support random access.
4. Inserting and deleting elements at any position in LinkedList is relatively efficient, and the time complexity is O(1)
5. LinkedList is more suitable for any position
2.3 LinkedList simulation implementation
public class MyLinkedList {
static class ListNode {
public int val;
ListNode prev;
ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public ListNode head;
public ListNode last;
//Header insertion method O(1)
public void addFirst(int data){
ListNode node = new ListNode(data);
if (head == null) {
head = node;
last = node;
}else {
node.next = head;
head.prev = node;
head = node;
}
}
//Tail insertion method O(1)
public void addLast(int data){
ListNode node = new ListNode(data);
if (head == null) {
head = node;
last = node;
}else {
last.next = node;
node.prev = last;
last = node;
}
}
//Insert at any position, the first data node is subscript 0
public void addIndex(int index,int data){
if (index < 0 || index >size()) {
throw new CheckOutOfException("The position is legal");
//return;
}
if (index == 0) {
addFirst(data);
return;
}
if (index == size()) {
addLast(data);
return;
}
ListNode cur = findIndex(index);
ListNode node = new ListNode(data);
node.next = cur;
cur.prev.next = node;
node.prev = cur.prev;
cur.prev = node;
}
public ListNode findIndex(int index) {
ListNode cur = head;
while (index != 0) {
cur = cur.next;
index--;
}
return cur;
}
//Find whether it contains the keyword key and whether it is in the linked list
public boolean contains(int key){
ListNode cur = head;
while (cur != null) {
if (cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
//Delete the node where the keyword is key for the first time
public void remove(int key){
ListNode cur = head;
while (cur != null) {
if (cur.val == key) {
//1. Delete the head node
if (cur == head) {
head = head.next;
//Process only one node
if (head != null) {
head.prev = null;
}
}else {
//middle tail
cur.prev.next = cur.next;
//Not a tail node
if (cur.next != null) {
cur.next.prev = cur.prev;
}else {
//It is the tail node
last = cur.prev;
}
}
return;
}
cur = cur.next;
}
}
//Delete all nodes whose value is key O(n)
public void removeAllKey(int key){
ListNode cur = head;
while (cur != null) {
if (cur.val == key) {
//1. Delete the head node
if (cur == head) {
head = head.next;
//Process only one node
if (head != null) {
head.prev = null;
}
}else {
//middle tail
cur.prev.next = cur.next;
//Not a tail node
if (cur.next != null) {
cur.next.prev = cur.prev;
}else {
//It is the tail node
last = cur.prev;
}
}
}
cur = cur.next;
}
}
//Get the length of the linked list
public int size(){
int len = 0;
ListNode cur = head;
while (cur != null) {
len + + ;
cur = cur.next;
}
return len;
}
//print linked list
public void display(){
ListNode cur = head;
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println();
}
}
Summarize:
| Differences | ArrayList | LinkedList |
| In storage space | It must be physically continuous | Logically continuous, but not necessarily physically continuous |
| Random access | Support O(1) | Not support: O(N) |
| Header plug | Needs to move elements, low efficiency O(N) | Just modify Reference pointer, time complexity O(1) |
|
insert |
When there is not enough space, expansion is needed | There is no concept of expansion |
| Application scenarios | Efficient storage of elements + frequent questions | Frequent insertion and deletion at any position |
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 56875 people are learning the system