arrayList ＆＆ linkedList

A long time ago, I wrote an article about two list Performance articles Performance comparison test
This article goes back to the bottom , Let's take a look at two list.

One 、List Interface

1） characteristic ：

Orderly 、 With subscript 、 Elements can be repeated .

2） A unique method of manipulating collections based on element indexes

List As Collection Sub interface of collection , Not only did they inherit Collection All methods in the interface , In addition, some operations based on element index are added
A unique way to make a collection , as follows ：

• public void add(int index, E element) : Will specify the element , Add to the specified location in the collection .
• public E get(int index) : Returns the element at the specified location in the collection .
• public E remove(int index) : Remove the element at the specified location in the list , What is returned is the removed element .
• public E set(int index, E element) : Replace the element at the specified location in the collection with the specified element , Returns the pre update element of the value .
  List Collection specific methods are all index related

Two 、ArrayList

1） characteristic

Slow addition and deletion of elements , Quick search , Because the most commonly used functions in daily development are
Query data 、 Traversal data , therefore ArrayList Is the most commonly used set .

2） Storage structure

Using array implementation .

• The reason of fast query ：
  An array is a continuous space , You can find the array through the first address , Through the index , You can find an element in the array .
• The reason for the slow addition and deletion ：
  The length of the array is fixed , When we want to add or delete an array , You must create a new array , Copy the data of the original array . For example, the following delete operations ：
  We need to delete an element , A new array needs to be created , Length is original array -1, Copy other elements of the original array to the new array , Assign the address of the new array to the variable arr, The original array is destroyed , Garbage collection .
  

3） Advantages and disadvantages

advantage ： Query data 、 Traversing data is very efficient . It uses indexes to quickly locate objects .
shortcoming ： Is to insert or delete elements relative to LinkedList slower . Because the array is used , You need to move the following elements to adjust the order of the index .

4） Something to watch out for

In heap memory , Create and destroy arrays frequently , Copy the elements in the array , inefficiency , If there is a similar scene , You can consider LinkedList.

3、 ... and 、LinkedList

1） What is a linked list ？

A linked list is a physical storage unit that is discontinuous 、 Nonsequential storage structure

• Single chain list
• Double linked list
• Circular linked list

2） Storage structure

Chain table structure , Convenient elements add 、 Deleted sets , Access traversal is relative to ArrayList slower .
And it is a two-way linked list .

In actual development, the addition and deletion of a set element often involves the first and last operations , and LinkedList There are a lot of ways to start and end operations . These parties
Just let us know ：

• public void addFirst(E e) : Inserts the specified element at the beginning of this list .
• public void addLast(E e) : Add the specified element to the end of this list .
• public E getFirst() : Returns the first element of this list .
• public E getLast() : Return the last element of this list .
• public E removeFirst() : Remove and return the first element of this list .
• public E removeLast() : Remove and return the last element of this list .
• public E pop() : Pop an element from the stack represented by this list .
• public void push(E e) : Push elements onto the stack represented by this list .
• public boolean isEmpty() ： If the list does not contain elements , Then return to true.