# Section 7.3 of algorithm notes - special topic of data structure - > linked list processing

Section 7.3 of algorithm notes - Special Topic on data structure (1) - > linked list processing

# Problem A: algorithm 2-8 ~ 2-11: basic operation of linked list

### Title Description

Linked list is one of the most basic data structures. It is a linear list realized by linked storage structure. Compared with the sequential table, it does not have to move the subsequent elements during insertion and deletion. Now give you some integers, and then you will frequently insert and delete some elements. At some time, you will find an element or output all the elements in the current linked list.
Here is the basic algorithm description:  ### input

There is only one set of input data. The first line has n+1 integers. The first integer is the number of remaining integers in this line, N, followed by N integers. This line of integers is used to initialize the list, and the input order is opposite to that in the list, that is, if there are 1, 2 and 3 in the list, the input order is 3, 2 and 1.
The second line has an integer m, which means there are m lines below. Each line has a string. The string is one of "get", "insert", "delete" and "show". If it is "get" or "delete", it will be followed by an integer a, which means to obtain or delete the a-th element; If it is "insert", it will be followed by two integers a and E, representing the insertion of e before the a position; There is no integer after "show".

### output

If the acquisition is successful, the element is output; If the deletion is successful, "delete OK" is output; If the acquisition or deletion fails, "get fail" and "delete fail" are output. If the insertion is successful, "insert OK" is output; otherwise, "insert fail" is output. If it is "show", all elements in the list will be output. If the list is empty, "Link list is empty" will be output. Note: all double quotation marks are not output.

3 3 2 1
21
show
delete 1
show
delete 2
show
delete 1
show
delete 2
insert 2 5
show
insert 1 5
show
insert 1 7
show
insert 2 5
show
insert 3 6
show
insert 1 8
show
get 2

### sample output

1 2 3
delete OK
2 3
delete OK
2
delete OK
Link list is empty
delete fail
insert fail
Link list is empty
insert OK
5
insert OK
7 5
insert OK
7 5 5
insert OK
7 5 6 5
insert OK
8 7 5 6 5
7

### code

```#include<cstdlib>//malloc func
#include<cstdio>//stdio func
#include<cstring>//strcmp func

#define OK 1
#define ERROR 0

typedef int Status;//function type
typedef int ElemType;//LNode data type

typedef struct LNode{
ElemType data;//data element definition
struct LNode *next;//next node address definition
}LNode, *LinkList;//node type & list type definition

Status GetElem_L(LinkList &L,int i, ElemType &e){
//L is head node
p=L->next;
int j=1;//p is the 1st node(next to L), j is a counter
while (p&&j<i){//find the node i(L is node 0)
p=p->next;
++j;
}
if (!p||j>i)//node i is not exist
return ERROR;
e=p->data;//e is data of node i
return OK;
}
Status ListInsert_L(LinkList &L, int i,ElemType e){
//insert new data before node i
LinkList p,s;//definition of new node(s),node i-1(p)
p=L;
int j=0;
while(p&&j<i-1){//find node i-1
p=p->next;
++j;
}
if(!p||j>i-1)//if i<1 or i>length of list, return ERROR
return ERROR;
s=(LinkList)malloc(sizeof(LNode));//insert new node as node i-1
s->data=e;
s->next=p->next;
p->next=s;
return OK;
}
Status ListDelete_L(LinkList &L,int i,ElemType &e){
//delete node i,and return the data by e(by address transmission)
p=L;
int j=0;
while(p->next&&j<i-1){//find the node i-1
p=p->next;
++j;
}
if(!(p->next)||j>i-1)//delete isn't exist
return ERROR;
q=p->next;
p->next=q->next;//delete and free node
e=q->data;
free(q);
return OK;
}
void CreateList_L(LinkList &L,int n){
//input a list from rear to start
int i;//the length of list
for(i=n;i>0;--i){
p=(LinkList)malloc(sizeof(LNode));//new node between head node(L) and L->next
scanf("%d",&p->data);
p->next=L->next;
L->next=p;
}
}
//show data of L
LinkList p=L->next;//p is a node to show L
if(p==NULL)
{
printf("Link list is empty\n");
return;
}
while(p!=NULL){
if(p->next==NULL)
printf("%d",p->data);
else printf("%d ",p->data);
p=p->next;
}
printf("\n");
}

int main(){
int n=0,m=0,num=0;
ElemType e;
char str_Instruction;
scanf("%d",&n);
CreateList_L(List,n);
scanf("%d",&m);
while(m--){
scanf("%s",str_Instruction);
if(!strcmp(str_Instruction,"get")){
scanf("%d",&num);
if(GetElem_L(List,num,e)){
printf("%d\n",e);
}
else{
printf("get fail\n");
}
}
else if(!strcmp(str_Instruction,"delete")){
scanf("%d",&num);
if(ListDelete_L(List,num,e)){
printf("delete OK\n");
}
else{
printf("delete fail\n");
}
}
else if(!strcmp(str_Instruction,"insert")){
scanf("%d %d",&num,&e);
if(ListInsert_L(List,num,e)){
printf("insert OK\n");
}
else{
printf("insert fail\n");
}
}
else if(!strcmp(str_Instruction,"show")){
ShowList_L(List);
}
}
return 0;
}
```

# Question B: C language - linked list sorting

### Title Description

There are two linked lists a and b, and the nodes in each linked list include student number and grade. It is required to merge the two linked lists and arrange them in ascending order by student number.

### input

In the first row, the number N and M of a and b linked list elements are separated by spaces. Next, row n is the data of a, and then row M is the data of b. each row of data is composed of student number and grade

### output

Data in ascending order of student number

2 3
5 100
6 89
3 82
4 95
2 10

2 10
3 82
4 95
5 100
6 89

### Code submission

```#include <cstdio>

struct node {
int num;
int score;
node *next;
};
void insert(node *ans, node *q) {    //ans is the final printed linked list, and q is the node of a person's student number and score inserted
node *pre, *p;    //Create two new nodes
pre = ans, p = ans->next;
while (p != NULL && p->num < q->num) { //Find the first node whose student number is greater than q
pre = p;
p = p->next;
}
pre->next = q; // pre-q-p connection
q->next = p;
}
int main() {
node *ans, *p;
int n, m;
scanf("%d %d", &n, &m);
ans = new node;
ans->next = NULL;
for (int i = 0; i < n + m; i++) {
p = new node;
p->next = NULL;
scanf("%d %d", &p->num, &p->score);
insert(ans, p); //Connect the new node into the linked list
}
for (p = ans->next; p != NULL; p = p->next) {
printf("%d %d\n", p->num, p->score);
}
return 0;
}

```

I never thought of this before. In fact, after each new node is created, the sorting can be realized by traversing to find the location where it should be inserted.

Posted by minds_gifts on Thu, 12 May 2022 22:26:46 +0300