Khái niệm: Danh sách liên kết đơn là một cấu trúc dữ liệu bao gồm một tập các nút, mà mỗi nút bao gồm:

§ Dữ liệu cần lưu trữ;

§ Liên kết trỏ đến nút tiếp theo.

Các thao tác trên danh sách liên kết đơn

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

1. struct node {

2. int data;

3. struct node *link;

4. };

5. typedef struct node *nodeptr;

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

1. nodeptrcapphat(void) {

2. nodeptrp;

3. p = (nodeptr) malloc(sizeof( struct node));

4. return(p);

5. }

Giải phóng 1 node

1. nodeptrgiaiphong( nodeptrp){

2. free(p);

3. }

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

1. void themdau( nodeptr*first, int x) {

2. nodeptrp;

3. p= capphat();

4. p -> data= x;

5. p ->link= *first;

6. *first= p;

7. }

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

1. void themcuoi( nodeptr*first, int x) {

2. nodeptrp, q;

3. p= capphat();

4. p->data= x;

5. q = *first;

6. while (q-> link!= NULL)

7. q = q -> link;

8. q -> link= p;

9. p ->link= NULL;

10. }