Danh sách

Một danh sách (list) là một khái niệm cấu trúc dữ liệu trừu tượng biểu diễn một tập hợp các phần tử có thứ tự, hỗ trợ các thao tác như truy cập, sửa đổi, chèn, xóa và duyệt qua các phần tử, mà không yêu cầu người dùng phải xem xét các giới hạn về dung lượng. Danh sách có thể được triển khai dựa trên danh sách liên kết hoặc mảng.

• Một danh sách liên kết có thể được coi là một danh sách một cách tự nhiên: nó hỗ trợ chèn, xóa, tìm kiếm và cập nhật, đồng thời có thể tăng kích thước linh hoạt khi cần thiết.
• Một mảng cũng hỗ trợ chèn, xóa, tìm kiếm và cập nhật, nhưng vì độ dài của nó là cố định, nên nó chỉ có thể được coi là một danh sách có giới hạn dung lượng.

Khi một danh sách được triển khai bằng mảng, độ dài cố định của nó làm cho nó kém thực tế hơn. Điều này là do chúng ta thường không thể xác định trước lượng dữ liệu cần lưu trữ là bao nhiêu, khiến việc chọn một dung lượng thích hợp trở nên khó khăn. Nếu dung lượng quá nhỏ sẽ không đáp ứng được nhu cầu; nếu quá lớn sẽ gây lãng phí không gian bộ nhớ.

Để giải quyết vấn đề này, chúng ta có thể sử dụng một mảng động (dynamic array) để triển khai danh sách. Nó thừa hưởng tất cả các ưu điểm của mảng trong khi hỗ trợ thay đổi kích thước động trong quá trình thực thi chương trình.

Trên thực tế, các kiểu danh sách được cung cấp bởi thư viện chuẩn của nhiều ngôn ngữ lập trình đều được triển khai bằng mảng động, ví dụ như list trong Python, ArrayList trong Java, vector trong C++, và List trong C#. Trong các phần thảo luận sau đây, chúng ta sẽ coi "danh sách" và "mảng động" là các khái niệm tương đương.

Các thao tác danh sách thông thường

Khởi tạo danh sách

Chúng ta thường khởi tạo danh sách theo một trong hai cách: rỗng hoặc có giá trị xác định trước:

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

list.py

# Khởi tạo danh sách
# Không có giá trị khởi tạo
nums1: list[int] = []
# Có giá trị khởi tạo
nums: list[int] = [1, 3, 2, 5, 4]

list.cpp

/* Khởi tạo danh sách */
// Lưu ý rằng vector trong C++ tương đương với nums được mô tả trong bài viết này
// Không có giá trị khởi tạo
vector<int> nums1;
// Có giá trị khởi tạo
vector<int> nums = { 1, 3, 2, 5, 4 };

list.java

/* Khởi tạo danh sách */
// Không có giá trị khởi tạo
List<Integer> nums1 = new ArrayList<>();
// Có giá trị khởi tạo (lưu ý rằng các phần tử mảng nên sử dụng lớp bao bọc Integer[] thay vì int[])
Integer[] numbers = new Integer[] { 1, 3, 2, 5, 4 };
List<Integer> nums = new ArrayList<>(Arrays.asList(numbers));

list.cs

/* Khởi tạo danh sách */
// Không có giá trị khởi tạo
List<int> nums1 = [];
// Có giá trị khởi tạo
int[] numbers = [1, 3, 2, 5, 4];
List<int> nums = [.. numbers];

list_test.go

/* Khởi tạo danh sách */
// Không có giá trị khởi tạo
nums1 := []int{}
// Có giá trị khởi tạo
nums := []int{1, 3, 2, 5, 4}

list.swift

/* Khởi tạo danh sách */
// Không có giá trị khởi tạo
let nums1: [Int] = []
// Có giá trị khởi tạo
var nums = [1, 3, 2, 5, 4]

list.js

/* Khởi tạo danh sách */
// Không có giá trị khởi tạo
const nums1 = [];
// Có giá trị khởi tạo
const nums = [1, 3, 2, 5, 4];

list.ts

/* Khởi tạo danh sách */
// Không có giá trị khởi tạo
const nums1: number[] = [];
// Có giá trị khởi tạo
const nums: number[] = [1, 3, 2, 5, 4];

list.dart

/* Khởi tạo danh sách */
// Không có giá trị khởi tạo
List<int> nums1 = [];
// Có giá trị khởi tạo
List<int> nums = [1, 3, 2, 5, 4];

list.rs

/* Khởi tạo danh sách */
// Không có giá trị khởi tạo
let nums1: Vec<i32> = Vec::new();
// Có giá trị khởi tạo
let nums: Vec<i32> = vec![1, 3, 2, 5, 4];

list.c

// C không cung cấp mảng động được dựng sẵn

list.kt

/* Khởi tạo danh sách */
// Không có giá trị khởi tạo
var nums1 = listOf<Int>()
// Có giá trị khởi tạo
var numbers = arrayOf(1, 3, 2, 5, 4)
var nums = numbers.toMutableList()

list.rb

# Khởi tạo danh sách
# Không có giá trị khởi tạo
nums1 = []
# Có giá trị khởi tạo
nums = [1, 3, 2, 5, 4]

Trực quan hóa mã nguồn

https://pythontutor.com/render.html#code=%22%22%22Driver%20Code%22%22%22%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20%23%20%E5%88%9D%E5%A7%8B%E5%8C%96%E5%88%97%E8%A1%A8%0A%20%20%20%20%23%20%E6%97%A0%E5%88%9D%E5%A7%8B%E5%80%BC%0A%20%20%20%20nums1%20%3D%20%5B%5D%0A%20%20%20%20%23%20%E6%9C%89%E5%88%9D%E5%A7%8B%E5%80%BC%0A%20%20%20%20nums%20%3D%20%5B1,%203,%202,%205,%204%5D%&cumulative=false&curInstr=4&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=311&rawInputLstJSON=%5B%5D&textReferences=false

Truy cập phần tử

Vì danh sách về bản chất là một mảng, chúng ta có thể truy cập và cập nhật các phần tử với độ phức tạp thời gian \(O(1)\), điều này rất hiệu quả.

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

list.py

# Truy cập phần tử
num: int = nums[1]  # Truy cập phần tử tại chỉ số 1

# Cập nhật phần tử
nums[1] = 0    # Cập nhật phần tử tại chỉ số 1 thành 0

list.cpp

/* Truy cập phần tử */
int num = nums[1];  // Truy cập phần tử tại chỉ số 1

/* Cập nhật phần tử */
nums[1] = 0;  // Cập nhật phần tử tại chỉ số 1 thành 0

list.java

/* Truy cập phần tử */
int num = nums.get(1);  // Truy cập phần tử tại chỉ số 1

/* Cập nhật phần tử */
nums.set(1, 0);  // Cập nhật phần tử tại chỉ số 1 thành 0

list.cs

/* Truy cập phần tử */
int num = nums[1];  // Truy cập phần tử tại chỉ số 1

/* Cập nhật phần tử */
nums[1] = 0;  // Cập nhật phần tử tại chỉ số 1 thành 0

list_test.go

/* Truy cập phần tử */
num := nums[1]  // Truy cập phần tử tại chỉ số 1

/* Cập nhật phần tử */
nums[1] = 0     // Cập nhật phần tử tại chỉ số 1 thành 0

list.swift

/* Truy cập phần tử */
let num = nums[1] // Truy cập phần tử tại chỉ số 1

/* Cập nhật phần tử */
nums[1] = 0 // Cập nhật phần tử tại chỉ số 1 thành 0

list.js

/* Truy cập phần tử */
const num = nums[1];  // Truy cập phần tử tại chỉ số 1

/* Cập nhật phần tử */
nums[1] = 0;  // Cập nhật phần tử tại chỉ số 1 thành 0

list.ts

/* Truy cập phần tử */
const num: number = nums[1];  // Truy cập phần tử tại chỉ số 1

/* Cập nhật phần tử */
nums[1] = 0;  // Cập nhật phần tử tại chỉ số 1 thành 0

list.dart

/* Truy cập phần tử */
int num = nums[1];  // Truy cập phần tử tại chỉ số 1

/* Cập nhật phần tử */
nums[1] = 0;  // Cập nhật phần tử tại chỉ số 1 thành 0

list.rs

/* Truy cập phần tử */
let num: i32 = nums[1];  // Truy cập phần tử tại chỉ số 1
/* Cập nhật phần tử */
nums[1] = 0;             // Cập nhật phần tử tại chỉ số 1 thành 0

list.c

// C không cung cấp mảng động được dựng sẵn

list.kt

/* Truy cập phần tử */
val num = nums[1]       // Truy cập phần tử tại chỉ số 1
/* Cập nhật phần tử */
nums[1] = 0             // Cập nhật phần tử tại chỉ số 1 thành 0

list.rb

# Truy cập phần tử
num = nums[1] # Truy cập phần tử tại chỉ số 1
# Cập nhật phần tử
nums[1] = 0 # Cập nhật phần tử tại chỉ số 1 thành 0

Trực quan hóa mã nguồn

https://pythontutor.com/render.html#code=%22%22%22Driver%20Code%22%22%22%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20%23%20%E5%88%9D%E5%A7%8B%E5%8C%96%E5%88%97%E8%A1%A8%0A%20%20%20%20nums%20%3D%20%5B1,%203,%202,%205,%204%5D%0A%0A%20%20%20%20%23%20%E8%AE%BF%E9%97%AE%E5%85%83%E7%B4%A0%0A%20%20%20%20num%20%3D%20nums%5B1%5D%20%20%23%20%E8%AE%BF%E9%97%AE%E7%B4%A2%E5%BC%95%201%20%E5%A4%84%E7%9A%84%E5%85%83%E7%B4%A0%0A%0A%20%20%20%20%23%20%E6%9B%B4%E6%96%B0%E5%85%83%E7%B4%A0%0A%20%20%20%20nums%5B1%5D%20%3D%200%20%20%20%20%23%20%E5%B0%86%E7%B4%A2%E5%BC%95%201%20%E5%A4%84%E7%9A%84%E5%85%83%E7%B4%A0%E6%9B%B4%E6%96%B0%E4%B8%BA%200&cumulative=false&curInstr=3&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=311&rawInputLstJSON=%5B%5D&textReferences=false

Chèn và xóa phần tử

So với mảng, danh sách có thể thêm và xóa phần tử một cách tự do. Thêm một phần tử vào cuối danh sách có độ phức tạp thời gian là \(O(1)\), nhưng việc chèn và xóa phần tử vẫn có hiệu năng tương tự như mảng, với độ phức tạp thời gian là \(O(n)\).

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

list.py

# Xóa sạch danh sách
nums.clear()

# Thêm phần tử vào cuối
nums.append(1)
nums.append(3)
nums.append(2)
nums.append(5)
nums.append(4)

# Chèn một phần tử vào giữa
nums.insert(3, 6)  # Chèn số 6 tại chỉ số 3

# Xóa một phần tử
nums.pop(3)        # Xóa phần tử tại chỉ số 3

list.cpp

/* Xóa sạch danh sách */
nums.clear();

/* Thêm phần tử vào cuối */
nums.push_back(1);
nums.push_back(3);
nums.push_back(2);
nums.push_back(5);
nums.push_back(4);

/* Chèn một phần tử vào giữa */
nums.insert(nums.begin() + 3, 6);  // Chèn số 6 tại chỉ số 3

/* Xóa một phần tử */
nums.erase(nums.begin() + 3);      // Xóa phần tử tại chỉ số 3

list.java

/* Xóa sạch danh sách */
nums.clear();

/* Thêm phần tử vào cuối */
nums.add(1);
nums.add(3);
nums.add(2);
nums.add(5);
nums.add(4);

/* Chèn một phần tử vào giữa */
nums.add(3, 6);  // Chèn số 6 tại chỉ số 3

/* Xóa một phần tử */
nums.remove(3);  // Xóa phần tử tại chỉ số 3

list.cs

/* Xóa sạch danh sách */
nums.Clear();

/* Thêm phần tử vào cuối */
nums.Add(1);
nums.Add(3);
nums.Add(2);
nums.Add(5);
nums.Add(4);

/* Chèn một phần tử vào giữa */
nums.Insert(3, 6);  // Chèn số 6 tại chỉ số 3

/* Xóa một phần tử */
nums.RemoveAt(3);  // Xóa phần tử tại chỉ số 3

list_test.go

/* Xóa sạch danh sách */
nums = nil

/* Thêm phần tử vào cuối */
nums = append(nums, 1)
nums = append(nums, 3)
nums = append(nums, 2)
nums = append(nums, 5)
nums = append(nums, 4)

/* Chèn một phần tử vào giữa */
nums = append(nums[:3], append([]int{6}, nums[3:]...)...) // Chèn số 6 tại chỉ số 3

/* Xóa một phần tử */
nums = append(nums[:3], nums[4:]...) // Xóa phần tử tại chỉ số 3

list.swift

/* Xóa sạch danh sách */
nums.removeAll()

/* Thêm phần tử vào cuối */
nums.append(1)
nums.append(3)
nums.append(2)
nums.append(5)
nums.append(4)

/* Chèn một phần tử vào giữa */
nums.insert(6, at: 3) // Chèn số 6 tại chỉ số 3

/* Xóa một phần tử */
nums.remove(at: 3) // Xóa phần tử tại chỉ số 3

list.js

/* Xóa sạch danh sách */
nums.length = 0;

/* Thêm phần tử vào cuối */
nums.push(1);
nums.push(3);
nums.push(2);
nums.push(5);
nums.push(4);

/* Chèn một phần tử vào giữa */
nums.splice(3, 0, 6); // Chèn số 6 tại chỉ số 3

/* Xóa một phần tử */
nums.splice(3, 1);  // Xóa phần tử tại chỉ số 3

list.ts

/* Xóa sạch danh sách */
nums.length = 0;

/* Thêm phần tử vào cuối */
nums.push(1);
nums.push(3);
nums.push(2);
nums.push(5);
nums.push(4);

/* Chèn một phần tử vào giữa */
nums.splice(3, 0, 6); // Chèn số 6 tại chỉ số 3

/* Xóa một phần tử */
nums.splice(3, 1);  // Xóa phần tử tại chỉ số 3

list.dart

/* Xóa sạch danh sách */
nums.clear();

/* Thêm phần tử vào cuối */
nums.add(1);
nums.add(3);
nums.add(2);
nums.add(5);
nums.add(4);

/* Chèn một phần tử vào giữa */
nums.insert(3, 6); // Chèn số 6 tại chỉ số 3

/* Xóa một phần tử */
nums.removeAt(3); // Xóa phần tử tại chỉ số 3

list.rs

/* Xóa sạch danh sách */
nums.clear();

/* Thêm phần tử vào cuối */
nums.push(1);
nums.push(3);
nums.push(2);
nums.push(5);
nums.push(4);

/* Chèn một phần tử vào giữa */
nums.insert(3, 6);  // Chèn số 6 tại chỉ số 3

/* Xóa một phần tử */
nums.remove(3);    // Xóa phần tử tại chỉ số 3

list.c

// C không cung cấp mảng động được dựng sẵn

list.kt

/* Xóa sạch danh sách */
nums.clear();

/* Thêm phần tử vào cuối */
nums.add(1);
nums.add(3);
nums.add(2);
nums.add(5);
nums.add(4);

/* Chèn một phần tử vào giữa */
nums.add(3, 6);  // Chèn số 6 tại chỉ số 3

/* Xóa một phần tử */
nums.remove(3);  // Xóa phần tử tại chỉ số 3

list.rb

# Xóa sạch danh sách
nums.clear

# Thêm phần tử vào cuối
nums << 1
nums << 3
nums << 2
nums << 5
nums << 4

# Chèn một phần tử vào giữa
nums.insert(3, 6) # Chèn số 6 tại chỉ số 3

# Xóa một phần tử
nums.delete_at(3) # Xóa phần tử tại chỉ số 3

Trực quan hóa mã nguồn

https://pythontutor.com/render.html#code=%22%22%22Driver%20Code%22%22%22%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20%23%20%E6%9C%89%E5%88%9D%E5%A7%8B%E5%80%BC%0A%20%20%20%20nums%20%3D%20%5B1,%203,%202,%205,%204%5D%0A%20%20%20%20%0A%20%20%20%20%23%20%E6%B8%85%E7%A9%BA%E5%88%97%E8%A1%A8%0A%20%20%20%20nums.clear%28%29%0A%20%20%20%20%0A%20%20%20%20%23%20%E5%9C%A8%E5%B0%BE%E9%83%A8%E6%B7%BB%E5%8A%A0%E5%85%83%E7%B4%A0%0A%20%20%20%20nums.append%281%29%0A%20%20%20%20nums.append%283%29%0A%20%20%20%20nums.append%282%29%0A%20%20%20%20nums.append%285%29%0A%20%20%20%20nums.append%284%29%0A%20%20%20%20%0A%20%20%20%20%23%20%E5%9C%A8%E4%B8%AD%E9%97%B4%E6%8F%92%E5%85%A5%E5%85%83%E7%B4%A0%0A%20%20%20%20nums.insert%283,%206%29%20%20%23%20%E5%9C%A8%E7%B4%A2%E5%BC%95%203%20%E5%A4%84%E6%8F%92%E5%85%A5%E6%95%B0%E5%AD%97%206%0A%20%20%20%20%0A%20%20%20%20%23%20%E5%88%A0%E9%99%A4%E5%85%83%E7%B4%A0%0A%20%20%20%20nums.pop%283%29%20%20%20%20%20%20%20%20%23%20%E5%88%A0%E9%99%A4%E7%B4%A2%E5%BC%95%203%20%E5%A4%84%E7%9A%84%E5%85%83%E7%B4%A0&cumulative=false&curInstr=3&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=311&rawInputLstJSON=%5B%5D&textReferences=false

Duyệt danh sách

Tương tự như mảng, danh sách có thể được duyệt bằng chỉ số hoặc bằng cách lặp trực tiếp qua các phần tử.

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

list.py

# Duyệt danh sách bằng chỉ số
count = 0
for i in range(len(nums)):
    count += nums[i]

# Duyệt trực tiếp qua các phần tử danh sách
for num in nums:
    count += num

list.cpp

/* Duyệt danh sách bằng chỉ số */
int count = 0;
for (int i = 0; i < nums.size(); i++) {
    count += nums[i];
}

/* Duyệt trực tiếp qua các phần tử danh sách */
count = 0;
for (int num : nums) {
    count += num;
}

list.java

/* Duyệt danh sách bằng chỉ số */
int count = 0;
for (int i = 0; i < nums.size(); i++) {
    count += nums.get(i);
}

/* Duyệt trực tiếp qua các phần tử danh sách */
for (int num : nums) {
    count += num;
}

list.cs

/* Duyệt danh sách bằng chỉ số */
int count = 0;
for (int i = 0; i < nums.Count; i++) {
    count += nums[i];
}

/* Duyệt trực tiếp qua các phần tử danh sách */
count = 0;
foreach (int num in nums) {
    count += num;
}

list_test.go

/* Duyệt danh sách bằng chỉ số */
count := 0
for i := 0; i < len(nums); i++ {
    count += nums[i]
}

/* Duyệt trực tiếp qua các phần tử danh sách */
count = 0
for _, num := range nums {
    count += num
}

list.swift

/* Duyệt danh sách bằng chỉ số */
var count = 0
for i in nums.indices {
    count += nums[i]
}

/* Duyệt trực tiếp qua các phần tử danh sách */
count = 0
for num in nums {
    count += num
}

list.js

/* Duyệt danh sách bằng chỉ số */
let count = 0;
for (let i = 0; i < nums.length; i++) {
    count += nums[i];
}

/* Duyệt trực tiếp qua các phần tử danh sách */
count = 0;
for (const num of nums) {
    count += num;
}

list.ts

/* Duyệt danh sách bằng chỉ số */
let count = 0;
for (let i = 0; i < nums.length; i++) {
    count += nums[i];
}

/* Duyệt trực tiếp qua các phần tử danh sách */
count = 0;
for (const num of nums) {
    count += num;
}

list.dart

/* Duyệt danh sách bằng chỉ số */
int count = 0;
for (var i = 0; i < nums.length; i++) {
    count += nums[i];
}

/* Duyệt trực tiếp qua các phần tử danh sách */
count = 0;
for (var num in nums) {
    count += num;
}

list.rs

// Duyệt danh sách bằng chỉ số
let mut _count = 0;
for i in 0..nums.len() {
    _count += nums[i];
}

// Duyệt trực tiếp qua các phần tử danh sách
_count = 0;
for num in &nums {
    _count += num;
}

list.c

// C không cung cấp mảng động được dựng sẵn

list.kt

/* Duyệt danh sách bằng chỉ số */
var count = 0
for (i in nums.indices) {
    count += nums[i]
}

/* Duyệt trực tiếp qua các phần tử danh sách */
for (num in nums) {
    count += num
}

list.rb

# Duyệt danh sách bằng chỉ số
count = 0
for i in 0...nums.length
    count += nums[i]
end

# Duyệt trực tiếp qua các phần tử danh sách
count = 0
for num in nums
    count += num
end

Trực quan hóa mã nguồn

https://pythontutor.com/render.html#code=%22%22%22Driver%20Code%22%22%22%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20%23%20%E5%88%9D%E5%A7%8B%E5%8C%96%E5%88%97%E8%A1%A8%0A%20%20%20%20nums%20%3D%20%5B1,%203,%202,%205,%204%5D%0A%20%20%20%20%0A%20%20%20%20%23%20%E9%80%9A%E8%BF%87%E7%B4%A2%E5%BC%95%E9%81%8D%E5%8E%86%E5%88%97%E8%A1%A8%0A%20%20%20%20count%20%3D%200%0A%20%20%20%20for%20i%20in%20range%28len%28nums%29%29%3A%0A%20%20%20%20%20%20%20%20count%20%2B%3D%20nums%5Bi%5D%0A%0A%20%20%20%20%23%20%E7%9B%B4%E6%8E%A5%E9%81%8D%E5%8E%86%E5%88%97%E8%A1%A8%E5%85%83%E7%B4%A0%0A%20%20%20%20for%20num%20in%20nums%3A%0A%20%20%20%20%20%20%20%20count%20%2B%3D%20num&cumulative=false&curInstr=3&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=311&rawInputLstJSON=%5B%5D&textReferences=false

Ghép nối danh sách

Cho một danh sách mới nums1, chúng ta có thể ghép nối nó vào cuối danh sách ban đầu.

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

list.py

# Ghép nối hai danh sách
nums1: list[int] = [6, 8, 7, 10, 9]
nums += nums1  # Ghép nối danh sách nums1 vào cuối nums

list.cpp

/* Ghép nối hai danh sách */
vector<int> nums1 = { 6, 8, 7, 10, 9 };
// Ghép nối danh sách nums1 vào cuối nums
nums.insert(nums.end(), nums1.begin(), nums1.end());

list.java

/* Ghép nối hai danh sách */
List<Integer> nums1 = new ArrayList<>(Arrays.asList(new Integer[] { 6, 8, 7, 10, 9 }));
nums.addAll(nums1);  // Ghép nối danh sách nums1 vào cuối nums

list.cs

/* Ghép nối hai danh sách */
List<int> nums1 = [6, 8, 7, 10, 9];
nums.AddRange(nums1);  // Ghép nối danh sách nums1 vào cuối nums

list_test.go

/* Ghép nối hai danh sách */
nums1 := []int{6, 8, 7, 10, 9}
nums = append(nums, nums1...)  // Ghép nối danh sách nums1 vào cuối nums

list.swift

/* Ghép nối hai danh sách */
let nums1 = [6, 8, 7, 10, 9]
nums.append(contentsOf: nums1) // Ghép nối danh sách nums1 vào cuối nums

list.js

/* Ghép nối hai danh sách */
const nums1 = [6, 8, 7, 10, 9];
nums.push(...nums1);  // Ghép nối danh sách nums1 vào cuối nums

list.ts

/* Ghép nối hai danh sách */
const nums1: number[] = [6, 8, 7, 10, 9];
nums.push(...nums1);  // Ghép nối danh sách nums1 vào cuối nums

list.dart

/* Ghép nối hai danh sách */
List<int> nums1 = [6, 8, 7, 10, 9];
nums.addAll(nums1);  // Ghép nối danh sách nums1 vào cuối nums

list.rs

/* Ghép nối hai danh sách */
let nums1: Vec<i32> = vec![6, 8, 7, 10, 9];
nums.extend(nums1);

list.c

// C không cung cấp mảng động được dựng sẵn

list.kt

/* Ghép nối hai danh sách */
val nums1 = intArrayOf(6, 8, 7, 10, 9).toMutableList()
nums.addAll(nums1)  // Ghép nối danh sách nums1 vào cuối nums

list.rb

# Ghép nối hai danh sách
nums1 = [6, 8, 7, 10, 9]
nums += nums1

Trực quan hóa mã nguồn

https://pythontutor.com/render.html#code=%22%22%22Driver%20Code%22%22%22%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20%23%20%E5%88%9D%E5%A7%8B%E5%8C%96%E5%88%97%E8%A1%A8%0A%20%20%20%20nums%20%3D%20%5B1,%203,%202,%205,%204%5D%0A%20%20%20%20%0A%20%20%20%20%23%20%E6%8B%BC%E6%8E%A5%E4%B8%A4%E4%B8%AA%E5%88%97%E8%A1%A8%0A%20%20%20%20nums1%20%3D%20%5B6,%208,%207,%2010,%209%5D%0A%20%20%20%20nums%20%2B%3D%20nums1%20%20%23%20%E5%B0%86%E5%88%97%E8%A1%A8%20nums1%20%E6%8B%BC%E6%8E%A5%E5%88%B0%20nums%20%E4%B9%8B%E5%90%8E&cumulative=false&curInstr=3&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=311&rawInputLstJSON=%5B%5D&textReferences=false

Sắp xếp danh sách

Sau khi sắp xếp danh sách, chúng ta có thể sử dụng các thuật toán tìm kiếm nhị phân (binary search) và hai con trỏ (two-pointer) vốn rất thường gặp trong các bài toán thuật toán về mảng.

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

list.py

# Sắp xếp danh sách
nums.sort()  # Sau khi sắp xếp, các phần tử danh sách được sắp xếp từ nhỏ đến lớn

list.cpp

/* Sắp xếp danh sách */
sort(nums.begin(), nums.end());  // Sau khi sắp xếp, các phần tử danh sách được sắp xếp từ nhỏ đến lớn

list.java

/* Sắp xếp danh sách */
Collections.sort(nums);  // Sau khi sắp xếp, các phần tử danh sách được sắp xếp từ nhỏ đến lớn

list.cs

/* Sắp xếp danh sách */
nums.Sort(); // Sau khi sắp xếp, các phần tử danh sách được sắp xếp từ nhỏ đến lớn

list_test.go

/* Sắp xếp danh sách */
sort.Ints(nums)  // Sau khi sắp xếp, các phần tử danh sách được sắp xếp từ nhỏ đến lớn

list.swift

/* Sắp xếp danh sách */
nums.sort() // Sau khi sắp xếp, các phần tử danh sách được sắp xếp từ nhỏ đến lớn

list.js

/* Sắp xếp danh sách */
nums.sort((a, b) => a - b);  // Sau khi sắp xếp, các phần tử danh sách được sắp xếp từ nhỏ đến lớn

list.ts

/* Sắp xếp danh sách */
nums.sort((a, b) => a - b);  // Sau khi sắp xếp, các phần tử danh sách được sắp xếp từ nhỏ đến lớn

list.dart

/* Sắp xếp danh sách */
nums.sort(); // Sau khi sắp xếp, các phần tử danh sách được sắp xếp từ nhỏ đến lớn

list.rs

/* Sắp xếp danh sách */
nums.sort(); // Sau khi sắp xếp, các phần tử danh sách được sắp xếp từ nhỏ đến lớn

list.c

// C không cung cấp mảng động được dựng sẵn

list.kt

/* Sắp xếp danh sách */
nums.sort() // Sau khi sắp xếp, các phần tử danh sách được sắp xếp từ nhỏ đến lớn

list.rb

# Sắp xếp danh sách
nums = nums.sort { |a, b| a <=> b } # Sau khi sắp xếp, các phần tử danh sách được sắp xếp từ nhỏ đến lớn

Trực quan hóa mã nguồn

https://pythontutor.com/render.html#code=%22%22%22Driver%20Code%22%22%22%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20%23%20%E5%88%9D%E5%A7%8B%E5%8C%96%E5%88%97%E8%A1%A8%0A%20%20%20%20nums%20%3D%20%5B1,%203,%202,%205,%204%5D%0A%20%20%20%20%0A%20%20%20%20%23%20%E6%8E%92%E5%BA%8F%E5%88%97%E8%A1%A8%0A%20%20%20%20nums.sort%28%29%20%20%23%20%E6%8E%92%E5%BA%8F%E5%90%8E%EF%BC%8C%E5%88%97%E8%A1%A8%E5%85%83%E7%B4%A0%E4%BB%8E%E5%B0%8F%E5%88%B0%E5%A4%A7%E6%8E%92%E5%88%97&cumulative=false&curInstr=3&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=311&rawInputLstJSON=%5B%5D&textReferences=false

Triển khai danh sách

Nhiều ngôn ngữ lập trình tích hợp sẵn kiểu danh sách, chẳng hạn như Java, C++ và Python. Việc triển khai chúng khá phức tạp và các tham số được cân nhắc kỹ lưỡng, ví dụ như dung lượng ban đầu, bội số mở rộng, v.v. Bạn đọc quan tâm có thể tham khảo mã nguồn để tìm hiểu thêm.

Để hiểu sâu hơn về cách hoạt động của danh sách, chúng ta sẽ thử triển khai một danh sách đơn giản với ba cân nhắc thiết kế chính:

• Dung lượng ban đầu: Chọn một dung lượng ban đầu hợp lý cho mảng bên dưới. Trong ví dụ này, chúng ta chọn 10 làm dung lượng ban đầu.
• Theo dõi kích thước: Khai báo một biến size để ghi lại số lượng phần tử hiện tại trong danh sách và cập nhật biến này trong thời gian thực khi phần tử được chèn hoặc xóa. Dựa vào biến này, chúng ta có thể xác định vị trí cuối danh sách và quyết định xem có cần mở rộng hay không.
• Cơ chế mở rộng: Khi dung lượng danh sách đã đầy tại thời điểm chèn phần tử, chúng ta cần mở rộng. Chúng ta tạo một mảng lớn hơn dựa trên bội số mở rộng, sau đó di chuyển tuần tự toàn bộ phần tử từ mảng hiện tại sang mảng mới. Trong ví dụ này, chúng ta quy định mảng sẽ được mở rộng gấp 2 lần kích thước trước đó mỗi lần.

[file]{my_list}-[class]{my_list}-[func]{}