The operation and method of sequence list and linked list in data structure:
1. Initialization Construction Method
2. Add delete check change common method
3. Destruction Possibility of Nonexistence
I. Linear Tables
linear list is a finite sequence of n data elements with the same characteristics. Linear table is a data knot widely used in practice.
Construct, common linear list: sequence list, linked list, stack, queue, string...
The linear table is logically a linear structure, that is to say, a continuous straight line. But it's not necessarily continuous in physical structure. It's linear in matter.
When stored rationally, it is usually stored in the form of arrays and chains.
SEQUENCE TABLE
1. Concept and structure: Sequence table is a linear structure that stores data elements sequentially by a storage unit with a continuous physical address. Generally, array storage is used. Complete data addition, deletion and modification on the array. The sequence table can generally be divided into:
Static Sequence Table: Store in fixed-length array.
(2) Dynamic Sequence Table: Use dynamic open array storage.
2. Interface implementation:
public void pushBack(int element) //Increase to the end
public void pushFront(int element) //Increase at the beginning
public void insert(int index, int element) //Consider whether to insert the number outside of the array subscript
public void popBack() //Delete the last
public void popFront() //Delete the front
public void earse(int index) //Delete the middle
public void print() //Printing
private void ensureCapacity() //Capacity expansion
public int indexOf(int element) //Look up the data content and return the subscript of the data
public int get(int index) //Look up the subscript and return the data corresponding to the subscript
public void remove(int element) //Delete an element, and if it occurs multiple times, delete the first occurrence.
public void removeAll(int element) { //Delete all the data that appear in the table
3. Questions to be considered in the order table:
(1) The time complexity of insertion and deletion of middle/head is O(N);
(2) Increasing capacity requires applying for new space, copying data and releasing old space. There will be no small consumption;
(3) Increasing capacity is generally a double increase, which will inevitably lead to a certain amount of waste of space. For example, the current capacity is 100, when it is full, it will increase to 200. We will continue to insert five more data. If there is no data insertion after that, 95 data spaces will be wasted.
4. Writing procedures: Write pseudo-code and translate it into java code
5. Enlarging, increasing, deleting, checking and reforming thinking guidance:
Consider the relationship between array capacity (array.length) and the number of existing data (size)
1. Enough capacity: size < array. length;
2. Insufficient capacity: (Similar to moving, 1.5 or twice as large as moving to a previous home)
int newCapacity=array.length*2;
Moving to a new house (redefining an array, large memory)
int[] newArray=new int[newCapacity];
(2) Moving (putting the contents of the original array into the new array)
for(int i=0;i<size;i++){
newArray[i]=array[i];
}
(3) Tell someone that they have moved (visit new attributes)
this.Array=newArray;
(4) Return the old house: the original array object has no reference point, and automatically releases into garbage.
6. Addition/deletion of order table for drawing demonstration
7. Examples
// The element type int of the sequence table
public class MyArrayList1 {
// What are attributes?
private int[] array; // Represents an array of existing data.
// array.length represents the capacity of an array
private int size; // Number of Existing Data in Record Sequence Table
// Construction method
public MyArrayList1() {
// 1. Application space
array = new int[2];
// 2. Number of initialization data
size = 0;
}
//The subscript of the data that index needs to insert; the data that element needs to insert
// Increase (emphasis)
// Average O(1)
public void pushBack(int element) { //Increase to the end
ensureCapacity(); //Call expansion function to increase capacity
array[size++] = element; //Just insert the number directly to the end.
}
public void pushFront(int element) { //Increase at the beginning
ensureCapacity(); //Call expansion function to increase capacity
for (int i = size; i >= 1; i--) {
array[i] = array[i - 1]; //Appoint the former number to the latter by a loop
}
//Where the subscript is zero is empty.
array[0] = element; //Assign the number to be inserted to the place marked 0
size++; //Let size increase itself once
}
public void insert(int index, int element) { //Consider whether to insert the number outside of the array subscript
if (index < 0 || index > size) { //Output "subscript error" as long as one condition is satisfied
System.err.println("Subscription error");
return;
}
ensureCapacity();
for (int i = size - 1; i >= index; i--) {
array[i + 1] = array[i];
}
//for(int i=size;i>=index;i--){array[i]=array[i-1];}size++;
array[index] = element;
size++;
}
// Delete (emphasis)
public void popBack() { //Delete the last
if (size <= 0) { //If the sequence table is empty, the output of "the sequence table is empty"
System.err.println("The sequence table is empty");
return;
}
array[--size] = 0; //Let size-1 be zero in the original array, that is, size first -- and then reference
}
public void popFront() { //Delete the front
if (size <= 0) {
System.err.println("The sequence table is empty");
return;
}
//When deleting the first number, assign the latter number to the former number.
//for is usually followed by the scope of the modified array
for (int i = 0; i < size - 1; i++) {
array[i] = array[i + 1];
}
array[--size] = 0;
}
public void earse(int index) { //Delete the middle
if (size <= 0) {
System.err.println("The sequence table is empty");
return;
}
if (index < 0 || index >= size) {
System.err.println("Subscription error");
return;
}
for (int i = index + 1; i < size; i++) {
array[i - 1] = array[i];
}
//for(int i=index;i<size-1;i++){array[i]=array[i+1];}
array[--size] = 0;
}
// Printing
public void print() {
System.out.println("Print Sequence Table: Current capacity: " + array.length);
for (int i = 0; i < size; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
// Ensure adequate capacity or expand capacity
private void ensureCapacity() {
if (size < array.length) {
return;
}
int newCapacity = array.length * 2;
int[] newArray = new int[newCapacity];
for (int i = 0; i < size; i++) {
newArray[i] = array[i];
}
this.array = newArray; //Access properties
}
//Look up the subscript of element in the sequence table, and if it appears multiple times, return the subscript that first appears.
public int indexOf(int element) {
for (int i = 0; i < size; i++) {
if (array[i] == element) {
return i;
}
}
return -1;
}
//get is the second way to look up, returning the value of the subscript
public int get(int index) {
if (index < 0 || index >= size) {
System.err.println("Subscription error");
return -1;
}
return array[index];
}
//set is changed
public void set(int index, int element) {
if (index < 0 || index >= size) {
System.err.println("Subscription error");
return;
}
array[index] = element;
}
//Delete an element, and if it occurs multiple times, delete the first occurrence.
public void remove(int element) {
int mindex = indexOf(element); //Call the indexOf function to find the subscript for that number
if (index != -1) { //Explain the number in the table.
earse(index); //Call the earse function to delete the number labeled index
}
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void removeAll(int element) { //Delete all the data that appear in the table
int j = 0;
for (int i = 0; i < size; i++) {
if (array[i] != element) {
array[j++] = array[i];
}
}
size = j;
}
public static void main(String[] args) {
MyArrayList1 list = new MyArrayList1();
list.print();
list.pushBack(1);
list.pushBack(2);
list.pushBack(3);
// 1 2 3
list.print();
list.pushFront(10);
list.pushFront(20);
list.pushFront(30);
// 30 20 10 1 2 3
list.print();
list.insert(3, 100);
// 30 20 10 100 1 2 3
list.print();
list.insert(20, 200);
// Report errors
list.earse(2);
list.earse(2);
list.print();
// 30 20 1 2 3
list.popFront();
list.popFront();
list.popFront();
list.print();
// 2 3
list.popBack();
list.popBack();
list.print();
// Empty
list.popBack();
// Report errors
}
}
Operation results: