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. Sequence table can be generally divided into: static sequence table: using fixed length array storage. Dynamic sequential table: use dynamic array storage. The static sequence table is suitable for determining the scenario that knows how much data needs to be stored. The fixed length array of static sequence table leads to large N, waste of space and insufficient space In contrast, the dynamic sequential table is more flexible and dynamically allocates space according to needs.
Next, let's implement a dynamic sequence table.
1, Interface to implement
public class SeqList {
// Print sequence table
public void display() { }
// Add new element in pos position
public void add(int pos, int data) { }
// Determines whether an element is included
public boolean contains(int toFind) { return true; }
// Find the location of an element
public int search(int toFind) { return -1; }
// Gets the element of the pos location
public int getPos(int pos) { return -1; }
// Set the element of pos position to value
public void setPos(int pos, int value) { }
//Delete the keyword key that appears for the first time
public void remove(int toRemove) { }
// Get sequence table length
public int size() { return 0; }
// Empty sequence table
public void clear() { }
}2, Implementation of interface
1. Build the framework of table
As you can see from the picture above, We need to create an array (int[] elem) and add elements to it by ourselves. At the same time, we also need to know the size of the array in this table. The size of the array is determined by ourselves. Here, we assume the capacity of the initial development The size of (int IntCapacity) is 10. Although we have opened up such a large table, not every array may contain elements. At this time, we need to know its real size, that is, the effective size (int usedSize).
public int[] elem;
//Number of valid data
public int usedSize;
//The initial capacity cannot be changed
public static final int intCapacity = 10;
//Create the object and call the appropriate constructor
public MyArrayList() {
//Create an array object with an initial capacity of 10 sizes
this.elem = new int[intCapacity];
this.usedSize = 0;
}2. Print sequence table
First, print the sequence table. Only after printing can we know whether the subsequent interface implementation is correct. At the beginning, the contents of the table are empty. In this way, the printed table is naturally empty. Here, we assume that the table has content. We just need to traverse the table. Note that to print the valid elements in this table, you need to specify the end condition of traversal, whether it is IntCapacity or usedSize.
// Print sequence table
public void display() {
int i = 0;
for(i = 0; i < this.usedSize; i++) {
System.out.print(this.elem[i] + " ");
}
System.out.println();
//System.out.print(Arrays.toString(this.elem));
}3. Add an element at pos
Here, we need to consider: 1, how to achieve? 2. Is the pos position entered within the valid range of this array? 3. Will this array be full? What should I do when it's full?
We first consider how to achieve this problem. After finding the pos position first, move the elements inside and leave a position for the elements to be inserted. Otherwise, direct insertion will overwrite the contents of the pos position. Therefore, move the element after pos. When moving, you should start from the last one. Otherwise, moving from the pos position will still cause the problem of coverage. After that, let usedSize + +.
Next, consider questions 2 and 3. For question 2, pos is within the valid range and can be operated. The range is from the subscript 0 to the subscript usedSizes - 1. Once out of this range, it is illegal and needs to be warned. You can use exceptions or print. Question 3, we need to judge the full situation. When adding elements, usedSize (effective length) during accumulation, when enough elements are added, the usedsize will be equal to the capacity length of the array. Here is the condition for judging whether to expand the capacity. At the same time, note that the initial capacity cannot be changed, so when expanding the capacity, you need to copy the array for capacity expansion. You can copy the array by using the copyOf method in Arrays , while expanding capacity.
//Check pos location validity
private void checkPos(int pos) {
if(pos < 0 || pos > this.usedSize) {
throw new RuntimeException("pos Illegal location!");
}
}
//Check whether the array is full
private boolean isFull() {
if(this.elem.length == this.usedSize) {
return true;
}
return false;
}
// Add new element in pos position
public void add(int pos, int data) {
//pos location legitimacy
checkPos(pos);
//Check whether the array is full
if(isFull()) {
this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);
}
//New element
for(int i = this.usedSize - 1; i >= pos; i--) {
this.elem[i + 1] = this.elem[i];
}
this.elem[pos] = data;
this.usedSize++;
}4. Determine whether an element is included
This only needs to be traversed and then judged.
// Determines whether an element is included
public boolean contains(int toFind) {
for(int i = 0; i < this.usedSize; i++) {
if(this.elem[i] == toFind) {
return true;
}
}
return false;
}5. Find the corresponding position of an element
This only needs to be traversed and then judged. The function of legitimacy check has been written earlier. You can call it directly.
// Find the location of an element
public int search(int toFind) {
//Legitimacy check
checkPos(toFind);
for(int i = 0; i < this.usedSize; i++) {
if(this.elem[i] == toFind) {
return i;
}
}
return -1;
}6. Get the element of pos position
Questions to consider: 1. How to find? 2. Legitimacy? 3. Is the table empty?
We have previously written the function to judge the legitimacy of pos. here we only need to call it. Now let's solve problem 3. Why judge whether the table is empty? If the table is empty, it means that its effective length is 0, that is, there are no elements to return and no need to get.
//Judge whether it is empty
private boolean isEmpty() {
return this.usedSize == 0;
}
// Gets the element of the pos location
public int getPos(int pos) {
//Is the table empty
if (isEmpty()) {
//You can also print
throw new RuntimeException("Table is empty!");
}
//Check legitimacy
if(pos < 0 || pos >= this.usedSize) {
throw new RuntimeException("pos Illegal location!");
}
//Get element
return this.elem[pos];
}
7. Set the element of pos position to value
First, check the validity, and then overwrite the value. Whether the table is empty needs to be judged.
// Set the element of pos position to value
public void setPos(int pos, int value) {
checkPos(pos);
if(isFull()) {
throw new RuntimeException("Table is empty!");
}
this.elem[pos] = value;
}8. Delete the keyword key that appears for the first time
After deletion, let the effective length --.
//Delete the keyword key that appears for the first time
public void remove(int toRemove) {
int pos = search(toRemove);
if(pos == -1) {
System.out.println("The value was not found!");
return;
}
for(int i = pos; i < this.usedSize - 1; i++) {
this.elem[i] = this.elem[i + 1];
}
this.usedSize--;
}9. Obtain the length of sequence table
The length of the sequence table is its effective length.
// Get sequence table length
public int size() {
if (!isEmpty()) {
return this.usedSize;
}
return 0;
}10. Clearing sequence table
Let the effective length be 0.
// Empty sequence table
public void clear() {
this.usedSize = 0;
}3, All codes and results
import java.util.Arrays;
/**
* @author: Naion
* @create: 2021-12-26 14:56
**/
public class MySeqlist {
//Define a sequence table
private int[] elem;
private int usedSize;
private int intCapacity = 10;
//Call the appropriate constructor
public MySeqlist() {
//Define size
this.elem = new int[intCapacity];
this.usedSize = 0;
}
// Print sequence table
public void display() {
int i = 0;
for(i = 0; i < this.usedSize; i++) {
System.out.print(this.elem[i] + " ");
}
System.out.println();
}
//Check pos location validity
private void checkPos(int pos) {
if(pos < 0 || pos > this.usedSize) {
throw new RuntimeException("pos Illegal location!");
}
}
//Check whether the array is full
private boolean isFull() {
if(this.elem.length == this.usedSize) {
return true;
}
return false;
}
// Add new element in pos position
public void add(int pos, int data) {
//pos location legitimacy
checkPos(pos);
//Check whether the array is full
if(isFull()) {
this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);
}
//New element
for(int i = this.usedSize - 1; i >= pos; i--) {
this.elem[i + 1] = this.elem[i];
}
this.elem[pos] = data;
this.usedSize++;
}
// Determines whether an element is included
public boolean contains(int toFind) {
for(int i = 0; i < this.usedSize; i++) {
if(this.elem[i] == toFind) {
return true;
}
}
return false;
}
// Find the location of an element
public int search(int toFind) {
//Legitimacy check
checkPos(toFind);
for(int i = 0; i < this.usedSize; i++) {
if(this.elem[i] == toFind) {
return i;
}
}
return -1;
}
//Judge whether it is empty
private boolean isEmpty() {
return this.usedSize == 0;
}
// Gets the element of the pos location
public int getPos(int pos) {
//Is the table empty
if (isEmpty()) {
throw new RuntimeException("Table is empty!");
}
//Check legitimacy
if(pos < 0 || pos >= this.usedSize) {
throw new RuntimeException("pos Illegal location!");
}
//Get element
return this.elem[pos];
}
// Set the element of pos position to value
public void setPos(int pos, int value) {
checkPos(pos);
if(isFull()) {
throw new RuntimeException("Table is empty!");
}
this.elem[pos] = value;
}
//Delete the keyword key that appears for the first time
public void remove(int toRemove) {
int pos = search(toRemove);
if(pos == -1) {
System.out.println("The value was not found!");
return;
}
for(int i = pos; i < this.usedSize - 1; i++) {
this.elem[i] = this.elem[i + 1];
}
this.usedSize--;
}
// Get sequence table length
public int size() {
if (!isEmpty()) {
return this.usedSize;
}
return 0;
}
// Empty sequence table
public void clear() {
this.usedSize = 0;
}
}/**
* @author: Naion
* @create: 2021-12-26 14:55
**/
public class test_12_26_01 {
public static void main(String[] args) {
MySeqlist myseqlist = new MySeqlist();
for(int i = 0; i < 10; i++) {
myseqlist.add(i, i);
}
myseqlist.display();
System.out.println("======");
myseqlist.add(1, 3);
myseqlist.display();
System.out.println("======");
System.out.println(myseqlist.contains(3));
System.out.println("======");
System.out.println(myseqlist.search(3));
System.out.println("======");
System.out.println(myseqlist.getPos(1));
System.out.println("======");
myseqlist.setPos(1, 0);
myseqlist.display();
System.out.println("======");
myseqlist.remove(0);
myseqlist.display();
System.out.println("======");
System.out.println(myseqlist.size());
System.out.println("======");
myseqlist.clear();
myseqlist.display();
}
}
4, Sequence table problem
1. Insert and delete the middle / header of the sequence table, with a time complexity of O(N)
2. Capacity increase requires applying for new space, copying data and releasing old space. There will be a lot of consumption.
3. The capacity increase is generally double, which is bound to waste some space. For example, if the current capacity is 100 and the capacity is increased to 200 when it is full, we continue to insert 5 data, and there is no data to insert later, then 95 data spaces are wasted.
These problems need to be solved by single linked list.