## Data structure sequence table

MoYu-zc 2021-06-24 00:20:00
data structure sequence table

# The order sheet

A sequence table is a linear table stored in the memory of a computer in the form of an array , The sequential storage of linear table refers to a group of storage units with continuous addresses , Store the elements in the linear table in turn 、 The data elements that ring on the logical structure in the linear table are stored in the adjacent physical storage units , That is to say, the logical adjacency relationship between data elements is reflected by the adjacency relationship of physical storage of data elements .

## 1. Implementation sequence table

Code implementation

``````public class SequenceList<T>{
// Array of storage elements
private T[] list;
// Record the number of elements in the current sequence table
private int n;
public SequenceList(int capacity) {
// Initialize array
this.list = (T[]) new Objects[capacity];
// Initialization length
this.n = 0;
}
// Set a linear table to an empty table
public void clear() {
this.n = 0;
}
// Judge whether the current linear table is empty
public boolean isEmpty() {
return n == 0;
}
// Get the length of the linear table
public int length() {
return n;
}
// Get the element at the specified location
public T get(int i) {
return list[i];
}
// Add elements to the linetype table t
public void insert(T t) {
list[n++] = t;
}
// stay i Insert element at element t
public void insert(int i, T t) {
// Indexes i After the elements , Move backward in turn
for (int index = n; index > i; index--) {
list[index] = list[index - 1];
}
// t Put it in i Index
list[i] = t;
// Element number +1
n++;
}
// Delete the specified location i The element of , And return the element
public T remove(int i) {
// Deleted elements
T current = list[i];
// Indexes i After the elements , Move forward in turn
for (int index = i; index < n - 1; index++) {
list[index] = list[index + 1];
}
// Element number -1
n--;
return current;
}
// lookup t Where the element first appeared
public int indexOf(T t) {
for (int i = 0; i < n; i++) {
if (list[i].equals(t)) {
return i;
}
}
return -1;
}
}
``````

Code testing

``````public class SequenceListTest {
public static void main(String[] args) {
// Create a sequence table object
SequenceList<String> sl = new SequenceList<>(10);
// Test insert
sl.insert("test1");
sl.insert("test2");
sl.insert("test3");
sl.insert(1,"test4");
// Test acquisition
String getResult = sl.get(1);
System.out.println(" Get index 1 The result is ："+getResult);
// Test to delete
String removeResult = sl.remove(0);
System.out.println(" The deleted element is ："+removeResult);
// Test empty
sl.clear();
System.out.println(" The number of elements in the cleared linear table is :"+sl.length());
}
}
``````

## 2. Sequence table traversal

1. Inheritance implementation `Iterable` Interface , rewrite `iterator` Method ;

2. Provide an inner class `SIterator`, Realization `Iterator` Interface , rewrite `hasNext` Methods and `next` Method

Code implementation

``````public class SequenceList<T> implements Iterable<T> {
// ..... Previous code
// rewrite iterator Method
@Override
public Iterator<T> iterator() {
return new SIterator();
}
// Inner method class , Realization Iterator Interface
private class SIterator implements Iterator {
private int cusor;
// Construction method
public SIterator() {
this.cusor = 0;
}
// Does the next one exist
@Override
public boolean hasNext() {
return cusor < n;
}
// Point to the next value
@Override
public Object next() {
return list[cusor++];
}
}
}
``````

Code testing

``````public static void main(String[] args) {
// Create a sequence table object
SequenceList<String> sl = new SequenceList<>(10);
// Test insert
sl.insert("test1");
sl.insert("test2");
sl.insert("test3");
sl.insert(1,"test4");
for (String s : sl) {
System.out.println(s);
}
System.out.println("-------------------------------");
// Test acquisition
String getResult = sl.get(1);
System.out.println(" Get index 1 The result is ："+getResult);
// Test to delete
String removeResult = sl.remove(0);
System.out.println(" The deleted element is ："+removeResult);
// Test empty
sl.clear();
System.out.println(" The number of elements in the cleared linear table is :"+sl.length());
}
``````

## 3. The capacity of the order table is variable

test

1. Create a capacity of `2` The order of
2. Insert in `3` Elements
``````public static void main(String[] args) {
// Create a sequence table object
SequenceList<String> sl = new SequenceList<>(2);
// Test insert
sl.insert("test1");
sl.insert("test2");
sl.insert("test3");
}
``````

When adding elements , You should check whether the current array size can accommodate new elements , If it can't hold , You need to create a new array with a larger capacity , Let's create an original array here ` twice as much ` New array storage elements of capacity .

2. When removing elements ：
When removing elements , You should check whether the size of the current array is too large , This will cause a waste of memory space , You should create a smaller array to store elements . If we find that the number of data elements is less than the capacity of the array 1/4, Then create one that is the capacity of the original array `1/2` New array storage elements for .

Code implementation

Modify the above code

``````// According to the parameters newSize, Reset eles Size
public void resize(int newSize) {
// Define a temporary array , Point to the original array
T[] t = list;
// Create a new array
list = (T[]) new Object[newSize];
// Copy array data
for (int i = 0; i < n; i++) {
list[i] = t[i];
}
}
``````
``````// Add elements to the linetype table t
public void insert(T t) {
// Judge whether to expand capacity
if (n == list.length) {
resize(2 * n);
}
list[n++] = t;
}
// stay i Insert element at element t
public void insert(int i, T t) {
// Judge whether to expand capacity
if (n == list.length) {
resize(2 * n);
}
// Indexes i After the elements , Move backward in turn
for (int index = n; index > i; index--) {
list[index] = list[index - 1];
}
// t Put it in i Index
list[i] = t;
// Element number +1
n++;
}
// Delete the specified location i The element of , And return the element
public T remove(int i) {
// Deleted elements
T current = list[i];
// Indexes i After the elements , Move forward in turn
for (int index = i; index < n - 1; index++) {
list[index] = list[index + 1];
}
// Element number -1
n--;
// The number of elements is less than 1/4 length , The capacity is reduced to 1/2
if (n < list.length / 4) {
resize(list.length / 2);
}
return current;
}
``````

## 4. Time complexity

• get(i) : It's not hard to see. , Regardless of the number of data elements N How big is the , Only one query is needed to get the corresponding element , So the time complexity is `O(1)` ;

• insert(int i,T t) : Every time you insert , All need to put `i` The element behind the position moves once , With the number of elements N The increase of , The more elements you move , Time is complicated by `O(n)` ;

• remove(int i) : Every time you delete , All need to put `i` The element behind the position moves once , With the amount of data N The increase of , The more elements you move , The time complexity is `O(n)` ;

Because the bottom layer of the order table is implemented by arrays , The length of the array is fixed , So the container expansion operation is involved in the process of operation . As a result, the time complexity of the sequence table is not linear , At some nodes that need to be expanded , It's going to take a lot of time , Especially the more elements , The more obvious the problem is

https://javamana.com/2021/06/20210624001910562a.html