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 đơn. Tiếp theo cho một số nguyên k, (0 ≤ k < n).
Hãy xóa phần tử ở 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
  4 1 2 3 4 1	1 3 4

  
  Với l = [1, 2, 3, 4], k = 1 thì kết quả mong muốn là:
  "1 3 4 ".
   
• Test mẫu 2:
   

  Input	Output
  3 1 2 3 0	2 3

  
  Với l = [1, 2, 3], k = 0 thì kết quả mong muốn là:
  "2 3".

Lý thuyết.

Việc xóa phần tử trong danh sách liên kết đôi cũng tương tự như trong danh sách liên kết đơn. Với độ phức tạp là O(1).

Xóa phần tử đầu tiên trong danh sách liên kết đôi.

Để xóa phần tử đầu tiên trong danh sách liên kết đôi l, ta phải quan tâm tới phần tử l->head->next, chuyển liến kết pre của nó về NULL, cuối cùng là cập nhật l->head = l->head->next, và nhớ xóa vùng nhớ đã cập phát cho node đã xóa.

Code C++ mẫu:

douList *deleteHead(douList *l){
	node *p = l->head->next;
	node *temp = l->head;
	p->pre = NULL;
	l->head = p;
	delete(temp);
	return l;
}

Xóa phần tử cuối cùng trong danh sách liên kết đôi.

Để xóa phần tử cuối cùng trong danh sách liên kết đôi l, ta phải quan tâm tới phần tử l->tail->pre, chuyển liến kết next của nó về NULL, cuối cùng là cập nhật l->tail= l->tail->pre, và nhớ xóa vùng nhớ đã cập phát cho node đã xóa.

Code C++ mẫu:

douList *deleteTail(douList *l){
	node *p = l->tail->pre;
	node *temp = l->tail;
	p->next = NULL;
	l->tail = p;
	delete(temp);
	return l;
}

Xóa phần tử ở vị trí khác vị trí đầu và cuối trong danh sách liên kết đôi.

Để xóa phần tử vị trí k thì ta cần phải xử lý hai phần từ ở vị trí k-1 và k+1.

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 *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 *deleteHead(douList *l){
	node *p = l->head->next;
	node *temp = l->head;
	p->pre = NULL;
	l->head = p;
	delete(temp);
	return l;
}
douList *deleteTail(douList *l){
	node *p = l->tail->pre;
	node *temp = l->tail;
	p->next = NULL;
	l->tail = p;
	delete(temp);
	return l;
}
douList *deleteAt(douList *l, int k){
	node *p = l->head;
	for (int i = 0; i < k-1; i++){
		p = p->next;
	}
	node *temp = p->next;
	node *p2 = temp->next;
	p->next = p2;
	p2->pre = p;
	delete(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;
	if (k == 0){
		l = deleteHead(l);
	} else if (k == n-1){
		l = deleteTail(l);
	} else {
		l = deleteAt(l, k);
	}
	printList(l);
	return 0;
}