The operation of a singly linked list, the structure of a singly linked list

A singly linked list is a chained access data structure that holds data elements in a linear table in a set of storage units with arbitrary addresses. The data in the linked list is represented by nodes, and each node is composed of: element (image of the data element) + pointer (indicating the storage location of the successor element), the element is the storage unit where the data is stored, and the pointer is the address data connecting each node.

Introduction to Singly Linked Lists.

1.Introduction to the concept.

The data in the linked list is represented by nodes, and each node is composed of: element (image of the data element) + pointer (indicating the storage location of the successor element), the element is the storage unit where the data is stored, and the pointer is the address data connecting each node.

A linear table represented as a "sequence of nodes" is called a linear linked list (singly linked list), and a singly linked list is a chained access structure.

2.Linked storage methods.

A linear table stored in linked mode is referred to as a linked list.

The specific storage of a linked list is expressed as:

Use an arbitrary set of memory cells to hold the nodes of a linear table (this set of cells can be either continuous or discontinuous).

The logical and physical order of the nodes in a linked list is not necessarily the same. In order to correctly represent the logical relationship between nodes, the value of each node must be stored along with the address (or location) information (called a pointer or link) indicating its successor node

Chained storage is one of the most commonly used storage methods, and it can be used to represent not only linear tables, but also various non-linear data structures.

3.Node structure.

data field - the data field where the node value is stored.

Next Domain - A pointer domain (chain domain) that stores the address (location) of the node's immediate successor

A linked list links the n nodes of a linear table together in a logical order through the chain domain of each node, and a linked list with only one chain domain for each node is called a single linked list.

Head pointer head and terminal node.

The storage address of each node in a singly linked list is stored in the next field of its predecessor node, and the starting node has no predecessor, so the head pointer should be set to point to the start node. A linked list is uniquely determined by the head pointer, and a single linked list can be named by the name of the head pointer.

There is no successor to the terminal node, so the pointer field of the terminal node is empty, that is, null.

3.Node structure.

Insert an operation( ) Ideological method The insertion operation is to insert a new node with a value of x into the position of the ith node in the table of the state of the state, that is, insert it between ai and ai Specific steps ( Find the AI storage location p ( Generate a new node with a data field of x*s ( Make the pointer field of node *p point to the new node ( The pointer field of the new node points to the node ai

The specific insertion process is shown in the animation

The specific algorithm implements void insertlist(linklist head datatype x int i).

Algorithm Analysis: The time of the algorithm is mainly spent on the lookup operation getnode, so the time complexity is also o(n).

Delete the operation( ) Ideological method The deletion operation is to delete the ith node of the table Specific steps ( Find the storage location of the ai p (because in a singly linked list, the storage address of the node ai is in the pointer field of its immediate predecessor node ai next) (make p next point to the direct successor node of the ai (i.e., remove the ai from the chain) (free up the space of the node ai and return it to the storage pool.

For the specific operation process, see Animation

The specific algorithm implements void deletelist(linklist head int i) Note: Let the length of the singly linked list be n, then the deletion of the ith node is valid only if i n When i=n+ Although the deleted node does not exist, its forward node exists It is the terminal node Therefore, the existence of the direct forward *p of the deleted node does not mean that the deleted node must exist Only if *p exists (i.e., p! =null) and *p is not a terminal node (i.e. p next! =null) to determine the existence of the deleted node.

<>2. Implementation of linked list class: constructor, remorse insertion function, delete function, determine whether it is an empty function.

3. Implementation of constructor: definition of head pointer.

4. The implementation idea of the insertion function: determine whether to insert it in the first place.

<>6. The implementation idea of judging whether it is empty: determine whether the head node is 0.

Just look at the book of pointers, and understand the allocation of pointers, addresses, and memory.

The n nodes of a linear table are linked together in their logical order through the chain domain of each node, and if each node of the linked list has only one link domain, this kind of linked list is called a singly linked list.

The storage address of each node in a single-linked list is stored in the pointer domain of its predecessor node, and the start node has no precursor, so the head pointer should be set to point to the start node, and the terminal node has no successor, so the pointer domain of the terminal node is empty, that is, null (represented by in the figure). The structure of a singly linked list is shown in Figure 1 and Figure 2.

Figure 1: A single chain without a head node represents the meaning.

Figure 2: The single-strand representation of the lead node is indicated.

There are two linked lists LA (A1, A2,...,an) and lb (b1,b2,...bm), discuss the following questions:

1) LA and LB are both single-linked lists with lead pointers, how to connect LB to LA after the slag flushing? What is the time complexity?

Answer: Start with the head node of la and move the pointer to the last node of the single-linked list, that is, the number of nodes with the length of la moved, and finally connect LB after la, so the time complexity is o(n).

2) LA and LB are both single-cycle linked lists with leading nodes, how to connect LB to form a circular linked list after LA?

What is the time complexity?

Answer: Start with the head pointer of LA first, move the pointer to the last node of the circular linked list, move the number of nodes of the length of LA to move the pointer from the head pointer of LB, move the pointer to the last node of the LB linked list, move the number of nodes of LB length, and finally connect LB to form a circular chain after LA such as a pure annihilation table, with a time complexity of O(N M).

2) LA and LB are both single-cycle linked lists with the head node and tail pointer, how to realize that LB is connected to LA and form a circular linked list after LA? What is the time complexity?

Answer: LA and LB are both single-cycle linked lists with the head node and tail pointer, and only need to connect the tail of the LA table and the head of LB to form a circular linked list, so the time complexity is O(1).