Danh Sach Lien Ket Don

Ý tưởng: 
Khác với stack, queue danh sách liên kết đơn cũng là một kiểu danh sách tuyến tính gồm các phần tử vào lần lượt theo thứ tự tuy nhiên nó khác stack và queue ở chỗ là nó được cấp phát trong bộ nhớ bởi các phần tử rời rạc nhau, không nằm kề nhau, tuy nhiên giữa phần tử trước thì có 1 liên kết đến phần tử sau nó.
Thông thường thì người ta xây dựng stack, queue bằng mảng, nhưng điểm hạn chế là nó sẽ bị giới hạn về số lượng phần tử, bởi thế cách hay nhất là xây dựng stack, queue bẳng danh sách liên kết đơn ==> stack, queue là 1 danh sách liên kết đơn.

Các thao tác trên danh sách liên kết đơn(single-link list):

Định nghĩa tổng quát

struct tq {
thtin_t phantu;
struc tq*tiep;
};
typedef struct tq tq_t;

Con trỏ tới 1 node

struct  node {
        int infor;
        struct node *next;
    };
    typedef struct node *NODEPTR;

Cấp phát bộ nhớ cho 1 node

NODEPTR Getnode(void) {
    NODEPTR p;
    P = (NODEPTR) malloc(sizeof( struct node));
    Return(p);
}

Giải phóng 1 node

NODEPTR Freenode( NODEPTR p){
        free(p);
    }

Thêm phần tử vào đỉnh danh sách

void Push_Top( NODEPTR *plist, int x) {
    NODEPTR p;
    p= Getnode();
    p -> infor = x;
    p ->next = *plist;
    *plist = p;
}

Thêm node mới vào cuối danh sách

void Push_Bottom( NODEPTR *plist, int x) {
    NODEPTR p, q;
    p= Getnode(); //
    p->infor = x;
    q = *plist;
    while (q-> next != NULL)
        q = q -> next;
   
    q -> next = p;
    p ->next = NULL;
}

Thêm node mới vào giữa danh sách

void Push_Before( NODEPTR p, int x ){
    NODEPTR q;
    if (p->next==NULL)
        Push_Bottom(p, x);
    else {
        q= Getnode();
        q -> infor = x;
        q-> next = p-> next;  
        p->next = q;
    }
}

Xóa 1 node đầu danh sách

void Del_Top( NODEPTR *plist) {
    NODEPTR p;
    p = *plist;
    if (p==NULL) return;
    (*plist) = (*plist) -> next;
    p-> next = NULL;
    Freenode(p);
}

Xóa node cuối danh sách

void Del_Bottom(NODEPTR *plist) {
    NODEPTR p, q;
    if (*plist==NULL) return;
    else if ( (*plist)->next==NULL))
        Del_Top(plist);
    else {
        p = *plist;
        while (p->next!=NULL){
            q = p;
            p = p->next;
        }
        // p lµ node cuèi danh s¸ch;
        q->next =NULL;
        Freenode(p);
    }
}

Xóa node giữa danh sách

void Del_before(NODEPTR p){
    NODEPTR q;
    if (p->next==NULL) return;
    q = p ->next;
    p->next = q->next;
    Freenode(q);
}