## Chain List Introduction

### 1.1 Comparison of advantages and disadvantages between order table and chain table

Sequence table

Advantages: Any element in the table can be accessed at any time;

Disadvantages: Insert and delete operations require a large number of elements to be moved.

Chain Storage Linear Table

Advantages: No storage unit with contiguous addresses is required, and insertion and deletion operations do not require moving elements, only modifying the pointer;

Disadvantages: Loss of the advantage of random access to sequential tables.

Singly Linked List

Advantages: Solve the disadvantage that sequential tables require a large number of continuous storage units;

Disadvantages: Single-chain lists add pointer fields, which wastes storage space. When looking for a specific node, it is necessary to traverse from the header and look for it in turn.

### 1.2 Single Chain Table Definition

The chain storage of a linear table is called a single-chain table, which consists of a data field and a pointer field, which stores data elements, and a pointer field which stores the addresses of its subsequent nodes.

Single-chain table implementation:

Unheaded Node-->Empty Table Judgment: L=== NULL. Code writing is inconvenient

Leading Node-->Empty Table Judgment: L-> next==NULL. Writing code is more convenient (this is generally recommended)

Single Chain List Node Type Code Description:

typedef struct LNode { int data; // Node Data Domain struct LNode *next; // Pointer Domain of Node } LNode, *LinkList; // LinkList is a pointer type to struct LNode

"LinkList" is "equivalent to" LNode. The former emphasizes that this is a chain list, the latter emphasizes that this is a node, the appropriate place to use the appropriate name, and the code is more readable.

## 2. Basic operation of single-chain list

### 2.1 Bitwise insertion (leading node postinsertion)

ListInsert (&L, i, e): Insert operation. Insert the specified element E at the ith position i n table L. Average time complexity O(n)

[Analysis]: 1. Define the chain table structure first; 2. In the algorithm, determine if I position i s <1, create pointer *p pointing to the head node, find the i-1 node in the loop *p, insert it; 3. Create a node s to store element e, the next position of p i s the next position of s, that I s, assign p to s:s->next=p->next; and then the next position that becomes p i s s, that I s, p->next=s.

typedef struct LNode { ElemType data; // Node Data Domain struct LNode *next; // Pointer Domain of Node } LNode, *LinkList; // LinkList is a pointer type to struct LNode //Insert specified element e at position i I bool ListInsert(LinkList &L, int i, ElemType e){ if(i<1) return false; LNode *p; // Pointer p points to the currently scanned node int j=0; // The current p is pointing to the number of nodes p =L; // L points to the head node, which is the 0th node (there is no data) while (p!=NULL && j<i-1) { //Loop to find node 1-1 p=p->next; j++; } if(p==NULL) // Illegal i value return false; LNode *s = (LNode*)malloc(sizeof(LNode)); s->data = e; s->next=p->next; p->next=s; // Connect node s after p return true; // Insert Successful }

Without the post-interpolation of the first node, the operation at the first node is different from that of the other nodes.

[Analysis]: 1, Create new node *s, 2, s data field is element e, s next is L itself; 3, then s will become the original L.

if(i==1){ // Insert the first node differently from the other nodes LNode *s = (LNode*)malloc(sizeof(LNode)); s->data = e; S->next=L ; L=s; //Head Pointer Points to New Node return true; }

### 2.2 Interpolation operations for specified nodes

//Post-insert operation: insert element e after p-node bool InsertNextNode (LNode *p, ElemType e){ if (p==NULL) return false; LNode *s = (LNode *)malloc(sizeof(LNode)); if (s==NULL) //memory allocation failed return false; s->data = e; //Save data element e with node s s->next=p->next; p->next=s; //Connect node s after p return true; } call:return InsertNextNode(p,e)

### 2.3 Front Interpolation of Specified Nodes

Pre-insert operation: insert element e before the p-node.

How do I find the precursor of a p-node?

[Analysis 1]: With a known p node, the head pointer L can be passed in, the precursor Q of p can be looped, and then q can be interpolated back to complete the algorithm operation. Time complexity O(n).

[Analysis 2]: Known P node, create s node, we think that if the element value of P is e and the element value of S is p, then it can be a forward interpolation operation!!

- Next of s = next of p;
- next=s for p;
- Data of s = data of p;
- The data for p is e.

// Pre-insert operation: insert element e before the p-node. bool InsertPriorNode (LNode *p, ElemType e){ if (p==NULL) return false; LNode *s = (LNode *)malloc(sizeof(LNode)); if (s==NULL) //memory allocation failed return false; s->next=p->next; p->next=s; //Connect node s after p s->data=p->data p->data=e; // Elements in p are covered by e return true; }

### 2.4 Bitwise deletion (leading node)

ListDelete (&L, i, &e): Delete operation. Delete the element of the ith node i n table L and return the value of the deleted element with E. Time complexity O(n)

[Analysis]: Similar to insertion of 2.1, except the core code is different. Check the legality of the location of the deleted node, find the i-1 node*p, and then say that the pointer field of *p points to the next node of the deleted node*q, and release *q.

if(p==NULL) // Illegal i value return false; if(p->next == NULL) // Node i I has no return false; LNode *q=p->next; // Make q point to deleted node e = q->data; // Return the value of an element with e p->next=q->next; // Break *q Node from Chain free(q); // Release storage space for nodes return true; // Delete succeeded

### 2.5 Deletion of specified node p

[Analysis]: To delete the p-node, the precursor of P is unknown and the subsequent q is available. Then P exchanges the data domain with the next of p, assigns the next of Q to the next of p, and finally releases Q. Time complexity O(1)

//Delete the specified node p bool DeleteNode (LNode *p){ if (p==NULL) return false; LNode *q=p->next; // Point q to the next node of *p p->data=p->next->data; // Exchange data fields with subsequent nodes p->next=q->next; // Break *q Node from Chain free(q); // Release storage space for subsequent nodes return true; } [Note) When specifying a node is the last node, special handling is required

### 2.6 Find values by location

Bitwise lookup returns the first element (leading node)

[Analysis]: 1. Judge the legal location of i, create node *p pointing to head node L; 2, while loop finds the ith node, and finally return p. Time complexity O(n)

Starting from the first node in the single-chain list, search down the next pointer field one by one until the ith node is found, otherwise return to the last pointer field NULL.

// Bitwise lookup returns the first element (leading node) LNode *GetElem(LinkList L, int i){ if(i<0 ) return NULL; LNode *p; //Pointer p points to the currently scanned node int j=0; //The current p is pointing to the number of nodes p=L; //L points to the head node, which is the 0th node (there is no data) while (p!=NULL && j<i) { //Loop to find the ith node p=p->next; j++; } return p; }

### 2.7 Find Table Nodes by Value

Starting from the first node of a single-chain table, the values of each node's data field in the table are compared one after the other. If the value of a node's data field equals the given value e, a pointer to the node is returned: if there is no such node in the entire single-chain table, NULL is returned with time complexity O(n).

LNode *LocateElem (LinkList L, ElemType e) { LNode *p=L->next; while (p!=NULL&&p->data!=e) // Find nodes with data field e starting from the first node p-p->next; return P; // Return the node pointer when found, otherwise return NULL }