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.

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 (Reference: Java’s 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:

  1. If the insertion position is not reasonable, throw an exception;
  2. If the linear table length is greater than or equal to the array length, throw an exception or increase the size dynamically.
  3. Start from the last element and traverse forward to the ith position, moving them back one position each;
  4. 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:

  1. If the deletion location is inappropriate, throw an exception.

  2. Remove the deleted element;

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

  4. 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

A single – linked storage structure for linear tables

The chain storage structure of a linear table is characterized by an arbitrary set of storage units, which can be continuous or discontinuous, to store the data elements of a linear table. This means that these data elements can be stored anywhere memory is not occupied, as shown below:

In a sequential structure, only data information is needed for each element. Now, in addition to storing data information, the linked list structure also stores the storage addresses of its successors.

Data information + address of subsequent element = Node

The storage location of the first node in a single linked list is called the head pointer, and the entire linked list must be accessed from the ab initio pointer. Every node after that, that’s where the next pointer to the last one points to. The pointer to the last node is null. The diagram below:

The first node in a singly linked list is called a header. Header data can store no information, or it can be used to store additional information such as the length of a linear table. The pointer field of a header stores a pointer to the first node. The diagram below:

Header pointer and header:
The head pointer:
  • A header pointer is a pointer to the first node in the list, or to the first node if the list has a header
  • Header Pointers are used as identifiers, so they are often preceded by the name of the linked list
  • Whether the list is empty or not, the head pointer is not empty. The header pointer is a required element of the list
Head node:
  • The header node is set up for unity and convenience of operation. It is placed before the node of the first element and its data field is generally meaningless
  • With a header node, inserting a node before the first element node and deleting the first node are the same operations as other nodes
  • A header is not necessarily a list element

Reference:Basic Concepts of Linked Lists

Linear list chain storage structure code implementation
1. Overall code design of single linked list class (Reference:Java Basics — Implementation of Singleton Lists. Don Quixote)
public class Linked<E>
  private Node head; / / head node
	private int size;  // Number of linked list elements
  
	public Linked(a){
    this.head=null;
    this.size=0; }...// List nodes
  private static class Node<E> {
      E item; 			// Node data
      Node<E> next;	// Descendant (unidirectional lists have no "precursor")

      Node(E element, Linked.Node<E> next) {
          this.item = element;
          this.next = next; }}... }Copy the code
2. Nodes of singly linked lists

A node consists of a data field where data elements are stored and a pointer field where addresses of subsequent nodes are stored

// List nodes
private static class Node<E> {
  E item; 			// Node data
  Node<E> next;	// Descendant (unidirectional lists have no "precursor")
  
  Node(E element, LinkedList.Node<E> next) {
      this.item = element;
      this.next = next; }}Copy the code
3. Single linked list reading

In the sequential storage structure of a linear table, it is easy to calculate the storage location of any element. But in a singly linked list, there’s no way to know from the beginning where the ith element is, so you have to start from scratch.

Get the I th data in the list:

  1. Declare a node p to point to the first node in the list, initialize j from 1;
  2. When j
  3. If p is empty at the end of the list, the index element does not exist.
  4. Otherwise, the search succeeds and the data of node P is returned.

Code implementation:

public E get(int index) {
    int j = 1;
    Node<E> p = head.next; 
    while(p ! =null && j < index) {
        p = p.next;
        ++j;
    }
    if (p == null || j > index) {
        return null;
    } else {
        returnp.item; }}Copy the code

In other words, you start at the beginning, and you go all the way to node I. Since the time complexity of this algorithm depends on the position of I, when I =1, there is no need to traverse, and the data is taken out at the first one, while when I =n, n-1 traverse is ok. So the worst-case time is O(n).

4. Single linked list insertion

Assuming that the node of the storage element E is S, to realize the change of the logical relationship between nodes P, p->next and S, it is only necessary to insert node S between node P and p->next. The diagram below:

That s – > next = p – > next; P – > next = s. So the way to read these two lines of code is to change the successor of P to the successor of S, and then program s to the successor of P. The diagram below:

The algorithm idea of insertion node of the ith data in single linked list is as follows:

  1. Declare a pointer p to the linked list header and initialize j from 1;
  2. When j
  3. If p is empty at the end of the linked list, the index node does not exist.
  4. Otherwise, a null node S is generated in the system.
  5. Assign e to s->data;
  6. S ->next=p->next; P – > next = s.
// Insert elements into the middle of the list
public void add(E e, int index) {
    if (index < 0 || index > size) {
        throw new IllegalArgumentException("Index is error");
    }
    if (index == 0) {
        this.addFirst(e);
        return;
    }
    Node<E> p = this.head;
    int j = 1;
    // Find the previous node to insert the node
    while(p ! =null && j < index) {
        p = p.next;
        ++j;
    }
    if (p == null || j > index) {
        throw new NullPointerException("Node is not exist");
    }
    Node<E> node = new Node<>(e, null);
    // The next node of the node to be inserted points to the next node of the preNode
    node.next = p.next;
    // The next node of the preNode points to the node to be inserted
    p.next = node;
    this.size++;
}

// Insert an element to the end of the list
public void add(E e) {
    this.add(e, this.size);
}

// Add elements to the list header
public void addFirst(E e) {
    Node<E> node = new Node<>(e, null);    // Node object
    node.next = this.head;
    this.head = node;
    this.size++;
}
Copy the code
5. Delete single linked lists

Let the node of the storage element AI be q. In order to delete node Q from the single linked list, the pointer of its predecessor node is actually bypassing and pointing to its successor node, as shown in the following figure:

The q = p – > next; P – > next = q – > next. That is to say, change the successor of P to the successor of P.

Example: a family of three, mother (node P)-> father (node Q)-> daughter (node R), hand in hand shopping. Suddenly a beautiful woman appeared, and dad was petrified. The mother was very angry, threw away the father’s hand, and pulled away the father holding her daughter’s hand, took her daughter away.

The algorithm idea of the i-th data deletion node of single linked list:

  1. Declare a pointer p to the linked list header and initialize j from 1;
  2. When j< I, the list is traversed, so that the pointer to P moves backwards to the next node, and j accumulates by 1;
  3. If p is empty at the end of the list, the ith node does not exist.
  4. Otherwise, the search succeeds, and the node to be deleted p->next is assigned to q;
  5. P ->next=q->next;
  6. Assign the data in node Q to e as return;
  7. Release q.
// Delete the linked list element
public E remove(int index) {
    if (head == null) {
        return null;
    }
    // Delete the header
    if (index == 0) {
        head = head.next;
        this.size--;
        return head == null ? null : head.data;
    }
    Node<E> p = this.head;
    int j = 1;
    // Find the previous node to delete the node
    while(p ! =null && j < index) {
        p = p.next;
        ++j;
    }
    if (p == null || j > index) {
        return null;
    }
    // Delete node q
    Node<E> q = p.next;
    final Node<E> next = q.next;
    final E e = q.data;
    // Assign the successor of q to the successor of p
    p.next = next;
    //help gc
    q.data = null;
    q.next = null;
    // return the data in node q
    return e;
}
Copy the code

By analyzing the insertion and deletion algorithms we just explained, we find that they are actually composed of two parts: the first part is to traverse to find the ith node; The second part is inserting and deleting nodes.

From the whole algorithm, it can be deduced that their time complexity is O(n). If we do not know the pointer position of the ith node, the single-linked list data structure does not have much advantage over the sequential storage structure of the linear list in insert and delete operations. But if we want to insert 10 nodes from the ith position, for sequential storage, that means that we have to move n minus I nodes every time we insert, order n every time. Singly linked lists, we just need to find the ith position pointer the first time, which is O(n), and then simply move the pointer by assignment, which is O(1). Obviously, the more frequently data is inserted or deleted, the greater the efficiency advantage of singly linked lists.

Advantages and disadvantages of single – linked list and sequential storage

A simple comparison between a single-linked list and a sequential storage structure:

Storage allocation mode Time performance Space performance
1. Sequential structure stores the data elements of a linear table in a sequence of contiguous storage units;

2. Single linked list adopts chain storage structure, with a group of arbitrary storage units to store the elements of a linear list.		 1. Look for

Order structure O(1);

Single linked list O(n).

2. Insert and delete

The sequential structure requires an average move of half the length of the table, O(n);

A singly linked list is only O(1) when inserted and deleted after finding a pointer to a location.		 1. The sequential structure needs pre-allocated space, which is easy to overflow if it is divided into large and small parts;

2. Single-linked lists do not need to allocate storage space, and can be allocated as long as there is no limit on the number of elements.

Conclusion:

  • If the linear table needs to be searched frequently and insertion and deletion operations are seldom performed, the sequential storage structure is recommended. If frequent insertions and deletions are required, the single-linked list structure is recommended. For example, in game development, the personal information registered by users is read in most cases except the data inserted during registration, so the sequential storage structure should be considered. The list of weapons or equipment in the game can be added or deleted at any time as the player plays, so sequential storage is not appropriate, and single linked list structure can be useful. Of course, this is a simple analogy, but in real software development, the issues to consider are much more complex.
  • When the number of elements in a linear table varies greatly or the size of the elements is unknown, it is best to use a single-linked list structure, so that the size of the storage space does not need to be considered. The sequential storage structure is much more efficient if the approximate length of a linear table is known in advance, such as 12 months in a year and a week consisting of seven days from Monday to Sunday.

References:

Big Talk Data Structure cheng Jie