Technology Sharing

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Linear table

We are going to talkSequence table, we have to talk about linear lists first, because sequential lists are a type of linear lists.

Definition of Linear Table

As the name suggests, a linear table is a table that organizes data like a line.
You can understand it by associating it with queuing in real life.

Characteristics of linear lists:

• There is an order between the data elements of a linear list.
• Except for the first and last elements, every element has a predecessor and successor.

Sequence table

The sequence table is aPhysical address contiguousThe storage units are like people standing in line.
A linear structure that stores data elements sequentially, usually usingArraysstorage.
Complete the addition, deletion, query and modification of data in the array.

Implementation of Sequence Table Interface

Implement a sequence table (storing int type data) by yourself, and use the sequence table as a class. We implement some interfaces, namely someMember MethodsTo realize the addition, deletion, query and modification of data.

public class SeqList {
     private int[] elem;
     private int usedSize;
     // 默认构造方法
     SeqList(){   }
     // 将顺序表的底层容量设置为initcapacity
     SeqList(int initcapacity){   }
     // 新增元素,默认在数组最后新增
     public void add(int data) { }
     // 在 pos 位置新增元素
     public void add(int pos, int data) { }
     // 判定是否包含某个元素
     public boolean contains(int toFind) { return true; }
     // 查找某个元素对应的位置
     public int indexOf(int toFind) { return -1; }
     // 获取 pos 位置的元素
     public int get(int pos) { return -1; }
     // 给 pos 位置的元素设为 value
     public void set(int pos, int value) {   }
     //删除第一次出现的关键字key
     public void remove(int toRemove) {   }
     // 获取顺序表长度
     public int size() { return 0; }
     // 清空顺序表
     public void clear() {   }
     
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

Default Constructor

By default, we initially open up 10 spaces for data.

private static final int DEFAULT_SIZE = 10;
    public SeqList() {
        this.elem= new int[DEFAULT_SIZE];
    }
1
2
3
4

Set the underlying capacity of the sequence table to initcapacity

Pass in the array length and use the array length to allocate space.

private static final int DEFAULT_SIZE = 10;
    public SeqList(int initcapacity) {
        this.elem= new int[initcapacity];
    }
1
2
3
4

Tail plug

Add new elements, which are added at the end of the array by default.
Points to consider:

• Check whether the current sequence list is full. If it is full, add space.
• An element is added and usedSize increases by 1.

 public void add(int data) {
        if(isFull()){
            elem = Arrays.copyOf(elem,elem.length * 2);
        }
        elem[usedSize++] = data;
    }
     /**
     * 判断当前的顺序表是不是满的！
     *
     * @return true:满   false代表空
     */
    private boolean isFull() {
        return usedSize == elem.length;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

Add an element at position pos

Insert element at index pos.
Precautions:

• Check whether the current sequence list is full. If it is full, add space.
• Check if the given pos position is legal. If not, throw an exception.
• Use a back-to-front loop to move the element after position pos backwards.
• An element is added and usedSize increases by 1.

private boolean checkPosInAdd(int pos) throws PosIllegalException{

        if(pos < 0 || pos > usedSize){
            throw new PosIllegalException("位置不合法");
        }
        return true;
    }

    // 在 pos 位置新增元素
    public void add(int pos, int data) {
        try{
            if(checkPosInAdd(pos)){
                if(isFull()){
                    elem = Arrays.copyOf(elem,elem.length * 2);
                }
                for (int i = usedSize; i > pos ; i--) {
                    elem[i] = elem[i-1];
                }
                elem[pos] = data;
                usedSize++;
            }
        }catch(PosIllegalException e){
            e.printStackTrace();
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

Determine whether an element is contained

Check whether the given data is contained in the sequence table.
Just loop through it and return true if found, otherwise return false.

public boolean contains(int toFind) {
        for (int i = 0; i < usedSize; i++) {
            if(elem[i] == toFind){
                return true;
            }
        }
        return false;
    }
1
2
3
4
5
6
7
8

Find the position corresponding to an element

Look at the subscripts of the given data in this sequence table.
Just loop through it and find the return index, if not, return -1.

public int indexOf(int toFind) {
        for (int i = 0; i < usedSize; i++) {
            if(elem[i] == toFind){
                return i;
            }
        }
        return -1;
    }
1
2
3
4
5
6
7
8

Get the element at position pos

Output the element at position pos.
Precautions:

• Check whether POS is legal

public int get(int pos) {
        try{
            if(checkPosInAdd(pos)){
                return elem[pos];
            }
        }catch(PosIllegalException e){
            e.printStackTrace();
        }
        return 0;
    }
1
2
3
4
5
6
7
8
9
10

Set the element at position pos to value

Modify the pos position element.
Precautions:

• Check whether the POS is legal.

public void set(int pos, int value) {
        try{
            if(checkPosInAdd(pos)){
                elem[pos] = value;
            }
        }catch(PosIllegalException e){
            e.printStackTrace();
        }
    }
1
2
3
4
5
6
7
8
9

Delete the first occurrence of the keyword key

Delete the first occurrence of key.
Precautions:

• Loop through the search.
• Use the elements after the found key to overwrite them one by one.
• usedSize is reduced by 1.

public void remove(int key) {
        for (int i = 0; i < usedSize; i++) {
            if(elem[i] == key){
                for (int j = i; j < usedSize - 1; j++) {
                    elem[j] = elem[j + 1];
                }
                usedSize--;
            }
        }
    }
1
2
3
4
5
6
7
8
9
10

Get the length of the sequence list

The length of the sequence table is obtained, which refers to the number of useful data, that is, usedSize.

public int size() {
        return usedSize;
    }
1
2
3

Clear sequence table

Set the contents of the sequence table to empty.
Precautions:

• Because the real sequence table stores generics, the elements are set to empty one by one through the sequence table, and are replaced by 0 below.
• UsedSize is also set to 0.

public void clear() {
        for (int i = 0; i < usedSize; i++) {
            elem[i] = 0;
        }
        usedSize = 0;
    }
1
2
3
4
5
6

ArrayList in Java

In Java, the ArrayList class is provided to represent sequential lists.

Implemented interfaces

Interface Description:

1. The RandomAccess interface indicates support for random access.
2. The Cloneable interface indicates support for cloning.
3. The Serializable interface indicates support for serialization.

Construction method

Java provides 3 construction methods as shown in the table:

Common methods

The common methods provided are similar to what we implemented above.

Pros and cons of sequential lists

advantage

The advantages of sequential lists are as follows:

1. Supports random access.
2. Fast query given index.

shortcoming

1. If there is not enough space, the capacity needs to be expanded, which will result in a waste of memory.
2. Insertions and deletions at the head and in the middle will cause the data to be moved.

practise

Links to the exercises are below:
Pascal's Triangle