1. Two way linked list

Bidirectional linked list is that each node has two pointer fields, pointing to the front and rear nodes of the node respectively. Therefore, the data reading of bidirectional linked list is bidirectional, which is more convenient for data modification.

  Construction of bidirectional linked list:

#include<iostream>
using namespace std;

struct DLNode
{
	int data;
	DLNode* next;//Leading pointer
	DLNode* per;//Backward pointer
};

void creat(DLNode*& head)
{
	DLNode* p, * temp;
	head = (DLNode*)malloc(sizeof(DLNode));
	head->next = NULL;
	head->per = NULL;
	p = head;
	while (true)
	{
		temp = (DLNode*)malloc(sizeof(DLNode));
		cin >> temp->data;
		p->next = temp;
		p->next->per = p;
		p = temp;
	}
	p->next = NULL;
}

2. Circular linked list

The main representation of circular linked list is similar to that of one-way linked list, except that the pointer field of the last node is no longer empty, but points to the first node instead (sometimes it points to the second node, and the head node is reserved for subsequent data modification. Please use it according to your personal habits.)

 

  Creation of circular linked list:

#include<iostream>
using namespace std;

struct LNode
{
	int data;
	LNode* next;
};

void creat(LNode*& head)
{
	LNode* p;
	LNode* temp;
	head = (LNode*)malloc(sizeof(LNode));
	head->next = NULL;
	p = head;
	while (true)
	{
		temp = (LNode*)malloc(sizeof(LNode));
		cin >> temp->data;
		p->next = temp;
		p = temp;
	}
	p->next = head;
}

3. Addition and deletion of linked list

The difference between a linked list and an array is that the data storage flexibility of the linked list is higher, so it is more convenient in data modification (adding and deleting an array requires moving all the data with the modified position, while the modification of the linked list is only related to the modified node and the node of a unit around it)

① Linked list increase

In essence, adding linked list data is to insert new nodes at the required position on the basis of the original linked list. At this time, you only need to make the pointer of the previous node of the position to be inserted point to the new node, and the pointer field of the new node point to the next node of the position to be inserted. The specific operation is shown in the figure:

  Example: merging of PTA ordered linked list

Input two ordered Integer Sequences (including M and N data respectively), establish two ordered single linked lists, merge the two ordered single linked lists into one ordered single linked list, and output the merged single linked list data in turn.

Input format:

There are multiple groups of test data, which are processed to the end of the file. For each set of tests, enter the values of M and N in the first line; Enter m ordered integers in the second line; In the third line, enter n ordered integers in turn.

Output format:

For each group of tests, output M+N ordered integers contained in the combined single linked list.

Input example:

6 5
1 23 26 45 66 99
14 21 28 50 100
2 2
1 2
1 3

Output example:

1 14 21 23 26 28 45 50 66 99 100
1 1 2 3

Specific code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define maxn 10100
using namespace std;

typedef struct ListNode
{
    int data;
    ListNode* next;
}LNode;
LNode* newlist(int n)
{
    LNode* head;
    head = (LNode*)malloc(sizeof(LNode));
    head->next = NULL;
    cin >> head->data;
    n--;
    LNode* mail = head;
    while (n--)
    {
        LNode* p;
        p = (LNode*)malloc(sizeof(LNode));
        p->next = NULL;
        cin >> p->data;
        mail->next = p;
        mail = p;
    }
    return head;
}
LNode* add(LNode* head1, LNode* head2, LNode* head3)
{
    LNode* mail = head3;
    while (head1 && head2)
    {
        if (head1->data < head2->data)
        {
            mail->next = head1;
            mail = mail->next;
            LNode* p;
            p = head1;
            head1 = head1->next;
            p->next = NULL;
        }
        else
        {
            mail->next = head2;
            mail = mail->next;
            LNode* p;
            p = head2;
            head2 = head2->next;
            p->next = NULL;
        }
    }
    if (head1)
    {
        while (head1)
        {
            mail->next = head1;
            mail = mail->next;
            LNode* p = head1;
            head1 = head1->next;
            p->next = NULL;
        }
    }
    else if (head2)
    {
        while (head2)
        {
            mail->next = head2;
            mail = mail->next;
            LNode* p = head2;
            head2 = head2->next;
            p->next = NULL;
        }
    }
    return head3;
}
void print(LNode* head3)
{
    int top = 1;
    while (head3->next)
    {
        if (top)top = 0;
        else printf(" ");
        cout << head3->next->data;
        head3 = head3->next;
    }
    cout << endl;
}
int main()
{
    int m, n;
    while (cin >> m >> n)
    {
        LNode* head1, * head2, * head3;
        head1 = newlist(m);
        head2 = newlist(n);
        head3 = (LNode*)malloc(sizeof(LNode));
        head3->next = NULL;
        head3 = add(head1, head2, head3);
        print(head3);
    }
    return 0;
}

② Linked list data deletion

Data deletion can be regarded as the reverse operation of insertion, but pay attention to make the pointer field of the previous node point to the next node after the node to be deleted, and then clear the pointer of the node to be deleted. If you clear the pointer first, the address of the next node will be lost and the linked list will be broken.

The specific operation is shown in the figure:

  The specific practice blogger has not found it yet, and will update it again after finding it (mainly because the computer is running out of power, QAQ)