🧩Data structures
Cấu trúc dữ liệu là một storage được sử dụng để lưu trữ và tổ chức dữ liệu. Đó là tập hợp các cách tổ chức dữ liệu trên máy tính để có thể truy cập và cập nhật 1 cách hiệu quả.
Last updated
Cấu trúc dữ liệu là một storage được sử dụng để lưu trữ và tổ chức dữ liệu. Đó là tập hợp các cách tổ chức dữ liệu trên máy tính để có thể truy cập và cập nhật 1 cách hiệu quả.
Last updated
Tuỳ vào yêu cầu và project, điều quan trọng nhất là chọn đúng cấu trúc dữ liệu cho prj.
Ví dụ: Khi cần lưu kiểu dữ liệu tuần tự vào bộ nhớ, chúng ta có thể thao tác với Array DS.
Data structure and data types là 2 thứ hơi khác nhau. Data structure là tập hợp của các data type được sắp xếp theo thứ tự cụ thể.
Array in java là 1 nhóm các biến giống kiểu được gọi bằng tên chung. Arrays in Java hoạt động khác với C/C++. Dưới đây là 1 số điểm quan trọng trong Java arrays.
Trong java, tất cả các array được phân bổ động.
Là cấu trúc dữ liệu tĩnh với kích thước cố định.
Arrays được lưu trữ trong các bộ nhớ liền kề [vị trí bộ nhớ liên tiếp].
Vì Array là object trong java, chúng ta có thể đo chiều dài array bằng thuộc tính length.
A Java array variable can also be declared like other variables with [] after the data type.
Lớp cha trực tiếp của kiểu mảng là Object.
Kích thước của mảng không thể thay đổi (khi đã được khởi tạo). Tuy nhiên, một tham chiếu mảng có thể được tạo để trỏ đến một mảng khác.
Array cho phép truy xuất dữ liệu 1 cách nhanh chóng qua index giúp việc retrieve được tối ưu.
Array 2D giúp setup được các phép toán tuyến tính dễ dàng. Ứng dụng của nó (pixel) vào xử lí ảnh trong thời này rất phổ biến. Nó còn được ứng dụng vào đồ thị.
Vì cấu trúc đặc biệt mà nó còn được ứng dụng để triển khai các cấu trúc dữ liệu phức tạp hơn như ngăn xếp và hàng đợi.
Lưu kết quả của các phép toán con trong bài toán quy hoạch động.
Dễ dàng sắp xếp
Truy cập hiệu quả vào các phần tử: Array cung cấp quyền truy cập trực tiếp và hiệu quả vào bất kì vị trí nào trong collection. Truy cập phần tử trong array là phép toán O(1), nghĩa là thời gian truy cập vào mảng là 1 hằng số và không phụ thuộc vào kích thước mảng.
Truy xuất dữ liệu nhanh: Array cho phép truy xuất dữ liệu nhanh vì dữ liệu được lưu trữ trong các bộ nhớ liền kề. Điều này có nghĩa là dữ liệu có thể được truy xuất nhanh chóng và hiệu quả mà không cần đến các cấu trúc dữ liệu và thuật toán phức tạp.
Hiệu quả bộ nhớ: Array là 1 cách lưu trữ dữ liệu hiệu quả về bộ nhớ. Bởi vì phần tử của mảng được lưu trữ trong các vị trí bộ nhớ liền kề, kích thước mảnh cũng được biết trước vào thời điểm compile time. Điều này có nghĩa là bộ nhớ có thể được phân bổ cho toàn bộ mảng trong một khối, giúp giảm tình trạng phân mảnh bộ nhớ.
Linh hoạt: Array có thể được sử dụng để lưu nhiều kiểu dữ liệu khác nhau.
Dễ dàng sử dụng.
Khả năng tương thích với hardware: Cấu trúc dữ liệu mảng tương thích với hầu hết các kiến trúc phần cứng, làm cho nó trở thành một công cụ linh hoạt để lập trình trong nhiều môi trường.
Kích thước cố định: Vì kích thước mảng được cố định vào thời điểm khởi tạo nên khi cần tăng kích thước thì phải tạo 1 mảng mới và chép dữ liệu từ mảng cũ sang có thể gây lãng phí thời gian và bộ nhớ.
Vấn đề với việc phân bổ bộ nhớ: Việc phân bổ bộ nhớ cho 1 mảng lớn có thể là 1 vấn đề, đặc biệt là trong các hệ thống có bộ nhớ hạn chế. Nếu mảng quá lớn, hệ thống có thể hết bộ nhớ, điều này có thể gây ra lỗi cho ứng dụng.
Các vấn đề với chèn và xoá: Việc chèn hoặc xoá với array thực sự không hiệu quả và tốn thời gian vì sau mỗi điểm chèn hoặc xoá phải dịch chuyển để phù hợp với việc chuyển đổi.
Lãng phí bộ nhớ: Nếu 1 mảng được khai báo xong và không sử dụng hết dung lượng mảng. Đây có thể là 1 vấn đề với các hệ thống có bộ nhớ khiêm tốn.
Hỗ trợ dữ liệu hạn chế: Vì các phần tử trong mảng phải cùng kiểu dữ liệu, vậy nên sẽ có hạn chế với các kiểu dữ liệu như Object hay structures.
Thiếu linh hoạt: Kích thước cố định và hỗ trợ kiểu dữ liệu còn hạn chế làm cho Array thiếu linh hoạt hơn so với Link List hay Trees.
Linked List là 1 cấu trúc dữ liệu tuyến tính bao gồm 1 loạt các node được kết nối. Tại mỗi node, dữ liệu và địa chỉ của node tiếp theo được lưu trữ.
Bạn phải bắt đầu từ đâu đó, vì vậy chúng ta có node đầu tiên với 1 cái tên đặc biệt là HEAD. Tương tự, node cuối cùng của List có thể được xác định vì phần tiếp theo của nó trỏ đến NULL.
Linked lists có nhiều kiểu: singly, doubly, and circular linked list.
Nó giống như trò Truy tìm kho báu. Trong các mảnh bản đồ sẽ có thông tin và manh mối của mảnh bản đồ tiếp theo. Đó là cách hoạt động của Linked List.
Space Complexity: O(n)
Vì khả năng thêm và xoá với độ phức tạp là hằng số nên ứng dụng Linked List vào ngăn xếp và hàng đợi là phổ biến.
Thực hiện biểu đồ: vì trong mỗi node có lưu vị trí của node kế tiếp nên Linked List hỗ trợ mạnh mã trong việc thực thi các biểu đồ liền kề.
Cấp phát vùng nhớ động: Chúng ta sử dụng Linked List ở các khối dự do.
Thực hiện các phép toán số học với số nguyên dài.
Thao tác với các các đa thức bằng cách lưu các hằng số vào các node.
Trình bày các ma trận thưa thớt (hầu hết trong ma trận là số 0).
Kích thước động
Thêm và xoá nhanh và hiệu quả vì đơn giản chỉ cần thay đổi địa chỉ của node tiếp theo.
Hiệu quả về bộ nhớ: Vì chúng chỉ sử dụng nhiều bộ nhớ như chúng cần.
Dễ dàng sử dụng
Linh hoạt: Linked List có thể sử dụng nhiều kiểu dữ liệu trừu tượng khác nhau như ngăn xếp, hàng đợi hay mảng kết hợp.
Thời gian truy cập chậm: Việc phải truy cập qua các phần tử trước để đến được phần tử cần truy cập khiến cho việc truy cập trở nên phức tạp với O(n). Điều này khiến cho việc lựa chọn Linked List là 1 lựa chọn tồi nếu cần thời gian truy xuất dữ liệu nhanh.
Pointer: Việc sử dụng pointer để tham chiếu đến node kế tiếp, làm cho Linked List trông trở nên phức tạp để hiểu và sử dụng so với Array. Và sự phức tạp này cũng có thể là 1 vấn đề trong debug và maintain.
Chi phí cao hơn: Việc phải ghi nhớ vị trí của node kế tiếp khiến cho chi phí bộ nhớ của Linked List cao hơn so với Array.
Bộ nhớ cache không hiệu quả: vì vùng nhớ không phải là liền kề. Điều này có nghĩa là khi duyệt qua 1 linked list chúng ta không thể tìm dữ liệu cần trong bộ nhớ cache. Dẫn đến bộ đệm ẩn và hiệu suất chậm.
Map là một kiểu dữ liệu với mỗi phần tử là ánh xạ giữa yếu tố key (khóa) với giá trị (value) của nó. Tương tự set, map không chứa hai phần tử nào giống nhau và các phần tử trong map được sắp xếp theo một thứ tự nào đó. Mỗi phần tử trong map có yếu tố key dùng để xác định value của nó, điều này cũng có nghĩa là key và value có thể có kiểu khác nhau.
Lập chỉ mục và truy xuất: Map được sử dụng để lập chỉ mục các phần tử. Truy xuất các phần tử hiệu quả dựa trên các key của chúng.
Nhóm và phân loại chúng thành các nhóm khác nhau.
Network routes: Lưu các nút mạng từ đó tìm được đường đi ngắn nhất giữa các nút mạng dựa vào các thuật toán tìm đường đi.
Biểu diễn đồ thị: các đồ thị theo chiều sâu và chiều rộng.
Truy xuất nhanh: map sử dụng cây nhị phân để quản lý các cặp key-value, tức là truy xuất, chèn và xóa đều có thời gian logarithmic trong số lượng phần tử.
Tự động sắp xếp: map sẽ tự động sắp xếp các cặp key-value theo thứ tự tăng dần của key, giúp bạn dễ dàng tìm kiếm và duyệt qua các giá trị.
Tương thích với các kiểu dữ liệu khác nhau: map có thể lưu trữ bất kỳ kiểu dữ liệu nào có thể so sánh bằng toán tử <, giúp cho việc sử dụng nó trong các trường hợp khác nhau trở nên dễ dàng hơn.
Tốn tài nguyên: vì map lưu trữ cặp key, value nên sẽ tài nguyên bộ nhớ hơn.
Gây phức tạp nếu dữ liệu nhỏ.
Lặp thứ tự: trong hầu hết các cài đặt bản đồ, thứ tự key thường không được đảm bảo. Nếu cần thao tác map theo thứ tự cụ thể, sẽ phải tốn chi phí thời gian dành cho việc này.
Hiệu suất chậm hơn: mặc dù thường có độ phức tạp O(1) nhưng nó vẫn có hiệu suất chậm hơn so với Array
Giới hạn của key: Vì trong 1 số loại map key đòi hỏi phải băm
Set là một dạng cấu trúc dữ liệu dùng để lưu trữ các phần tử không trùng lặp và được sắp xếp theo thứ tự tăng dần hoặc giảm dần. (Mặc định trong set là tăng dần và chúng ta có thể viết lại hàm so sánh theo mục đích của chúng ta).
Trong môn Toán lớp 6, chúng ta đã tiếp xúc với khái niệm tập hợp, và biết đến tính chất không có hai phần tử nào trùng nhau trong một tập hợp. Và kiểu dữ liệu set có tính ưu việt hơn so với một tập hợp, ngoài tính chất không có hai phần tử nào giống nhau mà set còn có tính tự sắp xếp các phần tử (Có thể rút gọn một số công đoạn sắp xếp của bài toán).
Khi chúng ta làm việc với một cơ sở dữ liệu lớn và muốn lọc ra các trùng lặp hay kiểm tra xem 1 phần tử đã có trong tập hợp hay chưa. Set là 1 lựa chọn hoàn hảo vì nó cung cấp độ phức tạp về thời gian là không đổi.
Lưu trữ các unique values.
Các phần tử được sắp xếp giúp nó hoạt động hiệu quả hơn.
Cấp phát động nên không gặp phải vấn đề tràn bộ nhớ.
Độ phức tạp của tìm kiếm là O(logN).
Kiểm tra nhanh xem có 1 phần tử nào đó không.
Sets có thể được triển khai bằng cách sử dụng các cấu trúc dữ liệu khác nhau, chẳng hạn như HashSets và TreeSets, mỗi bộ có những ưu điểm và trường hợp sử dụng riêng.
Có thể được sử dụng trong nhiều ứng dụng, bao gồm thuật toán, phân tích dữ liệu và cơ sở dữ liệu.
Có thể được sử dụng để cải thiện hiệu suất trong nhiều thuật toán bằng cách cung cấp tra cứu nhanh.
Phần tử trong set có thể được truy cập bằng pointer, điều này có nghĩa là không có thể lập chỉ mục như Array.
Set rất phức tạp để thực hiện vì cấu trúc và thuộc tính của nó.
Tốn chi phí thời gian tận O(logN) cho các thao tác đơn giản như thêm, xoá.
Không phù hợp với dữ liệu lớn.
Set chỉ có thể lưu trữ dữ liệu trong cùng 1 kiểu dữ liệu cụ thể.
Tốn bộ nhớ hơn Array và List vì các phần tử được lưu trữ rời rạc.
Như đã xem qua cấu trúc của Array và Linked List ở trên, Vì Array có thể lập chỉ mục nên việc truy xuất dựa theo chỉ mục của Array làm cho tốc độ truy xuất là 1 hằng số. Còn với Linked List, Khi thực hiện thao tác thêm và xoá chính là hoạt động thay đổi địa chỉ của node kế tiếp nên độ phức tạp về thời gian của nó cũng là O(1).
Và chính vì cấu trúc của nó, nên việc thêm và xoá trên Array phải thao tác phức tạp với việc cắt ghép mảng và việc này cần thêm 1 mảng phụ nên thao tác này có độ phức tạp là O(n). Còn ở Linked List, Việc tổ chức các node liên kết với nhau như cấu trúc của nó giúp cho việc thêm xoá nhanh nhưng có 1 vấn đề ở đây, đó là khi cần truy xuất 1 phần tử nó buộc phải truy xuất qua hết các phần tử phía trước của phần tử cần truy xuất nên độ phức tạp của nó là O(n).
| Worst case | Average Case | |
|---|---|---|
| Truy xuất | Thêm | Xoá | |
|---|---|---|---|
| Array | |
|---|---|
| Array | Set |
|---|---|
Search
O(n)
O(n)
Insert
O(1)
O(1)
Deletion
O(1)
O(1)
Worst Case Scenario
Average Case Scenario
Best Case Scenario
Updating an element
O(N)
O(1)
O(1)
Insertion an element
O(N)
O(1)
O(1)
Deleting an element
O(N)
O(1)
O(1)
Searching an element
O(N)
O(1)
O(1)
Insert(TreeMap)
O(logN)
O(logN)
O(1)
Delete(TreeMap)
O(logN)
O(logN)
O(1)
Search(TreeMap)
O(logN)
O(logN)
O(1)
Array
O(1)
O(n)
O(n)
Linked List
O(n)
O(1)
O(1)
Array là 1 tập hợp các phần tử có cùng data type.
Map là 1 cấu trúc băm của 1 cặp key và value.
Chỉ mục phải là interger bắt đầu từ 0.
Key của map có thể là bất cứ kiểu dữ liệu nào.
Truy xuất bằng chỉ mục.
Truy xuất bằng key.
Thứ tự các phần tử đã nhập được duy trì.
Không đảm bảo duy trì thứ tự các phần tử đã nhập.
1D, 2D or multidimensional.
Multimap, Unordered Multimap, Unordered map, etc.
Kích cỡ được khai báo cố định.
Kích cỡ động.
Khởi tạo nhanh.
Khởi tạo chậm vì sử dụng quy trình băm.
Có thể lưu các phần từ giống nhau.
Không cho phép các phần tử giống nhau.
Được sắp xếp theo thứ tự.
Không có thứ tự.
