# Data Structure - Interpolation, Deletion and Lookup of Single Chain Table

## 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;

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!!

1. Next of s = next of p;
2. next=s for p;
3. Data of s = data of p;
4. 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)
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
}
```