{"id":1234,"date":"2025-10-09T02:41:28","date_gmt":"2025-10-09T02:41:28","guid":{"rendered":"https:\/\/seateklab.vn\/?p=1234"},"modified":"2025-10-09T02:41:28","modified_gmt":"2025-10-09T02:41:28","slug":"algorithms-02-link-list","status":"publish","type":"post","link":"https:\/\/seateklab.vn\/en\/2025\/10\/09\/algorithms-02-link-list\/","title":{"rendered":"Algorithms 02 \u2013 Link list\u00a0"},"content":{"rendered":"\n

Linked List<\/strong> (Danh s\u00e1ch li\u00ean k\u1ebft) l\u00e0 m\u1ed9t trong nh\u1eefng c\u1ea5u tr\u00fac d\u1eef li\u1ec7u n\u1ec1n t\u1ea3ng trong l\u1eadp tr\u00ecnh. N\u00f3 \u0111\u01b0\u1ee3c h\u00ecnh th\u00e0nh t\u1eeb m\u1ed9t chu\u1ed7i c\u00e1c n\u00fat (nodes)<\/strong>, trong \u0111\u00f3 m\u1ed7i node l\u01b0u gi\u00e1 tr\u1ecb (value<\/code>) v\u00e0 m\u1ed9t con tr\u1ecf (pointer<\/code>) tr\u1ecf \u0111\u1ebfn node ti\u1ebfp theo trong danh s\u00e1ch. C\u1ea5u tr\u00fac n\u00e0y \u0111\u1eb7c bi\u1ec7t h\u1eefu \u00edch khi l\u00e0m vi\u1ec7c v\u1edbi d\u1eef li\u1ec7u \u0111\u1ed9ng ho\u1eb7c c\u00e1c thao t\u00e1c ch\u00e8n, xo\u00e1 ph\u1ea7n t\u1eed th\u01b0\u1eddng xuy\u00ean.<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

L\u01b0u \u00fd:<\/strong> B\u00e0i vi\u1ebft n\u00e0y d\u00e0nh cho ng\u01b0\u1eddi m\u1edbi b\u1eaft \u0111\u1ea7u. T\u00e1c gi\u1ea3 chia s\u1ebb l\u1ea1i qu\u00e1 tr\u00ecnh t\u1ef1 h\u1ecdc, v\u1edbi mong mu\u1ed1n truy\u1ec1n c\u1ea3m h\u1ee9ng v\u00e0 c\u1ee7ng c\u1ed1 ki\u1ebfn th\u1ee9c cho c\u1ed9ng \u0111\u1ed3ng. N\u1ebfu b\u1ea1n \u0111\u00e3 c\u00f3 kinh nghi\u1ec7m, h\u00e3y ti\u1ebfp t\u1ee5c luy\u1ec7n \u1edf c\u1ea5p \u0111\u1ed9 cao h\u01a1n ho\u1eb7c th\u1eed vi\u1ebft l\u1ea1i, gi\u1ea3ng gi\u1ea3i l\u1ea1i \u2013 v\u00ec \u0111\u00f3 l\u00e0 c\u00e1ch hi\u1ec7u qu\u1ea3 nh\u1ea5t \u0111\u1ec3 ghi nh\u1edb v\u00e0 r\u00e8n luy\u1ec7n t\u01b0 duy thu\u1eadt to\u00e1n.<\/p>\n\n\n\n

1. Hi\u1ec3u Linked List qua v\u00ed d\u1ee5 tr\u1ef1c quan<\/h2>\n\n\n\n

H\u00e3y t\u01b0\u1edfng t\u01b0\u1ee3ng Linked List<\/strong> gi\u1ed1ng nh\u01b0 chu\u1ed7i ticket<\/em> tr\u00ean Jira<\/strong> ho\u1eb7c Trello<\/strong> \u2013 m\u1ed7i ticket c\u00f3 li\u00ean k\u1ebft \u201cNext<\/code>\u201d d\u1eabn \u0111\u1ebfn ticket k\u1ebf ti\u1ebfp.<\/p>\n\n\n\n

Trong th\u1ef1c t\u1ebf, b\u1ea1n b\u1eaft g\u1eb7p Linked List \u1edf r\u1ea5t nhi\u1ec1u n\u01a1i:<\/p>\n\n\n\n

    \n
  • Ch\u1ee9c n\u0103ng\u00a0Undo\/Redo<\/strong>\u00a0trong Excel ho\u1eb7c VS Code ch\u00ednh l\u00e0 v\u00ed d\u1ee5 \u0111i\u1ec3n h\u00ecnh c\u1ee7a\u00a0Doubly Linked List<\/strong>:\n
      \n
    • Ctrl + Z<\/strong>\u00a0\u2192 \u0111i l\u00f9i (prev)<\/li>\n\n\n\n
    • Ctrl + Y<\/strong>\u00a0\u2192 \u0111i t\u1edbi (next)<\/li>\n<\/ul>\n<\/li>\n\n\n\n
    • Tr\u00ecnh duy\u1ec7t web khi b\u1ea1n nh\u1ea5n\u00a0Back<\/strong>\u00a0ho\u1eb7c\u00a0Forward<\/strong>\u00a0\u2014 ch\u00ednh l\u00e0 b\u1ea1n \u0111ang di chuy\u1ec3n trong m\u1ed9t\u00a0Linked List hai chi\u1ec1u<\/strong>\u00a0bi\u1ec3u di\u1ec5n l\u1ecbch s\u1eed truy c\u1eadp.<\/li>\n<\/ul>\n\n\n\n

      2. C\u00e1c lo\u1ea1i Linked List ph\u1ed5 bi\u1ebfn<\/h2>\n\n\n\n

      Singly Linked List<\/h3>\n\n\n\n

      M\u1ed7i node ch\u1ec9 c\u00f3 m\u1ed9t con tr\u1ecf next<\/code> tr\u1ecf \u0111\u1ebfn node ti\u1ebfp theo.<\/p>\n\n\n\n

        \n
      • Duy\u1ec7t \u0111\u01b0\u1ee3c t\u1eeb\u00a0head \u2192 tail<\/code>\u00a0nh\u01b0ng kh\u00f4ng th\u1ec3 quay l\u1ea1i.<\/li>\n\n\n\n
      • \u01afu \u0111i\u1ec3m: \u0111\u01a1n gi\u1ea3n, ti\u1ebft ki\u1ec7m b\u1ed9 nh\u1edb, thao t\u00e1c ch\u00e8n ho\u1eb7c xo\u00e1 \u1edf \u0111\u1ea7u danh s\u00e1ch nhanh (O(1)).<\/li>\n\n\n\n
      • Nh\u01b0\u1ee3c \u0111i\u1ec3m: kh\u00f4ng th\u1ec3 truy c\u1eadp ng\u01b0\u1ee3c; mu\u1ed1n t\u00ecm node tr\u01b0\u1edbc ph\u1ea3i duy\u1ec7t t\u1eeb \u0111\u1ea7u.<\/li>\n\n\n\n
      • B\u00e0i t\u1eadp ti\u00eau bi\u1ec3u:\u00a0LeetCode 206 \u2013 Reverse Linked List<\/strong>.<\/li>\n<\/ul>\n\n\n\n

        Doubly Linked List<\/h3>\n\n\n\n

        M\u1ed7i node c\u00f3 c\u1ea3 hai con tr\u1ecf prev<\/code> v\u00e0 next<\/code>, cho ph\u00e9p duy\u1ec7t hai chi\u1ec1u.<\/p>\n\n\n\n

          \n
        • Duy\u1ec7t \u0111\u01b0\u1ee3c theo c\u1ea3 hai h\u01b0\u1edbng.<\/li>\n\n\n\n
        • Ch\u00e8n\/Xo\u00e1 \u1edf gi\u1eefa thu\u1eadn ti\u1ec7n h\u01a1n Singly List.<\/li>\n\n\n\n
        • T\u1ed1n th\u00eam b\u1ed9 nh\u1edb \u0111\u1ec3 l\u01b0u\u00a0prev<\/code>.<\/li>\n\n\n\n
        • C\u1ea7n c\u1ea9n tr\u1ecdng khi c\u1eadp nh\u1eadt con tr\u1ecf \u0111\u1ec3 tr\u00e1nh l\u1ed7i tr\u1ecf sai.<\/li>\n<\/ul>\n\n\n\n

          Circular Linked List<\/h3>\n\n\n\n

          Node cu\u1ed1i c\u00f9ng (tail<\/code>) tr\u1ecf ng\u01b0\u1ee3c l\u1ea1i node \u0111\u1ea7u (head<\/code>), t\u1ea1o th\u00e0nh v\u00f2ng kh\u00e9p k\u00edn.<\/p>\n\n\n\n

            \n
          • Duy\u1ec7t t\u1eeb b\u1ea5t k\u1ef3 node n\u00e0o c\u0169ng c\u00f3 th\u1ec3 \u0111i qua to\u00e0n b\u1ed9 danh s\u00e1ch.<\/li>\n\n\n\n
          • \u1ee8ng d\u1ee5ng trong\u00a0round-robin scheduling<\/strong>\u00a0ho\u1eb7c c\u00e1c h\u1ec7 th\u1ed1ng c\u1ea7n v\u00f2ng l\u1eb7p li\u00ean t\u1ee5c.<\/li>\n\n\n\n
          • C\u1ea7n x\u00e1c \u0111\u1ecbnh \u0111i\u1ec1u ki\u1ec7n d\u1eebng r\u00f5 r\u00e0ng \u0111\u1ec3 tr\u00e1nh v\u00f2ng l\u1eb7p v\u00f4 h\u1ea1n.<\/li>\n<\/ul>\n\n\n\n

            3. So s\u00e1nh Linked List v\u00e0 Array<\/h2>\n\n\n\n
            Ti\u00eau ch\u00ed<\/th>Array<\/th>Linked List<\/th><\/tr>
            Truy c\u1eadp theo index<\/td>O(1)<\/td>O(n)<\/td><\/tr>
            Ch\u00e8n\/Xo\u00e1 ph\u1ea7n t\u1eed<\/td>O(n)<\/td>O(1) (n\u1ebfu c\u00f3 pointer)<\/td><\/tr>
            B\u1ed9 nh\u1edb<\/td>C\u1ea5p ph\u00e1t c\u1ed1 \u0111\u1ecbnh<\/td>\u0110\u1ed9ng, linh ho\u1ea1t h\u01a1n<\/td><\/tr>
            \u1ee8ng d\u1ee5ng<\/td>DB Index, Static Array<\/td>Undo\/Redo, Cache, LRU Cache<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

            4. C\u00e1c b\u00e0i t\u1eadp LeetCode n\u1ed5i b\u1eadt<\/h2>\n\n\n\n
              \n
            • 206. Reverse Linked List<\/strong>\u00a0\u2192 \u0110\u1ea3o chi\u1ec1u con tr\u1ecf, d\u00f9ng ba bi\u1ebfn\u00a0prev<\/code>,\u00a0curr<\/code>,\u00a0next<\/code>.<\/li>\n\n\n\n
            • 141. Linked List Cycle<\/strong>\u00a0\u2192 Ph\u00e1t hi\u1ec7n v\u00f2ng l\u1eb7p b\u1eb1ng hai con tr\u1ecf nhanh\u2013ch\u1eadm (fast\u2013slow pointers<\/code>).<\/li>\n\n\n\n
            • 21. Merge Two Sorted Lists<\/strong>\u00a0\u2192 G\u1ed9p hai danh s\u00e1ch \u0111\u00e3 s\u1eafp x\u1ebfp, c\u1ea9n th\u1eadn tr\u1ecf \u0111\u00fang pointer.<\/li>\n\n\n\n
            • 146. LRU Cache<\/strong>\u00a0\u2192 K\u1ebft h\u1ee3p HashMap (O(1) lookup) v\u00e0 Doubly Linked List (O(1) reorder, delete).<\/li>\n<\/ul>\n\n\n\n

              5. V\u00ed d\u1ee5 code Python c\u01a1 b\u1ea3n<\/h2>\n\n\n\n
              class Node:\n    def __init__(self, val):\n        self.val = val\n        self.next = None\n\nclass LinkedList:\n    def __init__(self):\n        self.head = None\n\n    def insert_head(self, val):\n        node = Node(val)\n        node.next = self.head\n        self.head = node\n\n    def insert_end(self, val):\n        node = Node(val)\n        if not self.head:\n            self.head = node\n            return\n        curr = self.head\n        while curr.next:\n            curr = curr.next\n        curr.next = node\n\n    def print_list(self):\n        curr = self.head\n        while curr:\n            print(curr.val, end=\" -> \")\n            curr = curr.next\n        print(\"None\")\n<\/code><\/pre>\n\n\n\n
              6. C\u00e1ch h\u1ecdc v\u00e0 luy\u1ec7n t\u1eadp hi\u1ec7u qu\u1ea3<\/h2>\n\n\n\n
              Tr\u01b0\u1edbc khi code, h\u00e3y v\u1ebd s\u01a1 \u0111\u1ed3 Linked List tr\u00ean gi\u1ea5y<\/strong>. H\u1ea7u h\u1ebft l\u1ed7i sai khi thao t\u00e1c v\u1edbi Linked List \u0111\u1ebfn t\u1eeb vi\u1ec7c tr\u1ecf nh\u1ea7m con tr\u1ecf (pointer<\/code>), v\u00ec v\u1eady h\u00e3y ch\u1eafc ch\u1eafn hi\u1ec3u h\u01b0\u1edbng \u0111i c\u1ee7a next<\/code> v\u00e0 prev<\/code> tr\u01b0\u1edbc khi ch\u1ea1y code.<\/p>\n\n\n\n
                \n
              • T\u1eadp trung v\u00e0o 4 nh\u00f3m b\u00e0i: reverse list, detect cycle, merge lists, remove node, v\u00e0 LRU cache.<\/li>\n\n\n\n
              • Trong ph\u1ecfng v\u1ea5n backend\/frontend, b\u1ea1n th\u01b0\u1eddng \u0111\u01b0\u1ee3c h\u1ecfi v\u1ec1 trade-off gi\u1eefa Array v\u00e0 Linked List.<\/li>\n\n\n\n
              • Chu\u1ea9n b\u1ecb s\u1eb5n template\u00a0Node<\/code>\u00a0v\u00e0\u00a0LinkedList<\/code>\u00a0\u0111\u1ec3 code nhanh h\u01a1n.<\/li>\n\n\n\n
              • Lu\u00f4n t\u00ednh tr\u01b0\u1edbc time\/space complexity \u0111\u1ec3 t\u1ed1i \u01b0u gi\u1ea3i ph\u00e1p.<\/li>\n<\/ul>\n\n\n\n
                7. T\u01b0 duy r\u00e8n luy\u1ec7n quan tr\u1ecdng<\/h2>\n\n\n\n
                Khi luy\u1ec7n Linked List, h\u00e3y b\u1eaft \u0111\u1ea7u b\u1eb1ng danh s\u00e1ch ng\u1eafn: [1 \u2192 2 \u2192 3 \u2192 None]<\/code> ho\u1eb7c [10 \u2192 20 \u2192 30 \u2192 40 \u2192 None]<\/code>.<\/p>\n\n\n\n
                V\u1edbi list ng\u1eafn, b\u1ea1n d\u1ec5 quan s\u00e1t thay \u0111\u1ed5i sau t\u1eebng thao t\u00e1c insert, delete, reverse<\/em>. N\u1ebfu g\u1eb7p l\u1ed7i tr\u1ecf sai, vi\u1ec7c in list nh\u1ecf gi\u00fap ph\u00e1t hi\u1ec7n nhanh. Khi logic \u0111\u00e3 v\u1eefng, h\u00e3y th\u1eed v\u1edbi test case l\u1edbn h\u01a1n.<\/p>\n\n\n\n
                Ngo\u00e0i ra, h\u00e3y vi\u1ebft th\u00eam helper function<\/strong> nh\u01b0 print_list()<\/code> ho\u1eb7c to_array()<\/code> \u0111\u1ec3 tr\u1ef1c quan h\u00f3a d\u1eef li\u1ec7u sau m\u1ed7i b\u01b0\u1edbc.<\/p>\n\n\n\n
                8. K\u1ebft lu\u1eadn<\/h2>\n\n\n\n
                  \n
                • Linked List l\u00e0 n\u1ec1n t\u1ea3ng c\u1ee7a nhi\u1ec1u c\u1ea5u tr\u00fac d\u1eef li\u1ec7u kh\u00e1c nh\u01b0 Stack, Queue, Graph v\u00e0 Cache.<\/li>\n\n\n\n
                • Hi\u1ec3u b\u1ea3n ch\u1ea5t con tr\u1ecf quan tr\u1ecdng h\u01a1n vi\u1ec7c h\u1ecdc thu\u1ed9c c\u00f4ng th\u1ee9c.<\/li>\n\n\n\n
                • V\u1ebd \u2013 M\u00f4 ph\u1ecfng \u2013 Code \u2013 T\u1ed1i \u01b0u: \u0111\u00f3 l\u00e0 chu tr\u00ecnh h\u1ecdc hi\u1ec7u qu\u1ea3 nh\u1ea5t.<\/li>\n<\/ul>\n\n\n\n
                  T\u1ed5ng k\u1ebft:<\/strong> Khi n\u1eafm v\u1eefng Linked List, b\u1ea1n s\u1ebd hi\u1ec3u s\u00e2u h\u01a1n c\u00e1ch d\u1eef li\u1ec7u v\u1eadn h\u00e0nh trong b\u1ed9 nh\u1edb v\u00e0 m\u1edf r\u1ed9ng t\u01b0 duy sang c\u00e1c c\u1ea5u tr\u00fac ph\u1ee9c t\u1ea1p nh\u01b0 Tree, Graph, Heap hay HashMap. Hi\u1ec3u r\u00f5 b\u1ea3n ch\u1ea5t tr\u01b0\u1edbc, t\u1ed1i \u01b0u sau \u2013 \u0111\u00f3 l\u00e0 t\u01b0 duy \u0111\u00fang \u0111\u1eafn khi h\u1ecdc thu\u1eadt to\u00e1n.<\/p>\n","protected":false},"excerpt":{"rendered":"
                  Linked List (Danh s\u00e1ch li\u00ean k\u1ebft) l\u00e0 m\u1ed9t trong nh\u1eefng c\u1ea5u tr\u00fac d\u1eef li\u1ec7u n\u1ec1n t\u1ea3ng trong l\u1eadp tr\u00ecnh. N\u00f3 \u0111\u01b0\u1ee3c h\u00ecnh th\u00e0nh t\u1eeb m\u1ed9t chu\u1ed7i c\u00e1c n\u00fat (nodes), trong \u0111\u00f3 m\u1ed7i node l\u01b0u gi\u00e1 tr\u1ecb (value) v\u00e0 m\u1ed9t con tr\u1ecf (pointer) tr\u1ecf \u0111\u1ebfn node ti\u1ebfp theo trong danh s\u00e1ch. C\u1ea5u tr\u00fac n\u00e0y \u0111\u1eb7c bi\u1ec7t h\u1eefu \u00edch […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[9],"tags":[],"class_list":["post-1234","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/seateklab.vn\/en\/wp-json\/wp\/v2\/posts\/1234","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/seateklab.vn\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/seateklab.vn\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/seateklab.vn\/en\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/seateklab.vn\/en\/wp-json\/wp\/v2\/comments?post=1234"}],"version-history":[{"count":0,"href":"https:\/\/seateklab.vn\/en\/wp-json\/wp\/v2\/posts\/1234\/revisions"}],"wp:attachment":[{"href":"https:\/\/seateklab.vn\/en\/wp-json\/wp\/v2\/media?parent=1234"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/seateklab.vn\/en\/wp-json\/wp\/v2\/categories?post=1234"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/seateklab.vn\/en\/wp-json\/wp\/v2\/tags?post=1234"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}