Ch&agrave;o mừng c&aacute;c bạn đến với kh&oacute;a học "Cấu tr&uacute;c dữ liệu v&agrave; Giải thuật" tại TEK4.VN!
Bạn đ&atilde; bao giờ tự hỏi rằng để trở th&agrave;nh một lập tr&igrave;nh vi&ecirc;n xuất sắc, bạn cần những kiến thức v&agrave; kỹ năng g&igrave;? Kh&oacute;a học n&agrave;y ch&iacute;nh l&agrave; ch&igrave;a kh&oacute;a để mở ra c&aacute;nh cửa của tri thức đ&oacute;. Với nội dung phong ph&uacute; v&agrave; chi tiết, kh&oacute;a học Cấu tr&uacute;c dữ liệu v&agrave; Giải thuật tại TEK4.VN hứa hẹn sẽ gi&uacute;p bạn x&acirc;y dựng nền tảng vững chắc v&agrave; th&agrave;nh thạo trong lập tr&igrave;nh.
Trong kh&oacute;a học n&agrave;y, ch&uacute;ng ta sẽ tập trung v&agrave;o việc kh&aacute;m ph&aacute; v&agrave; hiểu r&otilde; c&aacute;c cấu tr&uacute;c dữ liệu quan trọng như mảng, chuỗi k&yacute; tự, danh s&aacute;ch li&ecirc;n kết, ngăn xếp, h&agrave;ng đợi, bảng băm, tập hợp, c&acirc;y, đồ thị v&agrave; heap. C&aacute;c cấu tr&uacute;c dữ liệu n&agrave;y l&agrave; nền tảng của lập tr&igrave;nh, gi&uacute;p ch&uacute;ng ta giải quyết c&aacute;c vấn đề phức tạp một c&aacute;ch hiệu quả.
Kh&oacute;a học cũng sẽ gi&uacute;p bạn hiểu r&otilde; c&aacute;c thuật to&aacute;n cơ bản v&agrave; n&acirc;ng cao, bao gồm thuật to&aacute;n sắp xếp, thuật to&aacute;n t&igrave;m kiếm, thuật to&aacute;n t&igrave;m kiếm nhị ph&acirc;n, thuật to&aacute;n t&igrave;m kiếm chuỗi k&yacute; tự, giải thuật tham lam, thuật to&aacute;n quay lui v&agrave; quy hoạch động. Bạn sẽ học c&aacute;ch &aacute;p dụng c&aacute;c thuật to&aacute;n n&agrave;y v&agrave;o c&aacute;c vấn đề thực tế, gi&uacute;p tăng cường kỹ năng giải quyết vấn đề của m&igrave;nh.
Ngo&agrave;i ra, ch&uacute;ng m&igrave;nh sẽ chia sẻ một số kinh nghiệm cần thiết cho buổi phỏng vấn, gi&uacute;p bạn chuẩn bị tốt nhất cho c&aacute;c cơ hội nghề nghiệp li&ecirc;n quan đến lập tr&igrave;nh trong tương lai. Bạn sẽ được học c&aacute;ch hiểu r&otilde; y&ecirc;u cầu của người phỏng vấn, thể hiện kỹ năng lập tr&igrave;nh của m&igrave;nh một c&aacute;ch hiệu quả v&agrave; trả lời c&aacute;c c&acirc;u hỏi một c&aacute;ch tr&ocirc;i chảy. Ch&uacute;ng m&igrave;nh tự tin rằng, sau khi bạn ho&agrave;n th&agrave;nh kh&oacute;a học n&agrave;y, bạn sẽ trở n&ecirc;n nhạy b&eacute;n trong tư duy lập tr&igrave;nh hiệu quả.
H&atilde;y tham gia kh&oacute;a học n&agrave;y để t&igrave;m hiểu s&acirc;u hơn về lập tr&igrave;nh v&agrave; mở rộng kỹ năng của bạn. TEK4.VN rất mong được hỗ trợ bạn trong qu&aacute; tr&igrave;nh học tập n&agrave;y.

Cấu trúc dữ liệu và Giải thuật

Đến đ&acirc;y, hẳn l&agrave; bạn đ&atilde; kh&aacute; th&agrave;nh thạo về hai kiểu cấu tr&uacute;c dữ liệu phổ biến l&agrave; mảng v&agrave; danh s&aacute;ch li&ecirc;n kết. Vậy th&igrave; khi n&agrave;o ta n&ecirc;n sử dụng loại cấu tr&uacute;c dữ liệu n&agrave;o? Sự kh&aacute;c biệt giữa ch&uacute;ng ra sao? Tại sao ta kh&ocirc;ng sử dụng một loại th&ocirc;i? Tất cả c&aacute;c c&acirc;u trả lời cho c&aacute;c vấn đề tr&ecirc;n sẽ được giải đ&aacute;p trong b&agrave;i học n&agrave;y.
<h2 style="text-align: justify;">1. Nhắc lại về mảng</h2>
Cấu tr&uacute;c dữ liệu mảng c&oacute; c&aacute;c đặc điểm sau:
<ul style="text-align: justify;">
<li>Truy cập ngẫu nhi&ecirc;n (Thời gian t&igrave;m kiếm nhanh).</li>
<li>Bộ nhớ cần cấp cho một phần tử &iacute;t hơn.</li>
<li>Thời gian x&oacute;a v&agrave; th&ecirc;m phần tử chậm hơn.</li>
<li>K&iacute;ch thước cố định.</li>
<li>Sử dụng bộ nhớ kh&ocirc;ng hiệu quả.</li>
<li>C&aacute;c phần tử nằm tr&ecirc;n một v&ugrave;ng bộ nhớ bao gồm c&aacute;c &ocirc; chứa dữ liệu liền nhau.</li>
</ul>
Khi một mảng được tạo, n&oacute; cần một dung lượng bộ nhớ nhất định. Nếu ta c&oacute; 7 chữ c&aacute;i cần được lưu trữ trong một mảng, ta sẽ cần 7 byte bộ nhớ để biểu diễn mảng đ&oacute;. Tuy nhi&ecirc;n, ta cần tất cả bộ nhớ đ&oacute; với c&aacute;c &ocirc; bộ nhớ liền kề nhau. Tức l&agrave;, m&aacute;y t&iacute;nh của ta sẽ cần định vị 7 byte bộ nhớ rỗng, một byte b&ecirc;n cạnh byte kh&aacute;c, tất cả nằm c&ugrave;ng một ph&acirc;n v&ugrave;ng bộ nhớ.
<h2 style="text-align: justify;"> 2. Danh s&aacute;ch li&ecirc;n kết</h2>
Danh s&aacute;ch li&ecirc;n kết c&oacute; c&aacute;c đặc điểm sau:
<ul style="text-align: justify;">
<li>Thời gian th&ecirc;m v&agrave; x&oacute;a phần tử nhanh hơn.</li>
<li>K&iacute;ch thước động.</li>
<li>Sử dụng hiệu quả bộ nhớ.</li>
<li>Thời gian t&igrave;m kiếm chậm hơn so với mảng.</li>
<li>Tốn nhiều bộ nhớ hơn cho một phần tử. C&aacute;c phần tử trong danh s&aacute;ch li&ecirc;n kết nằm tr&ecirc;n c&aacute;c ph&acirc;n v&ugrave;ng bộ nhớ kh&aacute;c nhau, do đ&oacute;, c&aacute;c phần tử trong danh s&aacute;ch li&ecirc;n kết cần chứa một con trỏ để trỏ tới c&aacute;c phần tử đằng sau n&oacute;.</li>
</ul>
Khi một danh s&aacute;ch li&ecirc;n kết được sinh ra, n&oacute; kh&ocirc;ng cần 7 byte bộ nhớ tất cả nằm ở c&ugrave;ng một ph&acirc;n v&ugrave;ng. Một byte c&oacute; thể tồn tại ở một ph&acirc;n v&ugrave;ng n&agrave;o đ&oacute;, trong khi byte tiếp theo c&oacute; thể được lưu trữ ở một ph&acirc;n v&ugrave;ng kh&aacute;c trong bộ nhớ. Danh s&aacute;ch li&ecirc;n kết kh&ocirc;ng cần chiếm một khối bộ nhớ, thay v&agrave;o đ&oacute;, bộ nhớ m&agrave; ch&uacute;ng sử dụng c&oacute; thể nằm rải r&aacute;c ở c&aacute;c ph&acirc;n v&ugrave;ng kh&aacute;c nhau.
<h2 style="text-align: justify;">3. Bảng so s&aacute;nh giữa danh s&aacute;ch li&ecirc;n kết v&agrave; mảng</h2>
Bảng b&ecirc;n dưới đ&acirc;y sẽ thực hiện so s&aacute;nh c&aacute;c đặc điểm giữa danh s&aacute;ch li&ecirc;n kết v&agrave; mảng:
<table style="border-collapse: collapse; width: 100%;" border="1">
<tbody>
<tr>
<td style="width: 48.8436%; text-align: center;">Mảng</td>
<td style="width: 48.8436%; text-align: center;">Danh s&aacute;ch li&ecirc;n kết</td>
</tr>
<tr>
<td style="width: 48.8436%;">Dữ liệu chỉ c&oacute; thể được lưu trữ trong c&aacute;c khối bộ nhớ liền nhau, n&ecirc;n k&iacute;ch thước của n&oacute; kh&ocirc;ng thể thay đổi trong thời gian thực thi.</td>
<td style="width: 48.8436%;">Mỗi n&uacute;t trỏ đến n&uacute;t tiếp theo để dữ liệu c&oacute; thể tồn tại ở c&aacute;c địa chỉ kh&ocirc;ng liền kề nhau, cho ph&eacute;p k&iacute;ch thước c&oacute; thể thay đổi trong thời gian thực thi.</td>
</tr>
<tr>
<td style="width: 48.8436%;">Việc x&aacute;o trộn một mảng sẽ phức tạp hơn v&agrave; chiếm nhiều bộ nhớ hơn.</td>
<td style="width: 48.8436%;">Việc x&aacute;o trộn danh s&aacute;ch li&ecirc;n kết chỉ l&agrave; vấn đề thay đổi c&aacute;c n&uacute;t trong danh s&aacute;ch, do đ&oacute; sẽ dễ d&agrave;ng hơn.</td>
</tr>
<tr>
<td style="width: 48.8436%;">Mảng cho ph&eacute;p việc truy cập c&aacute;c phần tử một c&aacute;ch ngẫu nhi&ecirc;n bằng c&aacute;ch sử dụng chỉ số.</td>
<td style="width: 48.8436%;">Danh s&aacute;ch li&ecirc;n kết chỉ cho ph&eacute;p truy cập c&aacute;c phần tử theo thứ tự từ đầu đến cuối.</td>
</tr>
<tr>
<td style="width: 48.8436%;">K&iacute;ch thước của một mảng được biết trước hoặc được tạo lại khi n&oacute; cần ph&aacute;t triển lớn hơn. Bởi v&igrave; kh&ocirc;ng gian bộ nhớ được ph&acirc;n bổ cho mảng trong thời gian bi&ecirc;n dịch, tức l&agrave; k&iacute;ch thước của n&oacute; được cố định khi ta khai b&aacute;o n&oacute;.</td>
<td style="width: 48.8436%;">Danh s&aacute;ch li&ecirc;n kết ph&aacute;t triển một c&aacute;ch tự nhi&ecirc;n, theo thứ tự được th&ecirc;m dữ liệu. Kh&ocirc;ng gian bộ nhớ được ph&acirc;n bổ cho danh s&aacute;ch li&ecirc;n kết trong thời gian thực thi, tức l&agrave; k&iacute;ch thước của n&oacute; c&oacute; thể tăng hoặc giảm trong khi chương tr&igrave;nh đang thực thi.</td>
</tr>
<tr>
<td style="width: 48.8436%;">Một mảng sẽ giả định rằng mọi phần tử đều c&oacute; c&ugrave;ng k&iacute;ch thước v&igrave; c&aacute;c phần tử của mảng phải c&oacute; c&ugrave;ng kiểu dữ liệu.&nbsp;</td>
<td style="width: 48.8436%;">Dễ d&agrave;ng lưu trữ dữ liệu c&oacute; k&iacute;ch thước kh&aacute;c nhau trong danh s&aacute;ch li&ecirc;n kết.</td>
</tr>
<tr>
<td style="width: 48.8436%;">Mảng c&oacute; kiểu mảng một chiều, mảng hai chiều hoặc mảng đa chiều.</td>
<td style="width: 48.8436%;">Danh s&aacute;ch li&ecirc;n kết c&oacute; kiểu danh s&aacute;ch li&ecirc;n kết đơn, đ&ocirc;i hoặc v&ograve;ng.</td>
</tr>
</tbody>
</table>
Như vậy, sự kh&aacute;c biệt cơ bản giữa mảng v&agrave; danh s&aacute;ch li&ecirc;n kết l&agrave; mảng l&agrave; cấu tr&uacute;c dữ liệu tĩnh, trong khi danh s&aacute;ch li&ecirc;n kết l&agrave; cấu tr&uacute;c dữ liệu động. Cấu tr&uacute;c dữ liệu tĩnh cần tất cả t&agrave;i nguy&ecirc;n được cấp ph&aacute;t khi cấu tr&uacute;c dữ liệu đ&oacute; được tạo. Điều n&agrave;y c&oacute; nghĩa l&agrave; ngay cả khi cấu tr&uacute;c được tăng hoặc thu nhỏ về mặt k&iacute;ch thước v&agrave; c&aacute;c phần tử được th&ecirc;m v&agrave;o hoặc được x&oacute;a bỏ, n&oacute; vẫn lu&ocirc;n cần một k&iacute;ch thước v&agrave; dung lượng bộ nhớ nhất định. Nếu cần th&ecirc;m nhiều phần tử v&agrave;o cấu tr&uacute;c dữ liệu tĩnh v&agrave; n&oacute; kh&ocirc;ng c&oacute; đủ bộ nhớ, bạn cần sao ch&eacute;p dữ liệu của mảng đ&oacute; v&agrave; tạo mảng kh&aacute;c với nhiều bộ nhớ hơn để c&oacute; thể th&ecirc;m c&aacute;c phần tử v&agrave;o đ&oacute;. Mặt kh&aacute;c, cấu tr&uacute;c dữ liệu động c&oacute; thể thu nhỏ v&agrave; gia tăng về mặt k&iacute;ch thước trong bộ nhớ. N&oacute; kh&ocirc;ng cần ph&acirc;n bổ một lượng bộ nhớ nhất định để lưu trữ, k&iacute;ch thước c&oacute; thể thay đổi, đồng thời dung lượng bộ nhớ cần cũng c&oacute; thể thay đổi.
<h2 dir="ltr" style="text-align: justify;">Ưu v&agrave; nhược điểm của danh s&aacute;ch li&ecirc;n kết so với mảng</h2>
C&ocirc;ng bằng m&agrave; n&oacute;i, sự kh&aacute;c biệt giữa danh s&aacute;ch li&ecirc;n kết v&agrave; mảng thực sự kh&ocirc;ng ảnh hưởng nhiều đến việc sử dụng thuật to&aacute;n trong c&aacute;c b&agrave;i tập. Nguy&ecirc;n nh&acirc;n l&agrave; do đa số c&aacute;c b&agrave;i to&aacute;n li&ecirc;n quan đến danh s&aacute;ch li&ecirc;n kết sẽ c&oacute; dữ liệu đầu v&agrave;o dạng danh s&aacute;ch, do đ&oacute;, bạn chắc chắn sẽ sử dụng danh s&aacute;ch li&ecirc;n kết. Tuy nhi&ecirc;n, tr&ecirc;n thực tế cũng c&oacute; một số b&agrave;i to&aacute;n sử dụng danh s&aacute;ch li&ecirc;n kết như một phần của thuật to&aacute;n tối ưu v&agrave; bạn c&oacute; thể được hỏi những chi tiết li&ecirc;n quan trong c&aacute;c cuộc phỏng vấn chuy&ecirc;n m&ocirc;n, v&igrave; vậy bạn vẫn n&ecirc;n nắm r&otilde; c&aacute;c ưu v&agrave; nhược điểm của mỗi loại.
Ưu điểm ch&iacute;nh của danh s&aacute;ch li&ecirc;n kết l&agrave; bạn c&oacute; thể th&ecirc;m bớt phần tử ở bất kỳ vị tr&iacute; n&agrave;o với độ phức tạp&nbsp;$O(1)$. Một lưu &yacute; l&agrave; bạn cần phải c&oacute; một tham chiếu đến n&uacute;t ở vị tr&iacute; m&agrave; bạn muốn th&ecirc;m/x&oacute;a, nếu kh&ocirc;ng th&igrave; thao t&aacute;c sẽ tốn&nbsp;$O(n)$. Tuy nhi&ecirc;n, điều n&agrave;y vẫn tốt hơn nhiều so với mảng (động) th&ocirc;ng thường, y&ecirc;u cầu thời gian&nbsp;$O(n)$&nbsp;để th&ecirc;m v&agrave; x&oacute;a từ một vị tr&iacute;&nbsp;t&ugrave;y &yacute;.
Nhược điểm ch&iacute;nh của danh s&aacute;ch li&ecirc;n kết l&agrave; khả năng truy cập v&agrave;o phần tử ngẫu nhi&ecirc;n bị hạn chế. Nếu bạn c&oacute; một danh s&aacute;ch li&ecirc;n kết lớn với rất nhiều phần tử v&agrave; bạn muốn truy cập phần tử thứ $150000$ th&igrave; c&aacute;ch tốt nhất thường l&agrave; bắt đầu từ n&uacute;t head v&agrave; sử dụng v&ograve;ng lặp lặp lại $150000$ lần để đi được đến vị tr&iacute; cần truy cập. V&igrave; vậy, trong khi việc truy cập phần tử tại vị tr&iacute; bất kỳ trong mảng chỉ c&oacute; độ phức tạp $O(1)$&nbsp;th&igrave; thao t&aacute;c tương tự trong danh s&aacute;ch li&ecirc;n kết c&oacute; độ phức tạp l&ecirc;n tới&nbsp;$O(n)$.
Một số lưu &yacute; kh&aacute;c &iacute;t li&ecirc;n quan đến c&aacute;c b&agrave;i to&aacute;n về thuật to&aacute;n hoặc lập tr&igrave;nh thi đấu nhưng c&oacute; thể xuất hiện trong c&aacute;c buổi phỏng vấn chuy&ecirc;n m&ocirc;n đ&oacute; l&agrave;: danh s&aacute;ch li&ecirc;n kết c&oacute; lợi thế l&agrave; kh&ocirc;ng c&oacute; k&iacute;ch thước cố định. Mặc d&ugrave; mảng động c&oacute; thể thay đổi k&iacute;ch thước nhưng ch&uacute;ng vẫn ngầm được ph&acirc;n bổ k&iacute;ch thước cố định - chỉ l&agrave; khi vượt qu&aacute; k&iacute;ch thước n&agrave;y, mảng sẽ được thay đổi k&iacute;ch thước (c&ograve;n nếu kh&ocirc;ng chương tr&igrave;nh sẽ vẫn b&aacute;o lỗi), điều n&agrave;y rất tốn k&eacute;m. Danh s&aacute;ch li&ecirc;n kết kh&ocirc;ng bị như vậy. Tuy nhi&ecirc;n, danh s&aacute;ch li&ecirc;n kết tốn nhiều chi ph&iacute; thao t&aacute;c hơn so với mảng - mọi phần tử cần c&oacute; th&ecirc;m dung lượng lưu trữ cho con trỏ. Nếu bạn chỉ lưu trữ c&aacute;c mục nhỏ như booleans hoặc k&yacute; tự th&igrave; chi ph&iacute; lưu trữ c&oacute; thể tăng gấp đ&ocirc;i cần thiết.

Sự khác biệt giữa danh sách liên kết đơn và mảng