How to define and implement ArrayList and sequence list in Java

1. Linear table

Definition

Linear table is the most basic, simplest, and most commonly used data structure. A finite sequence, which contains n data elements with the same characteristics, is called a linear list and is a type of data structure.

Common linear lists: sequential lists, linked lists, stacks, queues...

Linear lists are logically linear structures, that is to say, they are a continuous straight line. The physical storage form of linear tables is usually an array or linked list structure, but it is not necessarily continuous.

Features

• #There must be only one "first element" in the set.

• There must be only one "last element" in the set.

• Except for the last element, all elements have a unique successor (successor).

• Except for the first element, all elements have a unique predecessor (antecedent).

2. Sequence table

Definition

The linear structure usually stored in the form of an array is called a sequence table, which stores data elements in sequence in a physical in memory cells with consecutive addresses. Complete the addition, deletion, checking and modification of data on the array.

Implementation

First we need to create an array to store data.

Note: Because I created the integer array first for convenience, in order to better adapt to various types, you can create a generic array, which I don’t have here. wrote.

The next step is to perform various operations on the sequence table. For example: basic CURD, print sequence table, get sequence table length, clear sequence table, etc.

Print array

Because it is an array, just traverse the array and print it directly

Add new elements

When adding elements, it is necessary to consider whether the array is full, so we need to make a judgment. If the array space is full, it needs to be expanded. In addition, we also need to determine whether this pos position is legal.

Method to determine whether the space is full

Here we simplify the code as:

If you want In the case of expansion, after the expansion is completed, because the sequence list is a continuous structure, if a new element is added at the pos position, the elements after the pos position will be moved back in sequence. Only in this way can new elements be added.

Note: After expansion, we need to change the size of CAPACITY and usedSize.

Determine whether a certain element is contained

Here we need to consider whether the array is empty at this time.

After that, it is still a direct traversal of the array.

Finding elements

A null operation is also required here.

Get the element at pos position

There may be situations where the array is empty and pos is illegal, so judgment is required.

I am manually throwing exceptions here, and I have not written anything else.

Change the value of pos position

Delete operation

Delete an element at a certain position , you can directly let the elements behind it cover it to achieve deletion.

Get the sequence table length

Clear the sequence table

The following operations are relatively simple and will not be described in detail.

3. ArrayList

Introduction:

In the collection framework, ArrayList is an ordinary class that implements the List interface. The specific framework diagram is as follows:

[Explanation]

1. ArrayList implements the RandomAccess interface, indicating that ArrayList supports random access.

2. ArrayList implements the Cloneable interface, indicating that ArrayList can be cloned.

3. ArrayList implements the Serializable interface, indicating that ArrayList supports serialization.

4. Unlike Vector, ArrayList is not thread-safe and can be used in a single thread. In multi-threads, you can choose Vector or CopyOnWriteArrayList.

5. The bottom layer of ArrayList is a continuous space and can be dynamically expanded. It is a dynamic type sequence list.

Using

 public static void main(String[] args) {
        // ArrayList创建，推荐写法
        // 构造一个空的列表
        List<Integer> list1 = new ArrayList<>();
 
        // 构造一个具有10个容量的列表
        List<Integer> list2 = new ArrayList<>(10);
        list2.add(1);
        list2.add(2);
        list2.add(3);
 
        // list2.add("hello"); // 编译失败，List<Integer>已经限定了，list2中只能存储整形元素
        // list3构造好之后，与list中的元素一致
        ArrayList<Integer> list3 = new ArrayList<>(list2);
 
        // 避免省略类型，否则：任意类型的元素都可以存放，使用时将是一场灾难
        List list4 = new ArrayList();
        list4.add("111");
        list4.add(100);
    }

Some common methods

Method	Explanation
boolean add(E e)	End insert e
void add(int index, E element)	will e is inserted into the index position
boolean addAll(Collection extends E> c)	Insert the end of the elements in collection c into the collection
E remove(int index)	Remove the index position element and return
boolean remove(Object o)	Delete the first o
E get(int index)	Get the subscript index position element
E set(int index, E element)	Set the subscript index position element to element
void clear()	Clear the sequence table
boolean contains(Object o)	Judge whether o is in the linear table
int indexOf(Object o)	Return the subscript of the first o
int lastIndexOf(Object o)	Return the subscript of the last o
List subList(int fromIndex, int toIndex)	Interception of part of the list

## ArrayList traversal

Loop traversal

foreach traversal

##Iterator

        System.out.println("======迭代器1=========");
 
        ElementObservableListDecorator<Object> list;
        Iterator<String> it =  list.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
        System.out.println("======迭代器2=========");
        ListIterator<String> it2 =  list.listIterator();
        while (it2.hasNext()) {
            System.out.println(it2.next());
        }

Sequence table and The difference between arrays:

As mentioned above, the bottom layer of the sequence table can be understood as an array, but it is more advanced than an array.

The sequence table can expand by itself;

The sequence table strictly distinguishes between the array capacity and the number of elements.

So an array is actually an incomplete sequence list.

Notes in the sequence table:

We need to distinguish between two concepts in the sequence table: capacity and the number of elements (size).
Capacity can be understood as the size (length) of the array, and the number of elements is the number of valid elements recorded in size.
In a sequence table, data storage needs to be continuous, and there cannot be "gaps" between elements. When operations such as insertion and deletion are performed, after the operation is completed, Ensure the continuity of the sequence list.

The above is the detailed content of How to define and implement ArrayList and sequence list in Java. For more information, please follow other related articles on the PHP Chinese website!