Các dạng xóa phần tử trong danh sách liên kết đôi

XÓA ĐẦU DANH SÁCH

int removeHead (DList &l)
{
if( l.pHead == NULL) return 0; 
DNode *p = l.pHead; 
l.pHead = l.pHead->pNext;
l.pHead->pPrev = NULL;
delete p;
if (l.pHead == NULL) l.pTail = NULL;
else l.pHead->pPrev = NULL; 
return 1; 
}

XÓA CUỐI DANH SÁCH

int removeTail (DList &l)
{
if(l.pTail == NULL) return 0;
DNode *p = l.pTail; 
l.pTail = l.pTail->pPrev;
l.pTail->pNext = NULL;
delete p;
if (l.pHead == NULL) l.pTail = NULL;
else l.pHead->pPrev = NULL;
return 1;
} 

XÓA PHẦN TỬ SAU Q

int removeAfter (DList &l, DNode *q)
{
if(q == NULL) return 0;
DNode *p = q ->pNext ;
if (p != NULL)
{ 
q->pNext = p->pNext;
if (p == l.pTail) l.pTail = q;
else p->pNext->pPrev = q;
delete p;
return 1;
}
else return 0;
}

XÓA PHẦN TỬ TRƯỚC Q

int removeBefore (DList &l, DNode *q)
{
if(q == NULL) return 0;
DNode *p = q ->pPrev;
if(p != NULL)
{ 
q->pPrev = p->pPrev;
if (p == l.pHead) l.pHead = q;
else p->pPrev->pNext = q;
delete p;
return 1;
}
else return 0;
}

XÓA PHẦN TỬ CÓ KHÓA LÀ k

int removeNode (DList &l, int k)
{
DNode *p = l.pHead;
while (p != NULL)
{ 
if (p->data== k) break;
p = p->pNext;
}
if (p == NULL) return 0; // Không tìm thấy k
DNode *q = p->pPrev;
if (q != NULL) // Xóa nút p sau q
return removeAfter (l, q);
else // Xóa p là nút đầu ds
 return removeHead (l);
}

 DSLK đôi về mặt cơ bản có tính chất giống như DSLK đơn   Tuy nhiên DSLK đôi có mối liên kết hai chiều nên từ một phần tử bất kỳ có thể truy xuất một phần tử bất kỳ khác
Trong khi trên DSLK đơn ta chỉ có thể truy xuất đến các phần tử đứng sau một phần tử cho trước
Điều này dẫn đến việc ta có thể dễ dàng hủy phần tử cuối DSLK đôi, còn trên DSLK đơn thao tác này tốn chi phí
Bù lại, xâu đôi tốn chi phí gấp đôi so với xâu đơn cho việc lưu trữ các mối liên kết. Điều này khiến việc cập nhật cũng nặng nề hơn trong một số trường hợp. Như vậy ta cần cân nhắc lựa chọn CTDL hợp lý khi cài đặt
cho một ứng dụng cụ thể

Chèn thêm nút vào danh sách liên kết đôi

Sau khi đã khởi tạo, nhập xuất danh sách  Tại Đây thì ta viết code chèn nút vào danh sách:

CHÈN VÀO SAU NÚT Q

void addAfter (DList &l, DNode *q, DNode *new_node)
{
DNode *p = q->pNext;
if (q!=NULL) { 
new_node->pNext = p; //(1)
if (p != NULL) p->pPrev = new_node; //(2)
new_node->pPrev = q; //(3)
q->pNext = new_node; //(4)
if (q == l.pTail) l.pTail = new_node; 
}
else
addFirst (l, new_node); // chèn vào đầu ds
}

CHÈN VÀO TRƯỚC NÚT Q

void addBefore (DList &l, DNode q, DNode* new_node)
{ DNode* p = q->pPrev;
if (q!=NULL) 
{ new_node->pNext = q; //(1)
q->pPrev = new_node; //(2)
new_node->pPrev = p; //(3)
if (p != NULL) p->pNext = new_node; //(4)
if (q == l.pHead) l.pHead = new_node; 
}
else
addTail (l, new_node); // chèn vào cuối ds
}

Nhập xuất danh sách liên kết đôi(kép)

Danh sách liên kết đôi(kép): Là danh sách mà mỗi phần tử trong danh sách có kết nối với 1 phần tử đứng trước và 1 phần tử đứng sau nó

 KHAI BÁO CẤU TRÚC DANH SÁCH

struct DNode 
{
DataType data; 
DNode* pPre; // trỏ đến phần tử đứng trước 
DNode* pNext; // trỏ đến phần tử đứng sau
};
struct DList 
{
DNode* pHead; // trỏ đến phần tử đầu ds
DNode* pTail; // trỏ đến phần tử cuối ds
};

HÀM TẠO NÚT 

Với DataType: Kiểu dữ liệu của phần tử (int,float,string,struct…..)

DNode* getNode ( DataType x) 
{
DNode *p;
p = new DNode; // Cấp phát vùng nhớ cho phần tử
if (p==NULL) {
cout<<“Khong du bo nho”; return NULL;
}
p->data = x; // Gán thông tin cho phần tử p
p->pPrev = p->pNext = NULL;
return p; 
}

HÀM THÊM NÚT VÀO ĐẦU DANH SÁCH

void addHead (DList &l, DNode* new_node)
{
if (l.pHead==NULL)
l.pHead = l.pTail = new_node;
else
{ new_node->pNext = l.pHead; // (1)
l.pHead->pPrev = new_node; // (2)
l.pHead = new_node; // (3)
}
}

HÀM THÊM NÚT VÀO CUỐI DANH SÁCH

void addTail (DList &l, DNode *new_node)
{ if (l.pHead==NULL) 
l.pHead = l.pTail = new_node;
else
{ l.pTail->pNext = new_node; // (1)
new_node->pPrev = l.pTail; // (2)
l.pTail = new_node; // (3)
}
}