Nhập vào một số nguyên dương n, tiếp theo là n số nguyên của một dãy số, hãy cài đặt nó vào một danh sách liên kết đôi. Tiếp theo cho hai số nguyên k và x, (0 ≤ k ≤ n).
Hãy chèn giá trị x vào danh sách liên kết tại chỉ số k và in ra màn hình danh sách đó, sau một phần tử có đúng một khoảng trắng.

Ví dụ:

• Test mẫu 1:
   

  Input	Output
  3 1 2 3 0 10	10 1 2 3

  
  Với l = [1, 2, 3] và k = 0, x = 10 thì kết quả là:
  "10 1 2 3 ".
   
• Test mẫu 2:
   

  Input	Output
  3 1 2 3 3 10	1 2 3 10

  
  Với l = [1, 2, 3] và k = 3, x = 10 thì kết quả là:
  "1 2 3 10".
   
• Test mẫu 3:
   

  Input	Output
  4 1 2 3 4 2 10	1 2 10 3 4

  
  Với l = [1, 2, 3, 4] và k = 2, x = 10 thì kết quả là:
  "1 2 10 3 4 ".

Lý thuyết.

Thêm phần tử vào đầu douList:

Code C++ mẫu:

douList *addHead(douList *l, int x){
	node *temp = new node;
	temp->data = x;
	temp->pre = NULL;
	temp->next = l->head;
	l->head->pre = temp;
	l->head = temp;
	return l;
}

Thêm phần tử vào cuối danh sách liên kết đôi:

Code C++ mẫu:

douList *addTail(douList *l, int x){
	node *temp = new node;
	temp->data = x;
	temp->next = NULL;
	temp->pre = l->tail;
	l->tail->next = temp;
	l->tail = temp;
	return l;
}

Thêm phần tử vào vị trí khác đầu và cuối.

Tương tự như danh sách liên kết đơn để chèn phần tử vào ví trí k, ta cần tìm node trỏ tới phần tử k-1 trước.

Như hình vẽ ta thấy có bốn liên kết mới được tạo ra.

Code C++ mẫu:

douList *addAt(douList *l, int k, int x){
	node *p = l->head;
	for (int i = 0; i < k-1; i++){
		p = p->next;
	}
	node *temp = new node;
	temp->data = x;
	temp->pre = p;
	temp->next = p->next;
	p->next->pre = temp;
	p->next = temp;
	return l;
}

Hướng dẫn bài tập.

Code mẫu:

Ngôn ngữ C++:

#include<iostream>

using namespace std;

struct node{
	int data;
	node *next;
	node *pre;
};
struct douList{
	node *head;
	node *tail;
};
douList *createList(int x){
	douList *l = new douList;
	l->head = new node;
	l->head->data = x;
	l->head->pre = NULL;
	l->head->next = NULL;
	l->tail = l->head;
	return l;
}
douList *addHead(douList *l, int x){
	node *temp = new node;
	temp->data = x;
	temp->pre = NULL;
	temp->next = l->head;
	l->head->pre = temp;
	l->head = temp;
	return l;
}
douList *addTail(douList *l, int x){
	node *temp = new node;
	temp->data = x;
	temp->next = NULL;
	temp->pre = l->tail;
	l->tail->next = temp;
	l->tail = temp;
	return l;
}
douList *addAt(douList *l, int k, int x){
	node *p = l->head;
	for (int i = 0; i < k-1; i++){
		p = p->next;
	}
	node *temp = new node;
	temp->data = x;
	temp->pre = p;
	temp->next = p->next;
	p->next->pre = temp;
	p->next = temp;
	return l;
}
void printList(douList *l){
	node *p = l->head;
	while (p != NULL){
		cout << p->data << " ";
		p = p->next;
	}
}

int main(){
	int n, x, k;
	cin >> n;
	cin >> x;
	douList *l = createList(x);
	for (int i = 1; i < n; i++){
		cin >> x;
		l = addTail(l, x);
	}
	cin >> k >> x;
	if (k == 0){
		l = addHead(l, x);
	} else if (k == n){
		l = addTail(l, x);
	} else{
		l = addAt(l, k, x);
	}
	printList(l);
	return 0;
}