I. diagram sequence table

Concept of sequence table

Sequential table is a linear structure in which data elements are stored in sequence with a storage unit with continuous physical addresses. Generally, array storage is used. Complete the addition, deletion, query and modification of data on the array. (what we want to describe below is a dynamic sequential table, which dynamically allocates a memory space for data)

Implementation of sequence table

In Java classes and objects, we learned that. Java is an object-oriented programming language for how to add, delete, check and modify a group of data. We can put them into a class by instantiating objects. You can directly call the corresponding operation without too much concern about how the class is implemented. For a dynamic sequence table, we can define an array to store these data, and use useside to represent the length of the actual effective data in the array. In this way, we can get the member properties of the class and implement them through the corresponding methods. Next, let's understand what a sequence table is by combining pictures and code.

1 Abstract corresponding class

class ordly {
    public int[] elem;
    public int useside;//Indicates the effective length of the data
    public ordly(){
        this.elem=new int[6];
    }
}

Class 2 methods to implement the sequence table

For the caller of a class, it provides a corresponding interface to implement

2.1 printing of sequence table

  // Print sequence table (code implementation)
    public void display() {
        for (int i = 0; i < useside; i++) {
            System.out.println(elem[i]+" ");
        }
    }

2.2 new elements in sequence table

    // Add new element in pos (code implementation)
    public boolean isfull(){
        return this.useside==elem.length;
    }
    public void add(int pos, int data) {
        if (pos<0||pos>useside){
            System.out.println("input pos Illegal location");
            return;
        }
        if (isfull()){//Determine whether capacity expansion is required
            elem= Arrays.copyOf(elem,2*elem.length);
        }
        for (int i=useside-1;i>=pos;i--){
            elem[i+1]=elem[i];
        }
        elem[pos]=data;
        useside++;
    }

2.3 determining whether an element is included

    // Determine whether an element is included (code implementation)
    public boolean contains(int toFind) {
        if(useside==0){
            System.out.println("This is an empty sequence table");
            return false;
        }
        for (int i = 0; i < useside; i++) {
            if (elem[i]==toFind){
                return true;
            }
        }
        return false;//If the data is not found after the cycle, it means that there is no such data
    }

2.4 get the length of sequence table

 // Get sequence table length
    public int size() { 
    return useside;
     }

2.5 find the corresponding position of an element

Method is similar to whether to include a number

    // Find the corresponding location of an element (code implementation)
    public int search(int toFind) {
        if (useside==0){
            System.out.println("Empty sequence table, no data you are looking for");
        }
        for (int i = 0; i < useside; i++) {
            if (elem[i]==toFind){
                return i;
            }
        }
        return -1;//Can't find
    }

2.6 get pos location elements

    // Get the element of pos location (code implementation)
    public int getPos(int pos) {
            if (pos<0||pos>useside){
                System.out.println("Illegal input position");
                return -1;
            }
            if (useside==0){
                System.out.println("This is an empty sequence table");
                return -2;
            }
            return elem[pos];
    }

2.8 change pos position to value

  // Set the element of pos position to value
    public void setPos(int pos, int value) {
        if (pos<0||pos>useside){
            System.out.println("Illegal input position");
            return;
        }
        if (useside==0){
            System.out.println("This is an empty linked list");
            return;
        }
        elem[pos]=value;
    }

2.9 delete the keyword key that appears for the first time

    //Delete the keyword key that appears for the first time
    public void remove(int toRemove) {
        if (useside==0){
            System.out.println("This is an empty sequence table. There is no data you want to delete");
            return;
        }
        int index=search(toRemove);
        if (index==-1){
            System.out.println("There are no elements you want to delete");
        }
        for (int i = index; i <useside-1 ; i++) {
            elem[i]=elem[i+1];
        }
        useside--；
    }

2.10 emptying sequence table

 public void clear() {
        useside=0;
    }

In particular, the operations of emptying the sequence table and deleting the sequence table of an element are aimed at simple types, for reference types. We don't do this. For the source code of this block and the processing of reference operation types, you can refer to the code on my code cloud. I hope it will be helpful to you.
Code cloud address

Sequence table defect

1. For the insertion and deletion of sequence table, the complexity is O (N).
2. For capacity expansion, copying the array and freeing up the old space will consume a lot
3 for capacity expansion, there is still a waste of space
Defect solution: introduce linked list to solve this problem.

II. Graphical single link list

concept

Linked list is a discontinuous storage structure in physical storage structure. The logical order of data elements is realized through the reference link order in the linked list.

Classification of linked lists

Unidirectional head circulation unidirectional head non circulation
One way no lead cycle one way no lead no cycle
Two way lead circulation two way lead non circulation
Two way no lead cycle two way no lead no cycle
For single linked lists, we mainly focus on one-way, no lead, no loop.

node

For a single linked list, instead of using arrays, we use nodes to describe the linked list. For a node, it is composed of two parts: val (one value, integer) and next (reference type, used to point to the next address), as shown in the figure:

Head node and tail node

In the single linked list, we will take the first node as the head node. Note that in the one-way non leading non cyclic linked list, this head node can be changed (the head node means that it is the first in the single linked list), and the next of the tail node is null, as shown in the figure:

Common implementation methods of single linked list

1 abstract class

For a node, it is a type, which will contain the member attributes of val and next.
Single linked list is a kind of list, which contains nodes and basic implementation methods for single linked list operations

class nodelist{//node
    public int val;
    public nodelist next;

    public nodelist(int val){
        this.val=val;
    }
}
class singlelist{//Single linked list
    nodelist head;
}

2 implementation method in single linked list

2.1 instantiate a single linked list

Code implementation:

public void creat(){
       nodelist list=new nodelist(10);
       nodelist list1=new nodelist(20);
       nodelist list2=new nodelist(35);
       nodelist list3=new nodelist(20);
       nodelist list4=new nodelist(23);
       list.next=list1;
       list1.next=list2;
       list2.next=list3;
       list3.next=list4;
       head=list;
   }

2.2 traversing the single linked list

Using the loop to traverse, the code is implemented as follows

 //Print single linked list
    public void display(){
       nodelist cur=head;//Since the head node has not changed, it cannot be moved. At this time, create a head node equal to head to traverse instead of head
       while (cur!=null){
           System.out.print(cur.val+" ");
           cur=cur.next;//Now cur moves back
       }

    }

2.3 head insertion method

 //Head insertion
    public void addFirst(int data){
       nodelist first=new nodelist(data);
       first.next=head;
       head=first;
    }

2.4 tail interpolation

//Tail interpolation
    public void addLast(int data){
       nodelist last=new nodelist(data);
       nodelist cur=head;
       while (cur.next!=null){
           cur=cur.next;
       }
       cur.next=last;//After reaching the tail node, replace null with the address of last
    }

2.5 check whether the keyword is included and whether the key is in the single linked list

For this, we can traverse the single linked list to find whether there will be a value equal to key.

    //Find out whether the keyword is included and whether the key is in the single linked list
    public boolean contains(int key){
       if (head==null){//Single linked list is empty
           return false;
       }
       nodelist cur=head;
       while (cur!=null){
           if(cur.val==key){
               return true;
           }
           cur=cur.next;
       }
       return false;
    }

2.6 find the length of single linked list

    //Get the length of the single linked list
    public int size(){
       if (head==null){
           return -1;//Indicates that the single linked list is empty
       }
       int count=0;
       nodelist cur=head;
       while (cur!=null){
           count++;
           cur=cur.next;
       }
       return count;
   }

2.7 delete the node whose keyword is key for the first time

public void remove(int key){
       boolean ret=contains(key);
       if (ret==false){//Judge whether the single linked list contains the element you want to find, and call contains (key)
           System.out.println("There is no data you want to delete");
           return;
       }
       if (head.val==key){//But when the head node is deleted
           head=head.next;
           return;
       }
       nodelist cur=head;
       while (cur!=null){
           if (cur.next.val==key){
               cur.next=cur.next.next;
               return;
           }else{
               cur=cur.next;
           }
       }

    }

2.8 delete all nodes with key value

 //Delete all nodes with the value of key
    public void removeAllKey(int key){
        boolean ret=contains(key);//Judge whether the keyword key to be deleted is included
        if (ret==false){
            System.out.println("There are no elements you want to delete");
            return;
        }
        nodelist cur=head;
        nodelist prve=head.next;
        while (prve!=null){
            if (prve.val==key){
                cur.next=prve.next;
                prve=prve.next;
            }else{
                cur=cur.next;
                prve=prve.next;
            }

        }
        if (head.val==key){//If the header node is also equal to key
            head=head.next;
        }
    }

2.9 insert at any position, and the first data node is subscript 0

Before insertion:

After insertion:

    //Insert at any position, and the first data node is subscript 0
    public void addIndex(int index,int data){
       nodelist add=new nodelist(data);
        if (index==0){//Head insertion
            addFirst(data);
            return;
        }
        if (index==size()){//Tail interpolation
            addLast(data);
            return;
        }
        nodelist cur =head;
        while (index-1!=0){
            cur=cur.next;
        }
        add.next=cur.next;
        cur.next=add;

    }

2.10 empty single linked list

   public void clear(){
       //Empty head=null;
        while (head!=null){
            nodelist cur=head.next;
            head=null;
            head=cur;
        }
    }

Single linked list source address

Summary of sequence table and single chain table:

For sequence table and single linked list, we should know what the operation principle is and how to operate. We can understand it by drawing pictures, so as to deepen our understanding and application of single linked list and sequence table. Then we can consolidate and spread our thinking through some exercises, so as to improve our programming ability and specific topics, You can take a look at my later article records.