Two-way linked lists

“This is the 27th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

Homework problems

In the last article, we talked about single linked lists, and then at the end of the problem, I don’t know if you have done it, in order to take care of some students who are not very good at it, here is a simple explanation of this problem, let’s take a look at the original content:

Single linked list L = {a1,b1,a2,b2… A (n),b(n)},a(n),b(n)}, try to design an algorithm to split the single linked list L1 and L2 into two leading nodes, L1 = {a1,a2… ,a(n)}, L2 = {b(n),b(n-1)… ,b(1)}, requires L1 to use the header of L.

From the question, we can see that L1 is established by tail insertion and L2 by head insertion.

The problem itself is not too difficult. Let’s analyze it by drawing a picture. The following picture is part of single linked list L:

Since it is to split into two linked lists, we need to define variables p and q of two node types. We can first make P point to the first valid node, that is, the node where data A1 is stored, and then insert A1 into L1. Then q points to the next node of P, i.e. the node where b1 is stored, and then b1 is inserted into L2, and the cycle is complete.

See how the code works:

PNode split(PNode L){
	PNode L1,L2,R1,p,q;
	L1 = L;Here we still use the header of linked list L as the header of linked list L1
	R1 = L1;//R1 is the end of L1, initially pointing to the head
	p = L->next;//p refers to the first valid node of linked list L
	// create the header of linked list L2
	L2 = (PNode) malloc(sizeof(Node));
	if(L2 == NULL) {printf("Memory allocation failed, program terminated! \n");
		exit(- 1);
	}
	L2->next = NULL;//L2's initial pointer field is NULL
	while(p ! =NULL){
		q = p->next;//q refers to the second valid node of list L, which is used to find the node of list L2
		// Insert nodes into L1
		R1->next = p;
		R1 = p;
		// check whether q is null
		if(q == NULL) {break;
		}
		// move p back
		p = q->next;
		// Insert nodes into linked list L2
		q->next = L2->next;
		L2->next = q;
	}
	//L1 terminator pointer field is NULL
	R1->next = NULL;
	return L2;// return the header of list L2
}
Copy the code

If you know the head interpolation method and the tail interpolation method, this problem is not difficult to you, the only thing you need to notice is that there is a judgment condition in the loop, why do you want to determine q is not empty? And the position of the statement can not be written arbitrarily, otherwise the program will be wrong. In fact, there are two cases where linked list L has an odd number of nodes or an even number of nodes. Let’s look at the odd number first (assuming that linked list L1 has three valid nodes) :

Q is the node storing data 2. After inserting P into L1, we need to find the next node in L1, i.e. Q ->next, i.e., the node storing data 3. P =q->next; p=q->next; p=q->next; p=q->next; The program is in trouble, so make a non-null judgment on q before using the q variable.

If p=q->next is executed, the pointer field of q is NULL, so p is NULL, and the loop is terminated, and no program error occurs.

Write test code:

void main(a){
	PNode pHead,L2;
	int a[] = {1.2.3.4.5.6.7.8};
	pHead = create_listT(a,8);
	traverse_list(pHead);
	L2 = split(pHead);
	printf("Chain table L1: \ t");
	traverse_list(pHead);
	printf("\ n list L2: \ t");
	traverse_list(L2);
	getchar();
}
Copy the code

First of all, you have to create a linked list as linked list L, and I’m not going to repeat how to create a linked list here, but if you don’t understand it, you can read an article, and then pass in the header, and split it into two linked lists.

Running results:

1 2 3 4 5 6 7 8 9Chain table L1:1 3 5 7L2 list:8 6 4 2
Copy the code

Double linked list definition

After a brief review of singly linked lists at the beginning of this article, let’s move on to the topic of this article, double-linked lists.

Let’s start with the definition:

A bidirectional linked list, also known as a doubly linked list, is a type of linked list in which there are two data nodes pointing to the direct successor and direct precursor respectively. So, starting from any node in a bidirectional linked list, you can easily access its predecessors and successors.

From the definition, the only difference between a double-linked list and a single-linked list is that a double-linked list has a pointer field that can point to a direct precursor node, enabling bidirectional access.

So in a double-linked list, we assume that each Node’s type is denoted by Node, it should have a data field to store elements, denoted by data, a pointer field to store the address of the immediate successor Node, denoted by next, and a pointer field to store the address of the immediate precursor Node, denoted by prior, The Node types are defined as follows:

typedef struct Node{
	int data;
	struct Node *next;
	struct Node *prior;
}Node,*PNode;
Copy the code

Initialization of a double-linked list

So how do you build an empty double-linked list?

PNode create_list(a){
	// Create a header
	PNode pHead = (PNode) malloc(sizeof(Node));
	pHead->next = NULL;
	pHead->prior = NULL;
	return pHead;
}
Copy the code

Quite simply, allocate a chunk of memory for the header and set both pointer fields of the header to NULL.

For the establishment of non-empty double-linked list, we also need to master the head interpolation method and tail interpolation method of the establishment of two ways.

First look at the head insertion method:

This is the header of a double-linked list. How do you insert a node into the list by header?

So that completes the insertion. How do you do that? P ->next = p, p->next = p, p->next = s, p->next = s, p->next = s

There seems to be no problem, however, insert another element and you will see that the prior pointer field on the first node has not changed. It still points to the head node, when in fact it should point to the second node.

So how to solve it? P ->next = NULL; p->next = NULL; p->next = NULL;

PNode create_listH(int *a,int n){
	PNode pHead,pNew;
	int i;
	// Create a header
	pHead = (PNode) malloc(sizeof(Node));
	if(pHead == NULL) {printf("Memory allocation failed, program terminated! \n");
		exit(- 1);
	}
	pHead->next = NULL;// The initial pointer field of the header is NULL
	for(i = 0; i < n; i++){// Create new node
		pNew = (PNode) malloc(sizeof(Node));
		if(pNew == NULL) {printf("Memory allocation failed, program terminated! \n");
			exit(- 1);
		}
		// Save data
		pNew->data = a[i];
		pNew->next = pHead->next;// Set the pointer field to NULL for the new node, which is the end of the linked list
		// Check whether there are any nodes after the header
		if(pHead ->next ! =NULL) {// The prior pointer field to the node to which the header points points points to the newly created node
			pHead->next->prior = pNew;
		}
		pHead->next = pNew;// The header points to the new node
	}
	return pHead;
}
Copy the code

To verify the correctness of the code, we write a traversal function. The traversal of a double-linked list is the same as that of a single-linked list. Here is the code directly attached:

PNode create_list(a){
	// Create a header
	PNode pHead = (PNode) malloc(sizeof(Node));
	pHead->next = NULL;
	pHead->prior = NULL;
	return pHead;
}
Copy the code

Write test code:

void main(a){
	PNode pHead;
	int a[] = {1.2.3.4.5.6};
	pHead = create_listH(a,6);
	traverse_list(pHead);
	getchar();
}
Copy the code

Running results:

6 5 4 3 2 1

Copy the code

Now let’s look at tail insertion to create a double-linked list.

How do you insert the first node into a linked list with the same head node?

PTail = p; pTail = s; pTail = s; Prior = pTail; s->prior = pTail; pTail = s;

Here is the code implementation:

PNode create_listR(int *a,int n){
	PNode pHead,pNew,pTail;
	int i;
	// Create a header
	pHead = (PNode) malloc(sizeof(Node));
	if(pHead == NULL) {printf("Memory allocation failed, program terminated! \n");
		exit(- 1);
	}
	pTail = pHead;// The initial point is to the header
	for(i = 0; i < n; i++){// Create new node
		pNew = (PNode) malloc(sizeof(Node));
		if(pNew == NULL) {printf("Memory allocation failed, program terminated! \n");
			exit(- 1);
		}
		// Save data
		pNew->data = a[i];
		pTail->next = pNew;
		pNew->prior = pTail;
		pTail = pNew;
	}
	pTail->next = NULL;// The endpoint pointer field is NULL
	return pHead;
}

Copy the code

Let’s test it out:

void main(a){
	PNode pHead;
	int a[] = {1.2.3.4.5.6};
	pHead = create_listR(a,6);
	traverse_list(pHead);
	getchar();
}

Copy the code

Running results:

1 2 3 4 5 6

Copy the code

Find the length of a double-linked list

This is the same as the single linked list operation, nothing to say, directly look at the code:

int length_list(PNode pHead){
	int i = 0;
	PNode p = pHead->next;
	while(p ! =NULL){
		i++;
		p = p->next;
	}
	return i;
}

Copy the code

We’ve already done that in singly linked lists, so I’m not going to test it.

Check whether the table is empty

Check whether the table is empty or not is the same as the single linked list operation, look at the code:

int isEmpty_list(PNode pHead){
	if(pHead->next == NULL) {return 1;
	}else{
		return 0; }}Copy the code

Insert the node

Insert and delete operations in a double-linked list are very similar to, but slightly different from, single-linked lists. Insert and delete operations in a double-linked list involve changes in two pointer fields, so they are more complex, but easy to understand with careful taste.Suppose NOW I need to insert node S at position Q, then the structure of the linked list is as follows:

So how do you implement insertion? Similarly, we need to find the node before the insertion, so for example, in this case, if we want to insert s into q, we need to find the node before Q, which is P, and then we need to point next from S to next from P, so that s points to Q.

Then, the pointer field prior of node Q points to node S, thus establishing the bidirectional relationship between node S and node Q.

Then, the pointer field of node S prior points to node P, and the pointer field of node P next points to node S to establish the bidirectional relationship between node P and node S.

This completes the insertion.

Here is the code implementation:

int insert_list(PNode pHead,int pos,int val){
	PNode p,pNew;
	int len,i = 0;
	p = pHead;//p initially points to the header
	len = length_list(pHead);
	// Check the validity of the pos value
	if(pos < 1 || pos > len + 1) {return 0;
	}
	// find the node before the insertion position
	while(i < pos - 1&& p ! =NULL){
		i++;
		p = p->next;
	}
	if(p == NULL) {return 0;
	}
	// p is the node before the insertion position
	// Create new node
	pNew = (PNode) malloc(sizeof(Node));
	if(pNew == NULL) {printf("Memory allocation failed, program terminated! \n");
		exit(- 1);
	}
	// Save data
	pNew->data = val;
	// Insert node
	pNew->next = p->next;
	// determine whether p is the end node
	if(p->next ! =NULL){
		p->next->prior = pNew;
	}
	pNew->prior = p;
	p->next = pNew;
	return 1;
}

Copy the code

Insert also need to pay attention to a problem, that is the position of the insertion, if is a linked list at the end of the cycle through find nodes p is the list of the tail, and end node pointer field next to NULL, do not need to consider the node pointer domains pointing to the problem of the prior, judging if not checked, when you insert the node to the list at the end, The program will report an error.

Write test code:

void main(a){
	PNode pHead;
	int a[] = {1.2.3.4.5.6};
	pHead = create_listR(a,6);
	traverse_list(pHead);
	if(insert_list(pHead,5.50)) {printf("After insertion: \n");
		traverse_list(pHead);
	}else{
		printf("Insert failed! \n");
	}
	getchar();
}

Copy the code

Running results:

1 2 3 4 5 6After the insert:1 2 3 4 50 5 6

Copy the code

Delete nodes

Take a look at the following doubly linked list:

How do I remove node S from the linked list?

The principle is very simple, first of all, we take the pointer field of node P, next, and point to the pointer field of node S, which isp->next = p->next->next, prior to q points to p, i.eq->prior = p, the bidirectional relationship is established between node P and node Q, and the memory of node S can be released at last.See how the code works:

int delete_list(PNode pHead,int pos,int *val){
	PNode p,q;
	int len,i = 0;
	len = length_list(pHead);
	p = pHead;// The initial point is to the header
	// Check the validity of the pos value
	if(pos < 1 || pos > len){
		return 0;
	}
	// Find the previous node of the node to be deleted
	while(i < pos - 1&& p ! =NULL){
		i++;
		p = p->next;
	}
	// p is the previous node of the node to be deleted
	q = p->next;//q is the node to be deleted
	// Save data
	*val = q->data;
	// Delete the node
	p->next = q->next;
	if(p->next! =NULL){
		p->next->prior = p;
	}
	free(q);
	return 1;
}

Copy the code

Here also need to consider the problem of deleting the tail node, if you want to delete the tail node, then there are no nodes behind the tail node, so the direct successor node can not be processed, processing will report an error, we should be on the pointer field p next non-null judgment, do not put p->next! = NULL write q! = NULL; q = p->next; = NULL, this is an error. Before the judgment, the pointer field of P, next, has been changed, so it is only necessary to determine whether P is NULL. When the tail node is deleted, P points to the pointer of Q, and Q is the tail node, so the pointer of P is NULL, and Q is not empty, it is the tail node, which needs to be paid attention to.

Here is the test code:

void main(a){
	PNode pHead;
	int a[] = {1.2.3.4.5.6};
	int val;
	pHead = create_listR(a,6);
	traverse_list(pHead);
	if(delete_list(pHead,6,&val)){
		printf("After deletion: \n");
		traverse_list(pHead);
		printf("Delete node element value: %d\n",val);
	}else{
		printf("Delete failed! \n");
	}
	getchar();
}

Copy the code

Running results:

1 2 3 4 5 6After the delete:1 2 3 4 5The element value of the deleted node is:6

Copy the code

There is no need to repeat the same operations as singly linked lists as to find the node position of the specified element value, or find the element value of the specified node position, and destroy the linked list. If you don’t know, check out my last article.

Homework problems

As usual, I’ll also leave an algorithm problem:

For a double-linked list L with one leading node, try to design an algorithm to invert all its elements, that is, the first element becomes the last element, and the second element becomes the penultimate element… , the last element becomes the first element.

Also simple analysis, this problem is actually very simple, by traversing double linked list L, and then use the head plug method to create a linked list can be completed, the specific implementation depends on you. I’ll find out in my next column.