The difference between Arraylist and Vector
Vector is a collection type in jdk earlier. It is not used much in development now, so there is no need to study too much. ArrayList is completely an alternative to arrays. Most of the commonly used methods are almost the same as those in the list interface and collection interface implemented directly or indirectly.
ArrayList
Vector difference
Similarities:
1. The bottom layer uses arrays for data storage Object []
2. Have a common father AbstractList All implement the interface list
difference:
1. When creating an object, ArrayList does not open up space for the underlying array bottom
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
Vector creates an array with a length of 10 for the underlying object
public Vector() {
this(10);
}and ArrayList opens up space for the underlying array when adding objects, with a length of 10
private static final int DEFAULT_CAPACITY = 10;
2: Different expansion rules
The capacity of ArrayList is expanded to 1.5 times the original capacity
int newCapacity = oldCapacity + (oldCapacity >> 1);
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
Vector
int oldCapacity = elementData.length;//10
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?capacityIncrement : oldCapacity);
capacityIncrement: the capacity addition / growth factor is specified when the object is created
The stretch factor can be set in the constructor when creating an object( new Vector<>(30,40);)
If capacityincrement < = 0 Expand capacity to twice the original
If capacityincrement > 0 Expand to oldCapacity+capacityIncrement
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}3. Thread safety issues
Vector thread safe Low efficiency
ArrayList thread is unsafe efficient
4. Version problem
ArrayList 1.2
Vector 1.0
LinkedList: bidirectional linked list bidirectional circular linked list
public class LinkedListTest {
/*
LinkedList New method compared to List
*/
@Test
public void test02(){
//Object creation completed
LinkedList<String> list = new LinkedList<>();
list.add("Zhang San");
list.add("Li Si");
list.add("Wang Wu");
System.out.println(list);//[Zhang San, Li Si, Wang Wu]
System.out.println("list.getFirst() = " + list.getFirst());
System.out.println("list.getLast() = " + list.getLast());
list.addFirst("Angela");
list.addLast("Ying Zheng");
System.out.println(list);//[Angela, Zhang San, Li Si, Wang Wu, Ying Zheng]
list.removeFirst();
System.out.println(list);//[Zhang San, Li Si, Wang Wu, Ying Zheng]
list.removeLast();
System.out.println(list);//[Zhang San, Li Si, Wang Wu]
}
@Test
public void test01(){
//Object creation completed
LinkedList<String> list = new LinkedList<>();
list.add("Zhang San");
list.add("Li Si");
list.add("Wang Wu");
}
}
Member variables in the LinkedList class
length And maintain the front and back nodes to make them orderly
transient int size = 0;
transient Node<E> first;
transient Node<E> last;The Node class belongs to the member inner class of the LinkedList class
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;
}
}It's best to use the address value when drawing. Don't always use the arrow, otherwise the direction will be unclear
LinkedList new method compared with List
Analysis: the underlying layer of linkedlist uses a two-way linked list for storage, so the new methods are also related to the linked list (in addition, the two-way linked list increases and deletes quickly, but the query and change are slower than the array, so when using it, choose whether to use ArrayList or linkedlist according to different application scenarios)
increase addFirst(ele) addLast(ele);
Delete removeFirst() removeLast();
change
check getFirst() getLast()
Method of simulating stack and queue peek() poll()
push() pop() peek()
Stack:
FILO first in last out
Brush plate
Stack: adds elements to the stack
Out of stack: pop up the top element of the stack
Both stack entry and stack exit are [relative] to the top element of the stack
Queue: (queue an exit deque (method of accessing elements at both ends of two exit double ended queue)
Team head deletion
Add at the end of the queue
Deque simulation stack (the order of printing is from the top of the stack to the bottom of the stack (more image)
@Test
public void test01(){
Deque<String> stack = new LinkedList<>();
//When entering or leaving the stack, it is reversed
stack.push("001");
stack.push("002");
stack.push("003");
stack.push("004");
stack.push("005");
System.out.println("stack = " + stack);
//Bomb stack
String pop1 = stack.pop();
System.out.println("pop1 = " + pop1);
//Get stack top element
String peek = stack.peek();
System.out.println("peek = " + peek);
}
There is a stack class, but both queue and deque are interfaces
Test of Stack class (same code) The order of printing is in the order of addition
public void test02(){
Stack<String> stack = new Stack<>();
stack.push("001");
stack.push("002");
stack.push("003");
stack.push("004");
stack.push("005");
System.out.println("stack = " + stack);
//Bomb stack
String pop1 = stack.pop();
System.out.println("pop1 = " + pop1);
//Get stack top element
String peek = stack.peek();
System.out.println("peek = " + peek);
}
LinkedList simulation queue
@Test
public void test03(){
Queue<String> queue = new LinkedList<>();
queue.add("001");
queue.add("002");
queue.add("003");
queue.add("004");
queue.add("005");
System.out.println("queue = " + queue);
/* queue.remove();
queue.remove();
queue.remove();
queue.remove();
queue.remove();
System.out.println("queue = " + queue);*/
/*queue.poll();
queue.poll();
queue.poll();
queue.poll();
queue.poll();
System.out.println("queue = " + queue);*/
String peek = queue.peek();
System.out.println("peek = " + peek);
}
@Test
public void test02(){
Stack<String> stack = new Stack<>();
stack.push("001");
stack.push("002");
stack.push("003");
stack.push("004");
stack.push("005");
System.out.println("stack = " + stack);
//Bomb stack
String pop1 = stack.pop();
System.out.println("pop1 = " + pop1);
//Get stack top element
String peek = stack.peek();
System.out.println("peek = " + peek);
}