The linear table

Linear list: a finite sequence of zero or more data elements

The set of data objects in a linear table is {A1, A2… , an}, each data element has the same type. Where, each element has one and only one immediate precursor except for the first element A1, and each element has one and only one immediate successor except for the last element an. The relationship between data elements is one-to-one.

The sequential storage structure of linear tables

The data elements of a linear table are stored at a time in contiguous storage cells

a1 a2 . ai-1 ai . an

The sequential storage structure requires three properties:

  • The starting location of storage space: data, its storage location is the storage location of storage space.

  • Maximum storage capacity for linear tables: array length MaxSize.

  • Current length of a linear table: length.

    Note the difference between the length of an array and the length of a linear table: the length of an array is the size of the storage space used to store a linear table. The length of a linear table is the number of data elements in a linear table, which varies with insertion and deletion operations. At any given time, the length of the linear list should be less than or equal to the length of the array.

Memory address calculation method

Storing a sequential table in an array means allocating a fixed length of array space, which must be greater than or equal to the length of the current linear table because insertion and deletion can be performed in a linear table.

Addresses in memory, like seats in a library, are numbered. Each location in memory has its own number, which is an address. Because of the sequential structure, after the first position is determined, the following positions are computable. For example, I ranked fifth in my class, and the 10 students behind me ranked sixth and seventh respectively… Because 5+ 1,5 +2… , 5 + 10. Each data element, no matter whether it is plastic, real or character, needs to occupy a certain amount of storage space. Assuming that c storage units are occupied, the storage location of the ith +1 data element and the storage location of the ith data element in the linear table satisfy the following relation:

LOC(ai+1)=LOC(ai)+c

Therefore, the storage location of the ith data element AI can be calculated by A1:

LOC(ai)=LOC(a1)+(i-1)*c

And by using this formula, you can figure out the address at any point in the linear table, at any point in the linear table, at the same time. Its time complexity is O(1). The storage structure with this characteristic is usually called random access structure.

Insertion and deletion of sequential storage structures (Java ArraryList class)
1. Get element operation code:
public class ArrayList<E> { transient Object[] elementData; public E get(int index) { Objects.checkIndex(index, this.size); return this.elementData(index); } E elementData(int index) { return this.elementData[index]; }}Copy the code
2. Insert

For example, buying train tickets during the Spring Festival travel rush. Everybody’s lined up pretty good. This is to a beauty, in the line of the third you said, “eldest brother, please help, home mother sick, anxious to go back to see her, the line is so long, can you let me row in front of you?” When you relented, you said yes. Everyone in the back has to step back. In fact, this example has illustrated the linear table sequential storage structure, in the insertion of data implementation process.

Insert the idea:

  • If the insertion position is not reasonable, throw an exception;
  • If the linear table length is greater than or equal to the array length, throw an exception or increase the size dynamically.
  • Start from the last element and traverse forward to the ith position, moving them back one position each;
  • Insert the element at position I and add 1 to the table length.

Code implementation:

public boolean add(E e) {
        ++this.modCount;
        this.add(e, this.elementData, this.size);
        return true;
}
​
public void add(int index, E element) {
    this.rangeCheckForAdd(index);
    ++this.modCount;
    int s;
    Object[] elementData;
    if ((s = this.size) == (elementData = this.elementData).length) {
        elementData = this.grow();
    }
​
    System.arraycopy(elementData, index, elementData, index + 1, s - index);
    elementData[index] = element;
    this.size = s + 1;
}
Copy the code
3. Delete the vm

Follow the example above. Just then, a policeman appeared and said to the beauty, “Come with me to the station.” The woman left the group. It turned out that she was scalping train tickets, pathetic to jump the queue to buy tickets. At this time, the line of people, all moved forward a step. This is how the sequential storage structure of a linear table removes elements.

Delete thread:

If the deletion location is inappropriate, throw an exception.

Remove the deleted element;

Traverse from the deleted element position to the last element position, moving them all forward one position each;

The table length is reduced by 1.

Code implementation:

public E remove(int index) {
    Objects.checkIndex(index, this.size);
    Object[] es = this.elementData;
    E oldValue = es[index];
    this.fastRemove(es, index);
    return oldValue;
}
​
Copy the code
Insert and delete time complexity.

In the best case, if you want to insert the element to the last position, or delete the last element, the time is O(1), because you don’t need to move the element.

In the worst case, if the element is inserted into the first position or deleted from the first position, the time is O(n) because all elements are moved back or forward after 1 position.

In the average case, n minus I elements need to be moved because the element is inserted into the ith position, or the ith element is deleted. According to the principle of probability, each position has the same probability of inserting or deleting elements, that is, the higher the position, the more elements are moved, and the lower the position, the less elements are moved. So the average number of moves is the same as the number of moves in the middle element, which is order n minus 1 over 2, which is order n.

The time complexity of sequential storage structure of linear table is O(1) no matter where the data is stored or read. When you insert or delete, it’s O(n). This shows that it is suitable for the application where the number of elements does not change much, but is more about accessing data.

Advantages and disadvantages of the linear table sequential storage structure
Advantages:
  • No additional storage is required for logical relationships between elements in the table
  • You can quickly fetch an element anywhere in the table
Disadvantages:
  • Insert and delete operations require moving a large number of elements
  • When the length of linear table varies greatly, it is difficult to determine the capacity of storage space
  • Causing “fragmentation” of storage space
Reference:

Big Talk Data Structure cheng Jie