A linear table is a finite sequence of n data elements of the same data type

The number of elements in the table is limited

The elements in the table have a logical sequence. The elements in the table have their order.

The elements in the table are all data elements, and each element is a single element

The data types of the elements in the table are all the same, which means that each element occupies the same size of storage space

The elements in the table are abstract, that is, only the logical relationship between the elements is discussed, without considering what the elements actually represent.

InitList(&): Initialization list. Construct an empty linear table

Length(L): Find the length of the table. Returns the length of the linear table L, that is, the number of data elements in L

LocateElem(L,e): Find operation by value. Find elements in table L with given key value

GetElem(L,i): Bitwise search operation. Get the value of the element at position i in the table

ListInsert (&L,i,e): Insertion operation. Insert the specified element e at the i-th position in table L

ListDelete(&L,i,&e): Delete operation. Delete the element at the i-th position in the table and use e to return the value of the deleted element

PrintList(L): Output operation. Output all element values ​​of the linear table in sequential order

Empty(L): Empty operation. If the job is an empty table, return true, otherwise return false

DestroyList(&L): Destroy operation. Destroy the linear table and release the memory space occupied by linear table L

The sequential storage of a linear table uses a set of storage units with consecutive addresses to sequentially store the data elements in the linear table, so that two logically adjacent elements are also physically adjacent.

Features

（1） insert

（2） delete

（3） Find by value (sequential search)

Store data elements in a linear table through an arbitrary set of storage units

For each linked list node, in addition to storing the element's own information, it also needs to store a pointer to its successor.

Attach a node before the first node of the singly linked list, called the head node. Its data field does not contain any information, and the pointer points to the first element node of the linear list.

Create a singly linked list using head insertion method

Create a singly linked list using tail insertion method

Find node value by serial number

Find table nodes by value

Insert node operation

Delete node operation

Find table length operation

The time complexity of accessing the predecessor node of a single linked list is O(n). For this reason, a double linked list is introduced. Each node has two pointers, prior and next, pointing to its predecessor and successor nodes respectively.

insert operation

Delete operation

Circular singly linked list

Circular doubly linked list

Use arrays to describe the linked storage structure of linear lists

The pointer is the relative address of the node (array subscript), also known as the cursor

Use next==-1 as the end mark

Access (read and write) methods

Logical structure and physical structure

Find, insert and delete element operations

space allocation