Three elements of data structure

1） Logical structure   It refers to the logical relationship between data , It's not about data storage , Independent of the computer . It can be divided into linear structure and nonlinear structure

• Linear structure ： The linear table , Stack , queue , strand , Arrays and generalized tables
• Nonlinear structure ： Trees , chart , aggregate

2） Storage structure   Is a storage image of a logical structure , Is the expression of the relationship between data in the computer . It also becomes a physical structure . It is divided into 4 class ： Sequential storage , Chain store , Index storage and hash storage

• Sequential storage ： Store logically adjacent elements in storage units that are also physically adjacent
• Chain store ： Adjacency to physical location is not required , The logical relationship between elements is represented by a pointer indicating the storage address of the element
• Index storage ： While storing element information , Add additional index tables , Operate on nodes through indexes
• Hash store ： Also known as Hash Storage , According to the key words of the node, the storage address of the node is calculated by hash function

The same logical structure can be realized by different storage structures in the computer . For example, linear structure in logical structure , You can use arrays （ Sequential storage ） Or one-way linked list （ Linked storage ） To achieve .

3） Data operation ： An operation applied to data （ Including definition and implementation ）. Operations are defined for logical structures , The implementation of operation is aimed at the physical structure

2. Definition of linear table

Linear table definition ：

• With the same data type n A finite sequence of data elements
• A linear table is a logical structure , Represents the one-to-one logical relationship between elements

Using linear tables to store data can be understood in this way , String all the data in one line , And then store it in physical space

The following figure , On the left is “ strand ” Up data , On the right is the free physical space . Put this “ A string of ” Place data in physical space , We can choose the following two ways ：

Will have “ one-on-one ” The data of the relationship “ linear ” To store in physical space , This kind of storage structure is called linear storage structure ：

• ①  The order sheet （ As shown in the picture above on the left ）： Store the data in a continuous physical space in turn
• ②  Linked list （ As shown on the right side of the picture above ）： The data is scattered in the physical space , The logical relationship between them is preserved through a line Single chain list Double linked list Circular single chain table Circular double linked list

These two storage structures are explained in detail below

3. The order sheet

① Sequence table definition

Sequential storage of linear tables . Two logically adjacent elements are also physically adjacent

Array It's a sequence table , Subscripts generally start from 0 Start ：

The characteristics of the sequence table ：

• Random access （ Through the first address and element serial number can be in time O(1) Element found inside ）
• Inserting and deleting requires moving a large number of elements
• High storage density , Each node only stores data elements

② Basic operation of sequence table

Insert

In the array a Of the i A place ( Subscript i-1) Insert elements e

//  The first i Move elements and subsequent elements back 
for (int j = a.length; j >= i; j--)
    a[j] = a[j - 1];
a[i - 1] = e;
length++;

• The best situation ： Insert... At the end of the watch , Time complexity O(1)
• The worst ： Insert... In the header , Time complexity O(n)
• On average ： Time complexity O(n)

Delete

Delete array a Of the i Elements of position

//  From  i  Move a position element forward 
for(int j = i; j < a.length; j++) 
    a[j-1] = a[j];
length --;

• The best situation ： Delete the footer element , Time complexity O(1)
• The worst ： Delete header element , Time complexity O(n)
• On average ： Time complexity O(n)

Ⅲ According to the value lookup

Find array a The median is e The subscript of the element

for (int i = 0; i < a.length; i++)
    if (a[i] == e)
        return i;

• The best situation ： Find the element in the header , Time complexity O(1)
• The worst ： Find the element at the end of the table , Time complexity O(n)
• On average ： Time complexity O(n)

4. Linked list

① Definition and structure of linked list

Chain storage of linear table . Two logically adjacent elements are not necessarily adjacent in physical location

for example , Using linked list storage {1,2,3}, The physical storage status of data is shown in the figure below ：

You can see , The above figure can not reflect the logical relationship between the data . Regarding this , The solution to the linked list is , Each data element is stored with a The pointer , Used to point to its own direct successor element . As shown in the figure below ：

Of course , Pointers can point to their immediate successor elements , You can also point to your own direct precursor element . So , Linked lists can be divided into ：

• Single chain list （ The pointer points to its immediate successor element ）
• Double linked list （ The pointer points to its own direct successor element and direct precursor element ）
• Circular single chain table （ The pointer points to its immediate successor element , The pointer of the footer node points to the header node ）
• Circular double linked list （ The pointer points to its own direct successor element and direct precursor element , The pointer of the footer node points to the header node ）

Through the above, you should also know , The storage of each data in the linked list consists of the following two parts ：

• Data fields ： The data element itself
• Pointer to the domain ： Point to the immediate successor of this element / Forerunner /... Pointer to element

The structure shown in the above figure is called... In the linked list node . in other words , The linked list actually stores nodes one by one , The real data elements are contained in these nodes , Take an example of a single linked list ：

Of course , The linked list structure shown above is not complete . A complete linked list needs to be composed of the following parts ：

• The head pointer ： An ordinary pointer , It is characterized by always pointing to the position of the first node in the linked list . Obviously , The header pointer is used to indicate the position of the linked list , It is convenient to find the linked list and use the data in the list later
• node ： The nodes in the linked list are divided into header nodes 、 First element node and other nodes   Head node ： In fact, it is an empty node without any data , Usually as the first node of the linked list . For a linked list , The header node is not required , Its function is only to facilitate the solution of some practical problems   Primary node ： Because the head node （ That is, an empty node ） Why , In the linked list, the first node with data is called the first meta node . The first element node is just an appellation for the first data node in the linked list , Used to distinguish from the head node , No practical significance   Other nodes ： Other nodes in the linked list

therefore , A store {1,2,3} The complete single linked list structure is shown in the figure ：

Advantages of introducing head node ：

• The operation of the first element node of the linked list is the same as that of the elements in other locations , No special treatment is required
• Whether the list is empty or not , Its head pointer refers to the non null pointer to the head node , The processing of empty and non empty tables has been unified

② Single chain list

Ⅰ Definition

A single linked list is a linked list that points to its direct successor elements

With Java For example , We customize a single linked list structure ：

public class Node{
    private T t;
    private Node next;
    ......
}

Single linked list can solve the disadvantage that sequential table needs a lot of continuous storage space , But a single linked list has a pointer field , There are also disadvantages of wasting storage space

Single linked list is a non random storage structure ： That is, the node of a feature in the table cannot be found directly . You need to traverse from the beginning .

The time complexity of single linked list access precursor is O(n), Visit successor O(1)

Ⅱ Basic operation

The first interpolation

At the head node L Insert node after s, namely s Node becomes the first node of the current linked list

The reading order of header interpolation is opposite to the generation order

s.next = L.next;
L.next = s;

The tail interpolation

At the last node of the linked list r Insert node after s, namely s The node becomes the last node in the current linked list

The reading order of tail interpolation is the same as that of generation

r.next = s;
r = s; // s  The node becomes the last node in the linked list 

Insert node

p Insert after the node s node

s.next = p.next;
p.next = s;

Delete node

p Delete after node q node

//  Delete  p  After that  q 
q = p.next;
p.next = q.next;

③ Double linked list

Ⅰ Definition

A double linked list is a linked list with both a precursor pointer and a successor pointer

The time complexity of accessing the predecessor and successor nodes of the double linked list is O(1)

With Java For example , We customize a double linked list structure ：

public class Node{
    private T t;
    private Node next;
    private Node prior;
    ......
}

Ⅱ Basic operation

Insert node

p Insert after the node s node

Above picture 2、3 The order can be changed

s.next = p.next;
p.next.prior = s;
p.next = s;
s.prior = p;

Delete node

Delete p After the node s node

p.next = s.next;
s.next.prior = p;

③ Circular single chain table

Circular single linked list is The pointer of the tail node points to the single linked list of the head node

Air condition ： End of table node next Whether it is equal to the head pointer

④ Circular double linked list

Circular double linked list is The pointer of the end node points to the double linked list of the head node

5. The comparison between sequential list and linked list

1） Access method

• A sequence table can be accessed sequentially , It can also be accessed randomly
• A linked list can only access elements sequentially from the header

2） Logical structure and physical structure

• When storing in sequence , Logically adjacent elements , The corresponding physical storage locations are also adjacent
• Chain storage , Logically adjacent elements , Physical storage locations are not necessarily adjacent , Its logical relationship is represented by pointer Links

3） lookup 、 Insert and delete operations

• For find by value , When the order table is out of order , The time complexity of both is O(n); When the sequence table is ordered , You can use half to find , The time complexity is O(log2n) For searching by serial number , Sequential tables support random access , Time complexity is only O(1), The average time complexity of the linked list is O(n).
• Insertion of sequence table 、 Delete operation , On average, you need to move half a table length element Insertion of linked list 、 Delete operation , You only need to modify the pointer field of the relevant node . Because each node of the linked list has a pointer field , Therefore, the cost of storage space is higher than that of sequential table , The storage density is not large enough .

4） Space allocation

• Sequential storage is in the case of static storage allocation , Once the storage space is full, it cannot be expanded , If you add new elements , Overflow occurs , So we need to allocate enough storage space in advance . The pre allocation is too large , It may lead to a large number of idle sequence table candidates ; Preassigned too small , It's going to cause spillovers . Dynamic storage allocation, although the storage space can be expanded , But you need to move a lot of elements , Resulting in reduced operating efficiency , And if there is no more continuous storage space in memory , This will lead to allocation failure
• The linked list only applies for allocation when needed , Efficient and flexible