A finite sequence of N data elements of the same data type

The sequential representation of a linear table

define

The sequential storage of linear tables is also called sequential tables. It uses a set of contiguous locations to store data elements in a linear table in turn, so that two elements that are logically adjacent are also physically adjacent. The first element is stored at the beginning of the linear table, and the ith element is immediately followed by the ith + 1 element. Therefore, the characteristic of a sequential table is that the logical order of the elements in the table is the same as their physical order.

    #define MaxSize 50 // Define the maximum length of the linear table

    typedef struct {
        ElemType data[MaxSize]; // Order the elements of the table
        int length; // The current length of the order table

    }
    SqList; // The type definition of the order table
Copy the code

The most important features of the order table are:

  • Random access, that is, the first address and element sequence number can be found in O(1) time to specify the element.
  • The storage density of order table is high, and each node only stores data elements.
  • Elements that are logically adjacent to each other in a sequential table are also physically adjacent, so insertion and deletion operations need to move a large number of elements.

implementation

The insert

Insert the new element e at position I (1 <= I <= L.length+1) of the order table L. If I is invalid, false is returned, indicating that the insertion failed. Otherwise, move the ith element and all subsequent elements one position to the right, leaving an empty position and inserting a new element e, increasing the length of the order table by 1, and returning true on success.

    bool ListInsert(SqList & L, int i, ElemType e) {
        // This algorithm implements the insertion of element E into the i-th position in the order table L
        if (i < 1 || i > L.length + 1) { // Determine whether the range of I is valid
            return false;
        }
        if (L.length >= MaxSize) { // The current storage space is full and cannot be inserted
            return false;
        }
        for (int j = L.length; j >= i: j--) { // Move the ith element and the elements after it backward
            L.data[j] = L.data[j - 1];
        }
        L.data[i - 1] = e; // Put e at position I
        L.length++; // Add the length of the linear table by 1
        return true;
    }
Copy the code

Therefore, the average time complexity of linear table insertion algorithm is O(n).

Delete operation

Delete the ith (1 <= I <= L length) element in the order L, return true on success and return the deleted element with the reference variable e, false otherwise.

    bool ListDelete(SqList & L, int i, int & e) {
        // This algorithm is implemented to delete the element of the I position in the order table L
        if (i < 1 || i > L.length) { // Determine whether the range of I is valid
            return false;
        }
        e = L.data[i - 1]; // Assign the deleted element to e
        for (int j = i; j < L.length; j++) { // Move the elements after the ith position forward
            L.data[j - 1] = L.data[j]
        }
        L.length--; // Subtract 1 from the length of the linear table
        return true;
    }

Copy the code

Search by value (sequential search)

Look in order table L for the element whose first element value is equal to e and return its order.

    int LocateElem(SqList L, ElemType e) {
        // This algorithm implements the search order table of the element value e, if the search is successful, return the element order, otherwise return 0
        int i;
        for (i = 0; i < L.length; i++) {
            if (L.data[i] == e) {
                return i + 1; // Return the order I + 1 for the element whose subscript I is equal to e
            }
            return 0; // Exit the loop, indicating that the search failed}}Copy the code

A chain representation of a linear table

Because the insertion and deletion of sequential table need to move a large number of elements, which affects the operation efficiency, the chain storage of linear table is introduced. Chain store linear table, do not need to use the address continuous storage unit, i.e. it does not require logically adjacent elements on the physical location is adjacent, it is through the “chain” to establish the logical relationship between data elements, therefore, linear table insert, delete, do not need to move the elements, but only need to modify the pointer.

Definition of a singly linked list

Linear table chain storage is also called a single list, it refers to a set of arbitrary storage units to store the data elements in the linear table. In order to establish a linear relationship between data elements, each linked list node needs to store not only the information of the element itself, but also a pointer pointing to its successor. The node structure of the single linked list is shown in the following figure, where data is the data domain, storing data elements; Next is a pointer field that stores the addresses of subsequent nodes.

Typedef struct LNode {// Define the node type of the single linked list

        ElemType data; / / data domain

        struct LNode * next; / / pointer field

    }
    LNode, * LinkList;
Copy the code

The single linked list can solve the problem that the sequential list needs a large amount of continuous storage space, but the single linked list also has the disadvantage of wasting storage space with the addition of pointer field. Because the elements of a singly linked list are distributed discreetly in the storage space, the singly linked list is a non-random access storage structure, that is, it cannot directly find a specific node in the table. To find a particular node, you need to go through it from the beginning and look it up.

A singly linked list is identified by a “head pointer”, such as singly linked list L. If the head pointer is NULL, it indicates an empty table. In addition, for the convenience of operation, a node is attached before the first node of the singly linked list, called the head node. Header node data field does not set any information, can also record the table length and other related information. The pointer field of the head node points to the first element node of the linear table,

Single linked list of basic operation implementation

  1. The single linked list is established by head insertion method
  2. The single linked list is established by tail interpolation method
  3. Find node values by ordinal number
  4. Find nodes by value
  5. Insert node operation
  6. Delete node *p
  7. Table length operation

Double linked list

There is only one pointer to the node of a singly linked list, which makes the list only go backwards from the node to the node from the beginning. If you want to access the precursor (insert, delete) of a certain node, you can only start from the beginning. The time complexity of accessing the successor node is O(1), and the time complexity of accessing the precursor node is O(n).

In order to overcome the deletion defect of single linked list, double linked list is introduced. There are two Pointers prior and next in the node of double linked list, pointing to its predecessor and successor respectively. As shown in the figure below:

The double-linked list simply adds a prior pointer to the node of the single-linked list. Therefore, the lookup by value and the lookup by bit are performed in the double-linked list as in the single-linked list. But the double linked list in the implementation of insert and delete operation, and single linked list has a big difference. This is because the prior pointer needs to be changed when the chain changes, and the key is to ensure that the chain is continuously chained during the change. In addition, the precursors of the double-linked list can be found in many aspects, so the time complexity of the node insertion and deletion algorithm is O(1).Copy the code

In the operation of establishing double linked list, you can also use the head insert method and the tail insert method as the single linked list, but the operation needs to pay attention to the change of pointer and the single linked list is different.

Circular linked list

  1. Circular single linked list

The difference between circular singly linked list and singly linked list is that the last node pointer in the list is not NULL, but instead points to the head node, so that the whole list forms a loop.

  1. Circular double linked list

From the definition of a cyclic single linked list, it is not difficult to derive a cyclic double linked list. The difference is that in a cyclic double linked list, the prior pointer to the head node also points to the tail node.

Comparison of sequential list and linked list

  1. Access mode

    Sequential tables can be accessed sequentially or randomly, while linked lists can access elements sequentially only from the header.Copy the code

  2. Logical structure and physical structure

    When sequential storage is used, elements that are logically adjacent are also stored in adjacent physical locations. In the case of chain storage, the physical storage locations of logically adjacent elements are not necessarily adjacent, and the corresponding logical relationship is represented by pointer link. Please note the difference between access mode and storage mode.Copy the code

  3. Find, insert, and delete operations

    For search by value, when the order table is unordered, the time complexity of both is O(n). When the order table is ordered, the split search can be used, and the time complexity is O(). For search by sequence number, the order table supports random access and the time complexity is O(1), while the average time complexity of the linked list is O(n). The insertion and deletion operations of sequential tables need to move an element half a table length on average. The operation of insertion and deletion of linked list only needs to modify the pointer field of related nodes. Because each node of the linked list has a pointer field, the storage space is more expensive than that of sequential storage, and the storage density is not large enough.Copy the code

  4. Space allocation

    In the case of static storage allocation, sequential storage cannot be expanded once the storage space is full. If new elements are added, memory overflow will occur. Therefore, sufficient storage space needs to be allocated in advance. Pre-allocation is too large, may lead to a large number of idle at the back of the order table; Pre-allocation is too small, and will cause overflow. Dynamic storage allocation Although the storage space can be expanded, a large number of elements need to be moved. As a result, the operation efficiency is reduced. In addition, if there is no larger contiguous storage space in the memory, the allocation fails. The node space of chain storage is allocated only when needed. As long as there is memory space, it can be allocated. The operation is flexible and efficient.Copy the code

————— how to select the storage structure in practice?

1. Based on the consideration of storage, it is not suitable to use the sequential table when it is difficult to estimate the length or storage scale of the linear table; The list does not need to estimate the storage size in advance, but the storage density of the list is low, apparently the storage density of the list storage structure is less than 1. 2. Consideration based on operation: The time complexity of accessing a (I) by sequence number in the sequential list is O(1), while the time complexity of accessing a (I) by sequence number in the linked list is O(n). Therefore, if the operation often done is accessing data elements by sequence number, it is obvious that the sequential list is better than the linked list. When inserting or deleting a sequential table, half of the elements in the table are moved on average. This should not be ignored when the information of data elements is large and the table is long. In the list to do the insert, delete operation, although also need to find the insert position, but the operation is relatively simple, from this point of view, the latter is obviously better than the former. 3. Context-based order lists are easy to implement, and array types are available in any high-level language; The operation of linked lists is based on Pointers, which is relatively easy to implement, which is also a factor for users to consider. In short, each of the two storage structures has its own advantages and disadvantages, and the choice of which is determined by the major factors of the practical problem. Generally, the stable linear table should be stored sequentially, while the frequent insertion and deletion of the linear table (that is, strong dynamic) should be stored chained.Copy the code