1. Khái niệm và phân loại
Danh sách tuyến tính là một dãy hữu hạn gồm n phần tử cùng kiểu. Về mặt logic, nó có cấu trúc tuyến tính (liên tiếp), nhưng về mặt vật lý có thể được lưu trữ dưới dạng mảng (liên tục) hoặc con trỏ (rời rạc).
Danh sách tuần tự là một dạng của danh sách tuyến tính, trong đó các phần tử được lưu trữ liên tiếp trong bộ nhớ — thường dựa trên mảng.
1.1 Phân loại
- Danh sách tĩnh: sử dụng mảng có kích thước cố định. Nhược điểm: khó mở rộng, dễ lãng phí bộ nhớ.
- Danh sách động: cấp phát bộ nhớ linh hoạt bằng
malloc/realloc, cho phép thay đổi kích thước khi cần.
2. Triển khai danh sách tuần tự động
2.1 Cấu trúc dữ liệu
typedef int SLDataType;
typedef struct SeqList {
SLDataType* data;
int size; // số phần tử hiện tại
int capacity; // dung lượng bộ nhớ đã cấp
} SL;2.2 Các thao tác cơ bản
Khởi tạo
void SLInit(SL* list) {
assert(list);
list->data = NULL;
list->size = list->capacity = 0;
}Hủy bỏ
void SLDestroy(SL* list) {
assert(list);
free(list->data);
list->data = NULL;
list->size = list->capacity = 0;
}In danh sách
void SLPrint(const SL* list) {
for (int i = 0; i < list->size; ++i)
printf("%d ", list->data[i]);
printf("\n");
}2.3 Kiểm tra và mở rộng dung lượng
void SLEnsureCapacity(SL* list) {
if (list->size == list->capacity) {
int newCap = list->capacity ? list->capacity * 2 : 4;
SLDataType* tmp = (SLDataType*)realloc(list->data, newCap * sizeof(SLDataType));
if (!tmp) {
perror("realloc failed");
exit(EXIT_FAILURE);
}
list->data = tmp;
list->capacity = newCap;
}
}2.4 Chèn phần tử
Chèn cuối
void SLPushBack(SL* list, SLDataType value) {
assert(list);
SLEnsureCapacity(list);
list->data[list->size++] = value;
}Chèn đầu
void SLPushFront(SL* list, SLDataType value) {
assert(list);
SLEnsureCapacity(list);
for (int i = list->size; i > 0; --i)
list->data[i] = list->data[i - 1];
list->data[0] = value;
list->size++;
}Chèn tại vị trí
void SLInsert(SL* list, int index, SLDataType value) {
assert(list && index >= 0 && index <= list->size);
SLEnsureCapacity(list);
for (int i = list->size; i > index; --i)
list->data[i] = list->data[i - 1];
list->data[index] = value;
list->size++;
}2.5 Xóa phần tử
Xóa cuối
void SLPopBack(SL* list) {
assert(list && list->size > 0);
list->size--;
}Xóa đầu
void SLPopFront(SL* list) {
assert(list && list->size > 0);
for (int i = 0; i < list->size - 1; ++i)
list->data[i] = list->data[i + 1];
list->size--;
}Xóa tại vị trí
void SLErase(SL* list, int index) {
assert(list && index >= 0 && index < list->size);
for (int i = index; i < list->size - 1; ++i)
list->data[i] = list->data[i + 1];
list->size--;
}2.6 Tìm kiếm
int SLFind(const SL* list, SLDataType value) {
for (int i = 0; i < list->size; ++i)
if (list->data[i] == value)
return i;
return -1;
}3. Mã nguồn đầy đủ
SeqList.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLDataType;
typedef struct SeqList {
SLDataType* data;
int size;
int capacity;
} SL;
void SLInit(SL* list);
void SLDestroy(SL* list);
void SLPrint(const SL* list);
void SLEnsureCapacity(SL* list);
void SLPushBack(SL* list, SLDataType value);
void SLPushFront(SL* list, SLDataType value);
void SLInsert(SL* list, int index, SLDataType value);
void SLPopBack(SL* list);
void SLPopFront(SL* list);
void SLErase(SL* list, int index);
int SLFind(const SL* list, SLDataType value);SeqList.c
#include "SeqList.h"
void SLInit(SL* list) {
assert(list);
list->data = NULL;
list->size = list->capacity = 0;
}
void SLDestroy(SL* list) {
assert(list);
free(list->data);
list->data = NULL;
list->size = list->capacity = 0;
}
void SLPrint(const SL* list) {
for (int i = 0; i < list->size; ++i)
printf("%d ", list->data[i]);
printf("\n");
}
void SLEnsureCapacity(SL* list) {
if (list->size == list->capacity) {
int newCap = list->capacity ? list->capacity * 2 : 4;
SLDataType* tmp = realloc(list->data, newCap * sizeof(SLDataType));
if (!tmp) {
perror("realloc failed");
exit(EXIT_FAILURE);
}
list->data = tmp;
list->capacity = newCap;
}
}
void SLPushBack(SL* list, SLDataType value) {
assert(list);
SLEnsureCapacity(list);
list->data[list->size++] = value;
}
void SLPushFront(SL* list, SLDataType value) {
assert(list);
SLEnsureCapacity(list);
for (int i = list->size; i > 0; --i)
list->data[i] = list->data[i - 1];
list->data[0] = value;
list->size++;
}
void SLInsert(SL* list, int index, SLDataType value) {
assert(list && index >= 0 && index <= list->size);
SLEnsureCapacity(list);
for (int i = list->size; i > index; --i)
list->data[i] = list->data[i - 1];
list->data[index] = value;
list->size++;
}
void SLPopBack(SL* list) {
assert(list && list->size > 0);
list->size--;
}
void SLPopFront(SL* list) {
assert(list && list->size > 0);
for (int i = 0; i < list->size - 1; ++i)
list->data[i] = list->data[i + 1];
list->size--;
}
void SLErase(SL* list, int index) {
assert(list && index >= 0 && index < list->size);
for (int i = index; i < list->size - 1; ++i)
list->data[i] = list->data[i + 1];
list->size--;
}
int SLFind(const SL* list, SLDataType value) {
for (int i = 0; i < list->size; ++i)
if (list->data[i] == value)
return i;
return -1;
}test.c
#include "SeqList.h"
void runTest() {
SL list;
SLInit(&list);
SLPushBack(&list, 1);
SLPushBack(&list, 2);
SLPushBack(&list, 3);
SLPrint(&list); // 1 2 3
SLPushFront(&list, 0);
SLPrint(&list); // 0 1 2 3
SLInsert(&list, 2, 99);
SLPrint(&list); // 0 1 99 2 3
SLErase(&list, 2);
SLPrint(&list); // 0 1 2 3
SLPopFront(&list);
SLPopBack(&list);
SLPrint(&list); // 1 2
SLDestroy(&list);
}
int main() {
runTest();
return 0;
}4. Hạn chế và hướng cải tiến
Danh sách tuần tự có ba nhược điểm chính:
- Chèn/xóa ở đầu hoặc giữa yêu cầu dịch chuyển dữ liệu → độ phức tạp O(N).
- Mở rộng bộ nhớ tốn kém do phải cấp phát mới, sao chép và giải phóng cũ.
- Cấp phát theo bội số (thường là ×2) dẫn đến lãng phí không gian.
Để khắc phục, ta có thể sử dụng danh sách liên kết — cấu trúc cho phép chèn/xóa nhanh mà không cần dịch chuyển, đồng thời sử dụng bộ nhớ rời rạc, tránh lãng phí.