Chào mọi người, mình là Hàn và chủ đề mình sẽ chia sẻ hôm nay chính là Array (mảng) - một trong những cấu trúc dữ liệu cơ bản nhất trong lập trình.
Tại sao bạn nên đọc bài viết này? Mảng là gì, ai cũng biết cả rồi mà 🧐. Thật ra ban đầu chính mình cũng nghĩ vậy cho đến khi mình tham gia vào khóa Array 101 trên leetcode và sau đó thì "Quào !" có rất nhiều điều hay ho mà mình học được cũng như review lại mớ kiến thức căn bản mà mình đã bỏ quên.
Nội dung của khóa học trên bao gồm:
- Array là gì?
- Các đặc điểm cơ bản của Array
- Thao tác cơ bản với Array
- Một số giải thuật tương tác với Array
Và trong phạm vi của bài viết này, mình sẽ cố gắng tóm lượt lại nội dung và sử dụng cú pháp Java để demo một số phần. Dù bạn là người mới trong ngành hay là một lập trình viên đã có kinh nghiệm, mình tin rằng các kiến thức tới đây cũng sẽ giúp ích cho bạn. Ok, giờ thì ta cùng bắt đầu thôi!
BẮT ĐẦU VỚI ĐỊNH NGHĨA
Array (mảng) là một trong những cấu trúc dữ liệu cơ bản và sơ khai nhất trong khoa học máy tính, theo định nghĩa trên trang leetcode thì mảng là 1 tập hợp các phần tử được lưu dưới dạng những ô nhớ liền kề nhau. Thường thì mảng chỉ cho phép lưu những phần tử có cùng kiểu dữ liệu (data type) nhưng ở một số ngôn ngữ (dynamically typed languages) như PHP hay JavaScript thì mảng lại có thể lưu được nhiều kiểu dữ liệu (heterogenous array). Trong phạm vi của bài viết mình sẽ coi như mảng chỉ được phép chứa 1 kiểu dữ liệu nhé.
An Array is a collection of items. The items could be integers, strings, DVDs, games, books—anything really. The items are stored in neighboring (contiguous) memory locations. Because they're stored together, checking through the entire collection of items is straightforward.
Hãy hình dung bạn có một cái hộp đĩa DVDs chứa toàn bộ bộ sưu tập phim của bạn. Mỗi đĩa DVD sẽ được coi như một phần tử trong mảng và các đĩa DVD này nằm liền kề nhau. Tất nhiên vì đây là hộp đĩa DVD nên nó chỉ dùng để chứa DVDs chứ không phải nơi để bạn bỏ đồ ăn, quần áo vào (*trừ khi bạn bừa bộn🫥).
CÁC ĐẶC ĐIỂM CỦA 1 ARRAY
Ta cùng tiếp tục sử dụng ví dụ về hộp đĩa DVDs, phân tích các đặc điểm của nó và ráp nó vào array thử nhé. Trước tiên hãy suy nghĩ về nhu cầu của bạn, giả sử bạn đang cần một hộp đĩa có sức chứa (capacity) là 100 DVDs, và bạn cần phải tới cửa hàng để mua nó. Mảng cũng vậy, nó có một kích thược cố định và để sử dụng thì bạn phải khai báo nó:
DVD[] DVDBox = new DVD[100];
Sau khi đã sở hữu cho mình một hộp đĩa DVDs, bạn có thể tự do thêm đĩa vào bên trong chiếc hộp đó nhưng nên nhớ rằng sức chứa của hộp chỉ có 100 và nếu bạn có nhiều hơn thế, bạn buộc phải mua thêm chiếc hộp mới. Đến đây một số người có thể cho rằng sao không mua hẵn luôn hộp 500 DVDs luôn để khỏi lo hết chỗ. Điều này đối với máy tính sẽ gây tốn kém và lãng phí về mặt bộ nhớ, tương tự việc chiếc hộp 500 đĩa chắc chắn sẽ đắt tiền hơn và chiếm không gian trong phòng bạn.
Từ ví dụ trên, ta có thể suy ra một số đặc điểm của mảng:
- Kích thước cố định
- Các phần tư được lưu trữ trong các ô nhớ liền kề
- Chỉ lưu trữ được duy nhất 1 kiểu dữ liệu
- Rất tốn kém nếu muốn mở rộng
Lưu ý: chỉ nên sử dụng mảng khi nhu cầu về kích thước là cố định, nếu không hãy tham khảo 1 số kiểu dữ liệu khác như List, Set hoặc Map.
Thao tác cơ bản trên Array
Ok, sau khi nắm được các đặc điểm cơ bản hãy cùng đến với các thao tác mà bạn có thể thực hiện trên mảng và tiếp tục sử dụng ví dụ hộp đĩa DVDs ở trên.
Insert (thêm)
Để thêm 1 phần tử vào mảng bạn có thể sử dụng cú pháp sau:
DVDBox[position] = new DVD();
Đây là thao tác cơ bản nhất và bạn sẽ còn gặp ở các data structure khác, nó giống như việc bạn cho thêm đĩa vào hộp DVD của bạn. Tuy nhiên phụ thuộc vào vị trí mà bạn thêm, độ phức tạp sẽ khác nhau. Hãy hình dung cụ thể hơn về hộp đĩa DVDs, nó có 100 ngăn và mỗi ngăn chỉ chứa được 1 đĩa. Cách đơn giản nhất và ích tốn công nhất là thêm đĩa vào ngăn trống cuối cùng vì nó không cần thao tác gì thêm. Nhưng khi muốn thêm đĩa vào ngăn đầu tiên, bạn phải di chuyển toàn bộ số đĩa hiện có về phía sau, điều tương tự đối với việc thêm đĩa vào ngăn ở giữa. Tóm lại độ phức tạp của thao tác insert sẽ là:
- Insert cuối là O(1)
- Insert đầu là O(array.length)
- Insert giữa là O(n) với n là vị trí muốn insert
Việc thêm đĩa ngoài giới hạn của mảng là không thể như đã đề cập ở trên và sẽ gây ra lỗi "Index out of Range".
Delete (xóa)
Thao tác xóa cũng khá tương tự như thêm và có thể được thực hiện bằng các gán nó về null
DVDBox[position] = null;
Đôi khi bạn sẽ muốn bỏ đi một số đĩa có thể vì nó bị hư hoặc quá cũ hoặc khi bạn muốn thêm đĩa khác vào nhưng hết chỗ trống. Và cũng như thao tác insert, độ phức tạp cho các trường hợp sẽ là:
- Delete cuối là O(1)
- Delete đầu là O(array.length)
- Delete giữa là O(n) với n là vị trí muốn insert
Access (Truy cập)
Việc truy cập vào một phần tử trong mảng cũng tương tự như bạn lấy đĩa ra từ hộp đĩa của bạn. Giả sử bạn đang cần tìm đĩa phim "Finding Nemo" mà bạn đặt ở ngăn thứ 50 trong hộp đĩa, việc cần làm chỉ là tìm đến ngăn đó và lấy nó ra. Trong mảng ta sử dụng cú pháp:
DVD findingNemo = DVDBox[50];
Tất nhiên cũng sẽ có những lúc bạn quên mất đĩa phim mình cần tìm nằm ở ngăn nào, đó là lý do ta có thêm thao tác tìm kiếm (search) nằm ở bên dưới.
Search (tìm kiếm)
Sẽ rất khó để bạn có thể ghi nhớ toàn bộ vị trí đĩa DVDs và lấy chúng ra mỗi khi cần. Như bạn cần tìm đĩa phim Titanic và không nhớ được vị trí ngăn của nó, cách đơn giản nhất để tìm là lấy đĩa ra khỏi từng ngăn và xem nhãn trên đĩa (bắt đầu với ngăn đầu và kết thúc ở ngăn cuối) Trong mảng cũng vậy, bạn sẽ phải đi qua từng phần tử từ đầu đến cuối cho đến khi tìm được cái mình muốn - kỹ thuật này còn được gọi là Linear search. Trường hợp tốt nhất của Linear search là khi DVD bạn tìm nằm ở ngăn đầu tiên và tệ nhất là khi nó ở ngăn cuối cùng. Độ phức tạp của Linear search là O(n)
Một cách nhanh hơn để tìm kiếm là Binary search với độ phức tạp tương đương O(logn) nhưng chỉ có thể được sử dụng khi và chỉ khi mảng của bạn để được sắp xếp. Các thuật toán về tìm kiếm thì có rất nhiều nên mình sẽ không đi sâu và có thể mình sẽ chia sẻ về nó ở trong một chủ đề riêng trong tương lai.
Tổng kết
Như vậy, chúng ta đã review lại được kha khá kiến thức cơ bản về mảng. Nắm chắc được các kiến thức cơ bản sẽ luôn là một nền tảng tốt để bạn phát triển lâu dài.
Ở bài viết tiếp theo mình sẽ đi sâu vào các kỹ thuật thường được sử dụng trong cái bài thuật toán về mảng như: two-pointers, sliding-window, prefix-sum,... Xin cảm ơn và hẹn các bạn ở bài viết tiếp theo ^.^