1. Three elements of data structure

1) Logical structure refers to the logical relationship between data, which has nothing to do with data storage and is independent of computers. It is divided into linear structure and nonlinear structure

  • Linear structures: linear tables, stacks, queues, strings, arrays, and generalized tables
  • Nonlinear structure: tree, graph, set

2) The storage structure is the storage image of the logical structure, which is the representation of the relationship between data in the computer. It also becomes a physical structure. It is divided into four categories: sequential storage, chain storage, index storage and hash storage

  • Sequential storage: Storing logically adjacent elements in physically adjacent locations
  • Chain storage: Physical proximity is not required. Logical relationships between elements are represented by Pointers indicating where they are stored
  • Index storage: In addition to storing element information, additional index tables are added to perform operations on nodes through indexes
  • Hash storage: Also called Hash storage, the storage address of a node can be calculated using the Hash function based on the keyword of the node

The same logical structure in a computer can be implemented using different storage structures. For example, linear structures in logical structures can be implemented using arrays (sequential storage) or one-way linked lists (linked storage).

3) Data operations: operations applied to data (including definition and implementation). Operations are defined for logical structures and implemented for physical structures

2. Definition of linear tables

Linear table definitions:

  • A finite sequence of n data elements of the same data type
  • A linear list is a logical structure that represents a one-to-one logical relationship between elements

The way to store data in a linear table is to string all the data together on a string and store it in physical space

In the figure below, data is “strung” on the left and free physical space is on the right. To place this “bundle” of data into physical space, we can choose one of two ways:

Data with one-to-one relationship is stored “linearly” in physical space. This kind of storage structure is called linear storage structure:

  • ① Sequence table (as shown on the left side of the figure above) : The data is sequentially stored in a continuous whole physical space
  • 2.The list(Right) : Data is distributed in physical space, with a thread holding the logical relationship between them
    • Singly linked lists
    • Double linked list
    • Circular singly linked lists
    • Circular double-linked lists

These two storage structures are explained in detail 👇

3. The order sheet

① Order table definition

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

Arrays are ordered tables with subscripts starting at 0:

Sequence table features:

  • Random access (elements can be found in time O(1) by starting address and element number)
  • Insertion and deletion require moving a large number of elements
  • High storage density, each node stores only data elements

② Basic operation of sequence table

Ⅰ insert

Inserts element e at position I (subscript i-1) of array A

// The ith element and the elements after it move back
for (int j = a.length; j >= i; j--)
    a[j] = a[j - 1];
a[i - 1] = e;
length++;
Copy the code

  • Best case: Insert at the end of the table, time complexity O(1)
  • Worst case: Insert in table header, time complexity O(n)
  • Average case: Time complexity O(n)

Ⅱ delete

Deletes the element in position I of array A

// Move forward from the ith position element
for(int j = i; j < a.length; j++) 
    a[j-1] = a[j];
length --;
Copy the code

  • Best case: Drop table end element, time complexity O(1)
  • Worst case: Delete header element, time complexity O(n)
  • Average case: Time complexity O(n)

ⅲ Search by value

Find the index of the element e in array A

for (int i = 0; i < a.length; i++)
    if (a[i] == e)
        return i;
Copy the code
  • Best case: find element in table head, time complexity O(1)
  • Worst case: lookup element at end of table, time complexity O(n)
  • Average case: Time complexity O(n)

4. List

The definition and structure of linked list

Chain storage of linear lists. Two elements that are logically adjacent are not necessarily physically adjacent

For example, if a linked list is used to store {1,2,3}, the physical storage state of the data is as follows:

As you can see, the diagram does not show the logical relationship between the data at all. The solution to this is that each data element is stored with a pointer to its immediate successor. As shown below:

Of course, Pointers can point to their immediate successors as well as to their immediate precursors. To this end, linked lists can be divided into:

  • Single linked lists (Pointers to their immediate successors)
  • Double-linked lists (Pointers to their immediate successors and immediate precursors)
  • Circular singly linked lists (Pointers to their immediate successors, and Pointers to the table’s tail nodes to the head node)
  • Circular double-linked lists (Pointers to their immediate successors and immediate precursors, and Pointers to the end nodes to the head nodes)

As you know from the above, the storage of each data in the linked list consists of the following two parts:

  • Data field: The data element itself
  • Pointer field: refers to the element’s immediate successor/precursor /… Pointers to elements

The structures shown above are called nodes in linked lists. In other words, linked lists actually store nodes one by one, and the real data elements are contained in these nodes. For example, a single linked list:

🚨 Of course, the linked list structure shown above is not complete. A complete linked list should consist of the following parts:

  • Head pointer: A normal pointer that always points to the first node in the list. Obviously, the header pointer is used to indicate the location of the linked list so that it can be found and used later
  • node: The nodes in the linked list are divided into head nodes, head nodes and other nodes
    • Head node: An empty node that holds no data, usually the first node in a linked list. The head node is not necessary for linked lists, it is just a convenience for solving practical problems
    • Head node: Because of the head node (that is, the empty node), the first node that holds data is called the head node. The header node is just a name for the first data node in the linked list, which is used to distinguish it from the header node and has no practical significance
    • Other nodes: Other nodes in the linked list

Thus, a complete single-linked list structure that stores {1,2,3} looks like this:

💡 Introduces the advantages of the header node:

  • Operations on the first element of the list are the same as operations on other elements without special treatment

  • No matter whether the linked list is empty or not, its head pointer is a non-null pointer to the head node, and the treatment of empty table and non-empty table is unified

(2) the singly linked list

Ⅰ definition

A singly linked list is a list with Pointers to its immediate successors

In Java, for example, we define a single linked list structure:

public class Node{
    private T t;
    privateNode next; . }Copy the code

Single-linked lists can solve the problem that sequential lists need a lot of continuous storage space, but single-linked lists also have the disadvantage of wasting storage space with pointer fields

A singly linked list is a non-random storage structure: it is not possible to find a specific node in the table directly. You have to start from scratch.

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

ⅱ Basic Operations

The first interpolation

Insert node S after the head node L, that is, s node becomes the first member node of the current linked list

The read order of the header interpolation method is reversed from the generate order

s.next = L.next;
L.next = s;
Copy the code
The tail interpolation

Insert node S after the last node R in the list, that is, s node becomes the last node in the current list

The read order of the tail interpolation method is the same as the generate order

r.next = s;
r = s; // the s node becomes the last node in the list
Copy the code
Insert the node

After the p node, the S node is inserted

s.next = p.next;
p.next = s;
Copy the code
Remove nodes

After the p node, delete the Q node

// delete q after p
q = p.next;
p.next = q.next;
Copy the code

(3) double linked list

Ⅰ definition

A doubly linked list is one that has both a precursor and a successor

Double linked list access to both the precursor and the successor is O(1)

In Java, for example, we define a double-linked list structure:

public class Node{
    private T t;
    private Node next;
    privateNode prior; . }Copy the code

ⅱ Basic Operations

Insert the node

After the p node, the S node is inserted

The order of 2 and 3 in the figure above can be reversed

s.next = p.next;
p.next.prior = s;
p.next = s;
s.prior = p;
Copy the code
Remove nodes

Delete s node after p node

p.next = s.next;
s.next.prior = p;
Copy the code

③ Circular singly linked list

A cyclic singly linked list is one where the pointer to the last node points to the first node

Null condition: whether next at the end of the table is equal to the head pointer

④ Circular double-linked lists

A circular double-linked list is one in which the pointer to the last node points to the first node

5. Comparison of sequential and linked lists

1) Access mode

  • Sequential tables can be accessed sequentially or randomly
  • Linked lists can only access elements sequentially from the table header

2) Logical structure and physical structure

  • In sequential storage, logically adjacent elements are stored in adjacent physical locations
  • In chained storage, the logical relationship between logically adjacent elements may not be physically adjacent, but is represented by pointer links

3) Find, insert, and delete operations

  • For search by value, the time complexity of both is O(n) when the order table is out of order. When the order list is in order, the split search can be adopted, and the time complexity is O(log2n).

    For ordinal lookups, sequential tables support random access with a time complexity of only O(1), while linked lists have an average time complexity of O(n).

  • On average, the insertion and deletion operations of a sequential table need to move an element half the length of the table

    To insert and delete linked lists, only the pointer fields of related nodes need to be modified. Because each node of a linked list has pointer fields, the cost of storage space is higher than that of a sequential list, and the storage density is not large enough.

4) Space allocation

  • Sequential storage In the case of static storage allocation, once the storage space is full, it cannot be expanded. If new elements are added, it will overflow. Therefore, sufficient storage space must be allocated in advance. If the pre-allocation is too large, it may lead to a large number of idle sequential table candidates. Too small pre-allocation, and will cause overflow.

    Dynamic storage allocation Although the storage space can be expanded, a large number of elements need to be moved, resulting in low operation efficiency. Moreover, if there is no more contiguous storage space in memory, the allocation fails

  • Linked lists are only allocated when needed, efficient and flexible

💡 This article is included in Gitee Repository Cs-Wiki gitee.com/veal98/CS-W… (officially recommended project, 0.8K Star), welcome to Star!