Cấu trúc dữ liệu danh sách liên kết vòng

<p style="text-align: justify;">Danh s&aacute;ch li&ecirc;n kết v&ograve;ng&nbsp;l&agrave; một trong những kiểu cấu tr&uacute;c dữ liệu danh s&aacute;ch li&ecirc;n kết. Trong b&agrave;i viết n&agrave;y, ta sẽ c&ugrave;ng t&igrave;m hiểu về kiến thức n&agrave;y c&ugrave;ng c&aacute;c h&igrave;nh ảnh minh họa.</p> <h2 id="ftoc-heading-1" class="ftwp-heading" style="text-align: justify;">1. Thế n&agrave;o l&agrave; danh s&aacute;ch li&ecirc;n kết v&ograve;ng?</h2> <p style="text-align: justify;">Danh s&aacute;ch li&ecirc;n kết v&ograve;ng l&agrave; một dạng biến thể của danh s&aacute;ch li&ecirc;n kết, trong đ&oacute; phần tử đầu ti&ecirc;n trỏ đến phần tử cuối c&ugrave;ng v&agrave; phần tử cuối c&ugrave;ng trỏ đến phần tử đầu ti&ecirc;n. Cả danh s&aacute;ch li&ecirc;n kết đơn v&agrave; danh s&aacute;ch li&ecirc;n kết đ&ocirc;i đều c&oacute; thể được tạo th&agrave;nh một danh s&aacute;ch li&ecirc;n kết v&ograve;ng.</p> <p style="text-align: justify;">Danh s&aacute;ch li&ecirc;n kết đơn c&oacute; thể được tạo th&agrave;nh danh s&aacute;ch li&ecirc;n kết v&ograve;ng. Trong danh s&aacute;ch li&ecirc;n kết đơn, con trỏ tiếp theo của n&uacute;t cuối c&ugrave;ng sẽ trỏ đến n&uacute;t đầu ti&ecirc;n.</p> <p><img style="width: 100%;" src="../../../public_files/22caae76-4e58-4656-a147-293a2b4c88a7" alt="danh-sach-lien-ket-vong" /></p> <p style="text-align: justify;">Danh s&aacute;ch li&ecirc;n kết đ&ocirc;i cũng c&oacute; thể được tạo th&agrave;nh danh s&aacute;ch li&ecirc;n kết v&ograve;ng. Trong danh s&aacute;ch được li&ecirc;n kết đ&ocirc;i, con trỏ Next của n&uacute;t cuối c&ugrave;ng trỏ đến n&uacute;t đầu ti&ecirc;n v&agrave; con trỏ Prev của n&uacute;t đầu ti&ecirc;n trỏ đến n&uacute;t cuối c&ugrave;ng tạo th&agrave;nh v&ograve;ng tr&ograve;n theo cả hai hướng.</p> <p><img style="width: 100%;" src="../../../public_files/1612ec57-8869-425c-bee4-b1f14923e711" alt="danh-sach-lien-ket-vong-2" /></p> <h2 id="ftoc-heading-2" class="ftwp-heading">2. C&aacute;c thao t&aacute;c cơ bản của danh s&aacute;ch li&ecirc;n kết v&ograve;ng</h2> <p style="text-align: justify;">Sau đ&acirc;y l&agrave; c&aacute;c thao t&aacute;c được hỗ trợ bởi danh s&aacute;ch li&ecirc;n kết v&ograve;ng.</p> <h3 style="text-align: justify;"><strong> 2.1. Thao t&aacute;c ch&egrave;n n&uacute;t mới (Insert)</strong></h3> <p style="text-align: justify;">C&oacute; hai điều cần ch&uacute; &yacute; khi th&ecirc;m n&uacute;t cho danh s&aacute;ch li&ecirc;n kết v&ograve;ng:</p> <ol> <li style="text-align: justify;">Khi th&ecirc;m một phần tử v&agrave;o danh s&aacute;ch rỗng, ta sẽ đặt phần đầu của danh s&aacute;ch li&ecirc;n kết bằng n&uacute;t mới v&agrave; g&aacute;n con trỏ Next trỏ v&agrave;o ch&iacute;nh n&oacute;.</li> <li style="text-align: justify;">Khi th&ecirc;m một phần tử v&agrave;o danh s&aacute;ch li&ecirc;n kết với một hoặc nhiều n&uacute;t, ta cần phải t&igrave;m phần tử cuối c&ugrave;ng. Sau đ&oacute;, g&aacute;n con trỏ Next của n&uacute;t cuối c&ugrave;ng trỏ tới n&uacute;t mới v&agrave; con trỏ Next của n&uacute;t mới n&agrave;y trỏ tới n&uacute;t đầu ti&ecirc;n.</li> </ol> <p><img style="width: 100%;" src="../../../public_files/5d880d56-d100-4b80-93b7-1748b2d80862" alt="danh-sach-lien-ket-vong-3" /></p> <h3 style="text-align: justify;"><strong>2.2. Thao t&aacute;c x&oacute;a phần tử khỏi danh s&aacute;ch (Delete)</strong></h3> <p style="text-align: justify;">Khi x&oacute;a một phần tử, ta cần lưu &yacute; hai điều như sau:</p> <ol> <li style="text-align: justify;">Khi x&oacute;a một phần tử khỏi danh s&aacute;ch li&ecirc;n kết v&ograve;ng c&oacute; k&iacute;ch thước bằng một, ta sẽ g&aacute;n con trỏ đầu ti&ecirc;n với gi&aacute; trị NULL.</li> <li style="text-align: justify;">Khi x&oacute;a một phần tử khỏi danh s&aacute;ch c&oacute; hai phần tử trở l&ecirc;n, ta cần theo d&otilde;i hai con trỏ: con trỏ hiện tại v&agrave; con trỏ trước đ&oacute;. Ngay sau khi con trỏ hiện tại đến n&uacute;t cần x&oacute;a, ta sẽ g&aacute;n con trỏ Next của n&uacute;t trước đ&oacute; với con trỏ Next của của n&uacute;t hiện tại. Sau đ&oacute; thực hiện x&oacute;a n&uacute;t hiện tại.</li> </ol> <p><img style="width: 100%;" src="../../../public_files/9c170415-69c9-4096-9bdb-785e2cdda71e" alt="danh-sach-lien-ket-vong-4" /></p> <h3 style="text-align: justify;"><strong> 2.3. Thao t&aacute;c hiển thị danh s&aacute;ch (Display)</strong></h3> <p style="text-align: justify;">Hiển thị dữ liệu của danh s&aacute;ch li&ecirc;n kết v&ograve;ng tương tự như danh s&aacute;ch li&ecirc;n kết th&ocirc;ng thường, ta chỉ việc truy cập từng n&uacute;t v&agrave; in ra dữ liệu của từng n&uacute;t đ&oacute;.</p> <p style="text-align: justify;">Sự kh&aacute;c biệt duy nhất giữa hai danh s&aacute;ch l&agrave; ở phương ph&aacute;p kết th&uacute;c. Khi in dữ liệu của một danh s&aacute;ch li&ecirc;n kết th&ocirc;ng thường, đoạn m&atilde; sẽ bắt đầu hiển thị dữ liệu từ con trỏ đầu v&agrave; kết th&uacute;c ngay khi gặp gi&aacute; trị NULL. Trong khi đ&oacute;, trong danh s&aacute;ch li&ecirc;n kết tr&ograve;n, đoạn m&atilde; sẽ bắt đầu hiển thị dữ liệu từ con trỏ đầu ti&ecirc;n v&agrave; kết th&uacute;c ngay khi gặp lại con trỏ đầu ti&ecirc;n n&agrave;y.</p> <p><img style="width: 100%;" src="../../../public_files/3614be85-1769-47ad-94b7-70d1021be3e3" alt="danh-sach-lien-ket-vong-5" /></p> <h3 style="text-align: justify;"><strong> 2.4. Thao t&aacute;c cập nhật gi&aacute; trị lưu trữ trong c&aacute;c n&uacute;t của danh s&aacute;ch (Update)</strong></h3> <p style="text-align: justify;">Tương tự như với c&aacute;c danh s&aacute;ch li&ecirc;n kết th&ocirc;ng thường, ta chỉ việc duyệt qua từng n&uacute;t v&agrave; kiểm tra xem dữ liệu trong n&uacute;t đ&oacute; c&oacute; phải l&agrave; dữ liệu cần thay đổi hay kh&ocirc;ng. Nếu đ&uacute;ng th&igrave; dừng lại v&agrave; thay đổi, nếu kh&ocirc;ng th&igrave; tiếp tục duyệt.</p> <h2 id="ftoc-heading-3" class="ftwp-heading" style="text-align: justify;">3. Ứng dụng của danh s&aacute;ch li&ecirc;n kết v&ograve;ng</h2> <p style="text-align: justify;">M&aacute;y t&iacute;nh c&aacute; nh&acirc;n c&oacute; nhiều ứng dụng đang được thực thi. Tất cả c&aacute;c ứng dụng đang chạy được giữ trong một danh s&aacute;ch li&ecirc;n kết v&ograve;ng v&agrave; hệ điều h&agrave;nh cung cấp một khoảng thời gian cố định để tất cả c&aacute;c ứng dụng n&agrave;y c&ugrave;ng chạy. Hệ điều h&agrave;nh tiếp tục lặp lại danh s&aacute;ch li&ecirc;n kết cho đến khi ho&agrave;n th&agrave;nh tất cả c&aacute;c ứng dụng.</p> <p style="text-align: justify;">Một v&iacute; dụ kh&aacute;c l&agrave; tr&ograve; chơi với nhiều người chơi. Tất cả người chơi được lưu giữ trong danh s&aacute;ch li&ecirc;n kết v&ograve;ng v&agrave; con trỏ di chuyển về ph&iacute;a trước khi thời gian của người chơi kết th&uacute;c.</p> <p style="text-align: justify;">Danh s&aacute;ch li&ecirc;n kết v&ograve;ng cũng c&oacute; thể được sử dụng để tạo h&agrave;ng đợi v&ograve;ng tr&ograve;n. Trong một h&agrave;ng đợi, ch&uacute;ng ta phải lu&ocirc;n giữ hai con trỏ FRONT v&agrave; REAR (ta sẽ t&igrave;m hiểu về 2 con trỏ n&agrave;y trong c&aacute;c b&agrave;i sau) trong bộ nhớ, trong đ&oacute;, đối với danh s&aacute;ch li&ecirc;n kết v&ograve;ng, ta sẽ chỉ cần một con trỏ.</p> <p style="text-align: justify;">Tr&ecirc;n đ&acirc;y l&agrave; kh&aacute;i niệm v&agrave; v&iacute; dụ cơ bản về danh s&aacute;ch li&ecirc;n kết v&ograve;ng. Hy vọng mọi người c&oacute; thể &aacute;p dụng v&agrave;o trong chương tr&igrave;nh của m&igrave;nh. Nếu mọi người c&oacute; đ&oacute;ng g&oacute;p g&igrave; th&ecirc;m th&igrave; c&oacute; thể để c&aacute;c b&igrave;nh luận b&ecirc;n dưới b&agrave;i viết n&agrave;y. Mọi người h&atilde;y tiếp tục theo d&otilde;i c&aacute;c b&agrave;i tiếp theo v&agrave; cập nhật c&aacute;c b&agrave;i mới nhất tr&ecirc;n&nbsp;<a href="../../../">tek4</a>&nbsp;nh&eacute;!</p>