Danh sách liên kết (Linked List) trong C
Bước 1:
Định nghĩa cấu trúc nút của danh sách liên kết đơn.
struct Node { int data; struct Node *next; };
Cấu tạo của 1 Node gồm data, và 1 con trỏ next chứa địa chỉ của node tiếp theo.
Bước 2.Hàm Tạo 1 Node mới và trả địa chỉ Node.
struct Node* createNode(int data) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); if (newNode == NULL) { printf("Không đủ bộ nhớ\n"); exit(1); } newNode->data = data; newNode->next = NULL; return newNode; }
Hàm Tạo 1 Node mới và chứa dữ liệu data và con trỏ Trỏ tới NULL.
Bước 3.Hàm để chèn một nút mới vào đầu danh sách.
void insertAtBeginning(struct Node** head, int data) { struct Node* newNode = createNode(data); newNode->next = *head; *head = newNode; }
Bước 4: // Hàm để in ra danh sách liên kết đơn
void printList(struct Node* head) { struct Node* temp = head; while (temp != NULL) { printf("%d ", temp->data); temp = temp->next; } printf("\n"); }
Chương trình cụ thể như sau :
// Định nghĩa cấu trúc nút của danh sách liên kết đơn struct Node { int data; struct Node *next; }; // Hàm để tạo một nút mới struct Node* createNode(int data) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); if (newNode == NULL) { printf("Không đủ bộ nhớ\n"); exit(1); } newNode->data = data; newNode->next = NULL; return newNode; } // Hàm để chèn một nút mới vào đầu danh sách void insertAtBeginning(struct Node** head, int data) { struct Node* newNode = createNode(data); newNode->next = *head; *head = newNode; } // Hàm để in ra danh sách liên kết đơn void printList(struct Node* head) { struct Node* temp = head; while (temp != NULL) { printf("%d ", temp->data); temp = temp->next; } printf("\n"); } // Hàm chính int main() { struct Node* head = NULL; // Thêm các phần tử vào đầu danh sách insertAtBeginning(&head, 5); insertAtBeginning(&head, 4); insertAtBeginning(&head, 3); insertAtBeginning(&head, 2); insertAtBeginning(&head, 1); // In ra danh sách printf("Danh sách liên kết đơn: "); printList(head); return 0; }
Kết quả :
Sử dụng online compiler : https://www.programiz.com/c-programming/online-compiler/
Hàm insert vào Node cuối:
void insertAtEnd(struct Node** headRef, int data) { struct Node* newNode = createNode(data); if (*headRef == NULL) { *headRef = newNode; return; } struct Node* lastNode = *headRef; while (lastNode->next != NULL) { lastNode = lastNode->next; } lastNode->next = newNode; }