Khi chúng tôi đang phát triển phần mềm, chúng tôi phải lưu trữ dữ liệu trong bộ nhớ. Tuy nhiên, nhiều loại cấu trúc dữ liệu, chẳng hạn như mảng, bản đồ, bộ, danh sách, cây, đồ thị, v.v. và việc chọn đúng cho nhiệm vụ có thể phức tạp. Chuỗi bài viết này sẽ giúp bạn biết được sự đánh đổi để có thể sử dụng đúng công cụ cho công việc
Phần này sẽ tập trung vào cấu trúc dữ liệu tuyến tính. Mảng, danh sách, tập hợp, ngăn xếp và hàng đợi
Bạn có thể tìm thấy tất cả các triển khai này và hơn thế nữa trong repo Github. https. //github. com/amejiarosario/dsa. js
Bài đăng này là một phần của loạt bài hướng dẫn
Học thuật toán và cấu trúc dữ liệu (DSA) cho người mới bắt đầu
Giới thiệu về độ phức tạp thời gian của thuật toán và ký hiệu Big O
Tám độ phức tạp thời gian mà mọi lập trình viên nên biết
Cấu trúc dữ liệu cho người mới bắt đầu. Mảng, HashMap và Danh sách 👈 bạn đang ở đây
Cấu trúc dữ liệu đồ thị cho người mới bắt đầu
Cây cấu trúc dữ liệu cho người mới bắt đầu
Cây tìm kiếm nhị phân tự cân bằng
Phụ lục I. Phân tích thuật toán đệ quy
Cấu trúc dữ liệu Big-O Cheatsheet
Bảng sau đây là một bản tóm tắt của tất cả mọi thứ mà chúng tôi sẽ bao gồm
Đánh dấu trang, ghim hoặc chia sẻ để bạn luôn có sẵn khi cần
Bấm vào tên để đi đến phần hoặc bấm vào thời gian chạy để đi đến việc thực hiện
function remove(array, element) {
const index = search(array, element);
array.splice(index, 1);
return array;
}
const array1 = [0, 1, 2, 3];
console.log(remove(array1, 1)); // => [ 0, 2, 3 ]
4 = Thời gian chạy khấu hao
const index = search(array, element);
array.splice(index, 1);
return array;
}
const array1 = [0, 1, 2, 3];
console.log(remove(array1, 1)); // => [ 0, 2, 3 ]
5. Chi tiết tại đây. HashMapO(1)O(1)O(1)O(1)Việc băm lại có thể ảnh hưởng đến thời gian chèn. Chi tiết tại đây. Bản đồ (sử dụng Cây tìm kiếm nhị phân)O(log(n))-O(log(n))O(log(n))Được triển khai bằng Bộ cây tìm kiếm nhị phân (sử dụng HashMap)O(1)-O(1)O(1 . Chi tiết tại đây. Đặt (sử dụng danh sách)O(n)-O(n)O(n)Được triển khai bằng Cây tìm kiếm nhị phânSet (sử dụng Cây tìm kiếm nhị phân)O(log(n))-O(log(n))O(log(n) . Chi tiết tại đây. Danh sách Liên kết (đôi)O(n)-O(n)O(n)Thêm/Xóa từ đầu/cuối là function remove(array, element) {
const index = search(array, element);
array.splice(index, 1);
return array;
}
const array1 = [0, 1, 2, 3];
console.log(remove(array1, 1)); // => [ 0, 2, 3 ]
5. Nhưng, xóa/thêm từ giữa là function remove(array, element) {
const index = search(array, element);
array.splice(index, 1);
return array;
}
const array1 = [0, 1, 2, 3];
console.log(remove(array1, 1)); // => [ 0, 2, 3 ]
8. Chi tiết tại đâyStack (triển khai mảng)O(1)--O(1)Chèn/xóa là nhập sau, xuất trước (LIFO)Hàng đợi (ngụ ý mảng ngây thơ. )O(1)--O(n)Remove (_______09) là O(n)Hàng đợi (triển khai mảng)O(1)--O(1)Chèn thời gian tồi tệ nhất là O(n). Tuy nhiên, khấu hao là O(1)Hàng đợi (triển khai danh sách)O(1)--O(1)Sử dụng Danh sách liên kết kép có tham chiếu đến phần tử cuối cùng
Ghi chú. Cây tìm kiếm nhị phân và cây nói chung sẽ được đề cập trong bài tiếp theo. Ngoài ra, cấu trúc dữ liệu đồ thị