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ó.
Các thao tác trên danh sách liên kết đơn(single-link list)
1. Định nghĩa tổng quát
PHP Code:
struct tq {
thtin_t phantu;
struc tq*tiep;
};
typedef struct tq tq_t;
2. Con trỏ tới 1 node
PHP Code:
struct node {
int infor;
struct node *next;
};
typedef struct node *NODEPTR;
3. Cấp phát bộ nhớ cho 1 node
PHP Code:
NODEPTR Getnode(void) {
NODEPTR p;
P = (NODEPTR) malloc(sizeof( struct node));
Return(p);
}
4. Giải phóng 1 node
PHP Code:
NODEPTR Freenode( NODEPTR p){
free(p);
}
5. Thêm phần tử vào đỉnh danh sách
PHP Code:
void Push_Top( NODEPTR *plist, int x) {
NODEPTR p;
p= Getnode();
p -> infor = x;
p ->next = *plist;
*plist = p;
}
6. Thêm node mới vào cuối danh sách
PHP Code:
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;
}
7. Thêm node mới vào giữa danh sách
PHP Code:
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;
}
}
8. Xóa 1 node đầu danh sách
PHP Code:
void Del_Top( NODEPTR *plist) {
NODEPTR p;
p = *plist;
if (p==NULL) return;
(*plist) = (*plist) -> next;
p-> next = NULL;
Freenode(p);
}
9. Xóa node cuối danh sách
PHP Code:
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;
}
// xoa node cuoi danh sach;
q->next =NULL;
Freenode(p);
}
}
10. Xóa node giữa danh sách
PHP Code:
void Del_before(NODEPTR p){
NODEPTR q;
if (p->next==NULL) return;
q = p ->next;
p->next = q->next;
Freenode(q);
}