Here we will only cover sequential and linked lists with different storage structures in linear tables, as well as stacks and queues with limited operation.

Data Structures and Algorithms Series of articles Data Structures and Algorithms – Time complexity data structures and Algorithms – linear tables

directory

3. Linked list 3.1, Linear linked list (single linked list) 3.1.1, Inserted element 3.1.2, Deleted element 3.2, Cyclic linked list (one-way) 3.3, Bi-directional linked list 3.4, bi-directional cyclic linked list 3.5 features of linked list 4. Stack 4.1, sequential stack 4.2, chain stack 5. Queue 5.1, sequential queue 5.2, chain queue

An overview,

Linear table is one of the simplest and most commonly used data structures with linear structure. A Linear List is a finite sequence of data elements with the same properties. Its elements can be simple data such as integers and characters, compound forms composed of multiple data items, or even a page of a book or other more complex information. For example, an alphabet of 26 capital English letters (A, B, C… , x, Y, Z) is a linear table in which each data element is a capital letter. Another example is the number of teachers with titles above associate professor in a university since 1990 (48,64,77,93,112,136,167… ,235) is also a linear table in which each data element is a positive integer. Both linear tables are examples of simple data elements. The data elements in a linear table can have various forms. However, for the same linear table, the data elements must have the same form, that is, the data elements in the same linear table must belong to the same set of data objects, and there is some order even relationship between the adjacent data elements in the table.

Linear structure features: in a non-empty finite set of data elements, there exists a unique data element called “the first” (head node); There is a unique “last” data element (endpoint); each data element in the set, except the first, has only one immediate precursor; Every data element in the collection except the last has only one immediate successor.

Second, the order table

A sequential table is a linear table in which data elements in a linear table are sequentially stored in a set of storage cells with contiguous addresses. Because this approach is consistent with the representation and implementation of one-dimensional arrays in high-level programming languages, it is also called array representation. Linear table in a sequential table said, logical location adjacent data elements will be stored in the table to the memory of the physical address of the adjacent storage unit, the logic relation of elements in the table are in conformity with sequential (physical), in other words, the order of the logical relationship is based on the data elements in the table in the physical storage structure (location). Therefore, in a sequential table, any element in the table can be randomly accessed according to the bit order of the data elements in the sequential table, that is, the sequential table is a random access storage structure.

  • 2.1 Insertion of sequence table

Order table insert table refers to the order of the first I – 1 between elements and the element I insert a new element, order at this time the logical relationship between before and after the insertion position in the table element changes, so unless the insert position is the current after the last element in the table, otherwise must move data element by sequential storage location to achieve. The schematic diagram of the insertion process is shown in the figure below:

The time consumption of sequential list insertion algorithm is mainly the movement of elements, and the number of moving elements depends on the insertion position. In the best case, insert at the end of the sequence table without moving elements; The worst case is to insert in the first place and move n elements. In order to insert an element before position I of the sequence table with length N, it is necessary to move N-i +1 element, and there can be N +1 insertion position. Under the condition of equal probability of insertion position, the average number of moves of an element is 1/(n+1)*∑(n-I +1)= N /2. Therefore, the time complexity of the algorithm is O(n). Note: ∑(n- I +1) means that the subscript is I =1 and the superscript is n+1.

  • 2.2. Delete the sequence table

A sequential table deletion is similar to an insert in that all elements stored after the deleted element are moved. The process is shown in the figure:

Like the insert algorithm, the time of the delete algorithm is mainly spent on the movement of elements. In the best case, the delete position is at the end of the order table without moving elements; In the worst case, the deletion location is the first element, and n-1 elements need to be moved. To delete an element at position I of a sequence table with length N, n-I elements need to be moved. Under the condition of equal probability of deleting positions, the average number of moves of deleting an element is 1/ N *∑(n-i)=(n-1)/2, so the time complexity of the algorithm is O(n). Note: ∑(n- I) denotes the sum of subscripts I =1 and superscripts n+1.

  • 2.3. Characteristics of sequence table

A sequence table is characterized by “adjacent storage locations” to indicate the precursor and successor relationship between two elements. The advantage of a sequential table is that you can randomly access any element in the table. Its main disadvantage is the waste of storage space; The second is that, on average, half of the elements in the table must be moved each time an insert or delete is performed. As a result, sequential tables are often used primarily for linear tables that do little insert and delete for queries and have little change in table length.

Three, the linked list

The so-called linked list refers to the linear list represented and realized by the chain storage structure. A linked list is characterized by the use of an arbitrary set of storage units, which can be continuous or discontinuous, to store the data elements in a linear list. In linked lists, the logical relationships between data elements are not dependent on their corresponding storage addresses, but are described by setting Pointers specifically to indicate the logical relationships between data elements. Therefore, each data element in the linked list is composed of two parts: the data domain which is used to store information representing itself and the pointer domain which is used to store the logical relationship between data elements. This special storage mode of data elements is called Node. According to the contained in the linked list node number, pointer to a pointer to the pointer domain and connections, the list can be divided into linear list, circular linked list, two-way chain table, multiple lists, curb table, binary, adjacency list and adjacency list multiple tables, etc., including linear list, circular linked list and two-way chain table used to implement the chain of the linear table storage structure, Other forms are used to implement extended linear structures (arrays and generalized tables, etc.) or nonlinear structures (trees, graphs, etc.).

  • 3.1 Linear Linked List (Single Linked List)

A linear linked list, also known as a single linked list, contains only one pointer in each node, which is used to indicate the direct successor node of the node. The whole linked list is connected by a pointer, and the pointer of the last node is set to NUll because there is no post-rally point. The schematic diagram of the structure is shown in the figure above.

3.1.1 Insertion of single linked lists

The insertion of a linear linked list refers to the insertion of a new node between the -1 node and the i-th node of the linear linked list. At this point, the logical relationship between the nodes before and after the insertion position in the linear linked list changes. Therefore, unless the insertion position is after the last node in the current table, Otherwise, you must change the pointer to both the node before the insertion position and the current insertion point. The insertion of linear linked list does not need to move elements, and the basic steps of the insertion algorithm are shown in the figure below: (1) Find the insertion position, that is, the position of the i-1 node. (2) Apply for node storage space and generate new nodes. (3) Modify the -1 node and the pointer field of the new node to link the new node in the linked list.

The time of linear linked list insertion algorithm is mainly spent on finding the insertion position. Nodes need to be visited successively from the linked list head pointer until the insertion position is found. Therefore, the time complexity of the algorithm is O(n).

3.1.2 Deletion of single linked list

The deletion of the linear linked list refers to the deletion of the ith node of the linear linked list. At this time, the logical relationship between the nodes before and after the deletion position in the linear linked list changes, so the pointer pointing of the node before the deletion position must be modified to achieve this goal. The deletion process is illustrated above. As with node insertion, the deletion process first finds the location of the node before the node to be deleted, and then completes the deletion by modifying the node pointer field. So the time complexity of the algorithm is also O(n).

  • 3.2 circular Linked Lists (One-way)

In a linear list, the pointer to the last node points to NULL, indicating the end of the linear list. If the pointer of the end node of the list is changed to point to the first node of the list, the whole linear list forms a closed loop, and this form of linear list connected head to tail is called circular list. The whole list is like a one-way circular bus route, and people can start from any station along the route to other stations along the route. The time complexity of insert and delete is also O(n). The storage structure of circular linked list is shown as follows:

  • 3.3. Bidirectional linked lists

If a pointer field is added to the node of a linear linked list to point to the direct precursor of the node, then from any node in the list, the successor of the node can be looked up backwards, and the precursor of the node can be looked up forwards. The entire linked list contains two chains that point to the precursor and the successor respectively, called a bidirectional linked list. The storage structure of bidirectional linked list is shown as follows:

  • 3.4. Bidirectional circular linked lists

If both of the two links in the bidirectional linked list form a closed loop, the bidirectional cyclic linked list is formed. Schematic diagram of the bidirectional circular linked list structure and the insert and delete process are shown below:

  • 3.5. Characteristics of linked lists

Linked lists are characterized by “Pointers” indicating subsequent elements, which can be stored in any set of storage units. Therefore, the advantage of linked list is that there is no need to estimate the size of linear list in advance, save storage overhead, and do insert, delete operations, no need to move elements; Its main disadvantage is that no matter the list is inserted, deleted or searched, it needs to start from the starting position of the list, and the list does not have random access characteristics.

Four, stack

Stack is a kind of constrained linear table operation, the above mentioned sequence table and linked list can be inserted on both ends of table and table delete operations, and the stack is only allowed in one end (stack) to insert the delete operation, which is in (into) stack and the stack operation, the stack is the only entrance, stack data read operation follow out (LIFO) after the “advanced” principle. For example, the navigation controller in Object-C is implemented with stack features.

According to the different storage structure, the stack can also be divided into sequential stack and chain stack.

  • 4.1. Sequential stack

Sequential stack storage, also known as sequential stack, uses a group of storage units with consecutive addresses to store the elements from the bottom of the stack to the top of the stack, with the top identifier to indicate the position of the elements at the top of the stack in the sequential stack. The schematic diagram of sequential stack loading and unloading operation is shown in the figure below:

  • 4.2, chain stack

The chain storage of stack is also called chain stack. It has the same storage principle as linked list. It can use idle space to store elements and use Pointers to establish logical relations between nodes. The chain also sets an identifier for the top element, called the top pointer. The schematic diagram of the operation structure of loading and unloading of chain stack is shown in the figure

Five, the queue

Queue is also a linear table with limited operation, but queue and stack are different, queue can only be inserted (queue) at one end (queue), delete (queue) at the other end (queue head), the operation follows the “first in, first out (FIFO)” principle. There is a pointer to the queue head called queue head pointer front. When an element exits the queue, the queue head pointer moves back to the next element, which becomes the new queue head element (similar to the top of the stack pointer). There will also be a pointer to the end of the queue, called rear, which is a null pointer after the last element. When an element needs to join the queue, it is inserted at the position indicated by the tail pointer. After insertion, the tail pointer moves back to the next empty space. When the queue is full, the element can no longer join the queue. Similarly, when the queue is empty, no queue operation can be performed.

Queue can also be divided into sequential queue and chain queue according to different storage structures.

  • 5.1. Sequential queues

Queues implemented using sequential tables are called sequential queues. The implementation of a sequential queue is similar to that of a sequential list, except that only inserts are allowed on one end and deletes are allowed on the other. Define two variables front and rear to identify the head and tail of the team respectively. When deleting the head element, front moves to the next position. When you insert a new element, you insert it at the position indicated by the rear, and when you insert it, the rear moves back to the next storage location. The queue access operation diagram of the sequential queue is as follows:

  • Note: queue “false overflow”

An “overflow” may occur in a sequential queue stored procedure. There are two types of “overflow”, one is true and the other is false. The so-called true “overflow” means that when the space allocated by the queue is full, the “overflow” will occur when the element is stored in the queue. This “overflow” means that there is no more space to store the element, which is the true “overflow”. A false overflow is an overflow that occurs when there is room in the queue. When the front end has an element out of the queue, the front moves backwards. When there is an element in the rear end joining the queue, the rear moves backward. If the rear has pointed to the position with the largest subscript in the queue, there is space in front of the front, but if there is an element joining the queue, there will also be an “overflow”, which is called “false overflow”, as shown in the diagram below. There are two ways to deal with fake overflow. One is to use the “move queue” method, that is, every time the queue out operation is performed, the queue head and the queue end pointer will be moved to the start of the array, always keep the queue head at the start of the array, the cost of this method is to produce a large number of element movement, obviously not a good method; Another method, which is more reasonable and efficient, is to use 5.2 circular queues.

  • 5.2. Circular queues

In order to solve the false “overflow” phenomenon in the sequential queue and make full use of the storage space of the array, the sequential queue can be connected to form a circular queue, which is generally implemented by the array. Imagine a circular queue as a circular space, as shown in the figure below. In a circular queue, both front and rear can move in a circular way. When the queue is empty, front=rear is established. Front =rear also holds when the team is full. So obviously you can’t tell if the team is empty or full just by front=rear. To solve this problem, there is a convention in the circular queue to use one less element of space, and the queue is full when the rear of the queue identifies the position above the front of the queue. In this case, the conditions are as follows: When the team is empty, front==rear is true. When the queue is full :(rear+1)% MAXSIZE== front is true (MAXSIZE is the size of the queue capacity). The movement of ront and rear in the circular queue is no longer simply incrementing by 1, because it is circular. Perhaps it originally meant at the end, and one unit forward is the beginning of another cycle, so each movement has to be modulo the queue capacity MAXSIZE: Front = (front +1)% MAXSIZE, rear = (rear+1)% MAXSIZE. And in a circular queue, it’s not just a matter of subtracting rear from ront, because rear might be smaller than front, so it’s negative, which is obviously not true. (Rear + MAXSIZE- front)% MAXSIZE (rear+ MAXSIZE- front)% MAXSIZE (rear+ MAXSIZE- front)% MAXSIZE

  • 5.3. Chain queue

The queue realized by linked list is also called chain queue. In the chain queue, Pointers front and rear are used to indicate the head and tail of the queue respectively, and elements are deleted at front and inserted at rear. Unlike sequential queues, chained queues have rear Pointers to the last element. The structure of chain queue and queue access operation diagram are as follows:

Note: all the pictures in this article are taken from the Internet