Hẳn các bạn ai cũng fai học qua môn Cấu trúc dữ liệu.Trong đó danh sách liên kết là 1 cấu trúc dữ liệu động rất phổ biến .
Hôm nay mình cũng bon chen viết bài về danh sách liên kết kép.Mình demo với trường data của 1 nút là kiểu dữ liệu int nha.
-Danh sách lien kết kép thực ra cũng giống với DSLKD thôi.chỉ khác là mỗi nút có thêm con trỏ prev để trỏ tới phần tử trước nó trong DSLKK thôi,thay vì chỉ có mỗi pnext đối với DSLKD.
Cách khai báo,cài đặt DSLKK cũng như DSLKD thôi:

Code:

typedef struct DNode
{
    int value;
    struct DNode *pnext,*prev;
}DNODE;//Cấu trúc của 1 nút
typedef struct DList
{
    DNODE *phead,*ptail;
}DLIST; //Cài đặt structure để quản lí DLIST 

-Tới đây ắt hẳn các bạn sẽ hỏi lệnh typedef để làm j?Thực ra typedef có nhiệm vụ định nghĩa 1 kiểu dữ liệu từ 1 kiểu đã có.Nếu ở đây không có typedef thì :

Code:

struct DNode
{
    int value;
    struct DNode *pnext,*prev;
};
struct DList
{
    DNODE *phead,*ptail;
}; 

lúc bạn khai báo biến fai có thêm struct (trong C thôi,C++ không cần)
VD: struct DNode a;




-Điều đầu tiên :Khi chúng ta thao tác với danh sách liên kết thì chúng ta phải đảm bảo rằng mọi thành phần kết nối ( pnext,prev) đều hợp lý và chính xác.
--Các bạn có thể thấy khi mình muốn add thêm 1 nút vào đầu Danh sách liên kết kép: Thì sẽ có 2 trường hợp cơ bản mà chúng ta cần xét:danh sách rỗng và danh sách không rỗng.
VD: Thêm nút A1 nào đó vào đầu danh sách liên kết kép L nha:
+TH Danh sách rỗng (L.phead=NULL):Khi danh sách rỗng thì các con trỏ đến phần tử đầu và cuối danh sách đều bằng null( nghĩa là danh sách chưa có cái j trong đó hết,rỗng tuếch).


- add A1 vào đầu danh sách.:thì lúc này danh sách chỉ có 1 phần tử và phần kết nối (prev,pnext) đều bằng NULL.vì đằng trước và đằng sau A1 đâu còn thằng nào nữa đâu mà trỏ tới nhỉ. Cập nhật lại giá trị con trỏ phead và ptail.Trường hợp này phần tử đầu danh sách trùng với cuối danh sách nên phead và ptail cùng trỏ tới A1( trỏ tới cùng 1 vùng nhớ trong bộ nhớ chính).
+TH Danh sách không rỗng (L.phead!=NULL)

Khi add A1 vào đâu danh sách thì ta phải chú ý đến thành phần kết nối(prev,pnext)

Ý tưởng:
Lúc đầu L.phead=A //đầu danh sách là A
A1->pnext=L.phead; ///cái thằng đứng sau nút A1 là nút A
L.phead->prev=A1 ;//chỉnh lại: vì A1 mới đc thêm vào đầu danh sách nên thằng đứng trước nút A là A1,chư không phải là NULL.
//Bây giờ phần tử đầu danh sách là A1 chứ không phải A nữa nên phải chỉnh lại con trỏ phead thôi pà con ui!!!
L.phead=A1;

*Còn việc add thêm nút vào cuối danh sách hay add sau 1 nút thì ý tưởng cơ bản cũng gần gần giống như add vào đầu danh sách thôi.Chỉ cần chú ý chỉnh sửa những thành phần kết nối( prev,pnext) có lien quan thôi nha.Không liên quan thì làm lơ nó.I don’t care)

*Xóa phần tủ ở đầu danh sách nè:
+Nếu danh sách rỗng thì khỏi cần xét làm gì đúng không pà con (cái này không biết đúng không………hihihihi)
+Giờ chỉ cần xét trường hợp danh sách khác rỗng thôi:

Muốn hủy phần tử đầu xâu thì ta phải hủy các mối liên hệ của nó trước: (giống như ngày xưa sát thủ giết vua,guan lại,phải giết hết mấy thằng lính ,người bên cạnh nó trước thì lúc đó giết nó mới dễ đúng không nào) .
Đầu tiên:
X=L.phead;// ghi nhớ mục tiêu tiêu diệt là A
L.phead=X->pnext; //lúc này thằng đầu danh sách là thằng đứng sau A,vì thằng A sắp bị mạng ra chém rồi còn gì( thằng B lên nắm quyền làm BOSS).
If(L.phead!=NULL) L.phead->prev=NULL;
+ //Nếu B tồn tại ( danh sách không rỗng khi hủy thằng A) thì trước thằng B phải là NULL.Nếu chúng ta không làm điều này:L.phead->prev=NULL(B->prev=NULL) thì sau khi thằng A bị hủy thì thằng B vẫn cứ nhớ là đằng trước nó còn thằng A(B->prev==A);
--Cuối cùng mang X (A) ra chém bay đầu cho ta: delete a;
Xóa 1 phần tử cuối danh sách cũng tương tự như thế này thôi.

Code:

/*
 Coder:tauit_dnmd
 */
#include<stdio.h>
#include<conio.h>
typedef struct DNode
{
    int value;
    struct DNode *pnext,*prev;
}DNODE;
DNODE* InitDNode(int x)
{
    DNODE* temp=new DNODE;
    if(temp==NULL) return NULL;
    temp->value=x;
    temp->prev=temp->pnext=NULL;
    return temp;
}
typedef struct DList
{
    DNODE *phead,*ptail;
}DLIST;
void InitDList(DLIST &L)
{
    L.phead=L.ptail=NULL;
}
void AddHead(DLIST &L,DNODE *p)
{
    if(p==NULL) return;
    if(L.phead==NULL)
    {
        p->pnext=p->prev=NULL;
        L.phead=p;
        L.ptail=L.phead;
       
    }
    else
    {
        p->prev=NULL;
        p->pnext=L.phead;
        L.phead=p;
    }
}
void AddTail(DLIST &L,DNODE *p)
{
    if(p==NULL) return;
    if(L.phead==NULL)
    {
        p->pnext=p->prev=NULL;
        L.phead=p;
        L.ptail=L.phead;
       
    }
    else
    {
        p->prev=L.ptail;
        p->pnext=NULL;
        L.ptail->pnext=p;
        L.ptail=p;
    }
}
int AddAt(DLIST &L,int x,int pos) //them x vao sau Node co gia tri ==pos  dau tien
{
    if(L.phead==NULL) return 0;
    DNODE *p=L.phead;
    while(p!=NULL)
    {
        if(p->value==pos) break;
        p=p->pnext;
    }
    if(p!=NULL)
    {
        DNODE *temp=InitDNode(x);
        temp->pnext=p->pnext;
        temp->prev=p;
        p->pnext=temp;
        if(p==L.ptail) L.ptail=temp;
        return 1;
    }
    return 0;
}
void RemoveHead(DLIST &L)
{
    DNODE *x;
    if(L.phead==NULL) return;
    x=L.phead;
    L.phead=L.phead->pnext;
    if(L.phead!=NULL) L.phead->prev=NULL;
    delete x;
}
void RemoveTail(DLIST &L)
{
    DNODE *p,*q;
    if(L.phead==NULL) return;
    p=L.ptail;
    if(p->prev==NULL){ RemoveHead(L);return;}
    q=p->prev;
    q->pnext=NULL;
    L.ptail=q;
    delete p;   
}