reverse List trong Java sử dụng đệ quy

Nếu bạn đã từng cần phải reverse một List trong Java, chắc hẳn bạn đã nghe đến phương thức Collections.reverse(). Điều đầu tiên, mình lưu ý là nên sử dụng phương thức này cho các trường hợp mà bạn cần dùng để reverse một List trong Java, vì đơn giản nó được viết bởi những Java expert, đã được test bởi bao thế hệ Java coder.

Nhưng đã bao giờ bạn tự hỏi là nếu tự mình viết lại phương thức đó thì mình sẽ viết thế nào chưa? Hoặc là trong bài tập về nhà, phỏng vấn thì đây chính là bài viết mà bạn cần. Bạn cũng có thể sử dụng kĩ thuật này để sử dụng trong việc reverse mọi List trong Java, ví dụ: List of Integers, List of String, List các thể loại object khác mà bạn tạo ra: cars, houses,… Đầu tiên mình nói một ít về recursion algorithm, khi ta nói một hàm đệ quy thì điều đó tương đương với việc hàm đó tự gọi chính nó để làm một việc gì đó. Sau mỗi bước, công việc sẽ dần dần nhỏ dần cho đến khi nó trở thành một công việc đơn giản nhất (điểm neo). Điểm neo này cực kì quan trọng trong Recursion, vì nếu không có nó, hoặc có nhưng sai thì vòng lặp đệ quy sẽ chạy mãi, cho đến khi Stack và Heap của bạn hết vùng nhớ để cấp phát thì thôi.

Trong trường hợp sử dụng đệ quy trong một List thì trường hợp đơn giản nhất sẽ là List có một phần tử. Quay trở lại việc reverse một mảng thì việc reverse một mảng 1 phần tử và chúng ta sẽ return chính nó luôn. Vậy, trong bài này mình sẽ tạo một method: reverseList(List<T>list) , mỗi lần gọi method này, chúng ta sẽ thực hiện đưa phần tử cuối cùng vào một list mới. Cho đến khi nó gặp điểm neo (chỉ còn 1 phần tử) thì chúng ta sẽ return chính nó. Chúng ta sẽ sử dụng method addAll() của java.util.Collection.

Source code:

import java.util.ArrayList;
import java.util.List;

public class Main {

    public static void main(String[] args) {
        List<String> colors = new ArrayList<>();
        colors.add("Red");
        colors.add("Green");
        colors.add("Blue");
        colors.add("Black");
        colors.add("White");
        System.out.println("Thu tu ban dau cua list:" + colors);
//        Collections.reverse(colors);
//        System.out.println("Thu tu sau khi thuc hien Collections.reverse(): "+colors);
        List<String> output = reverseList(colors);
        System.out.println("Thu tu sau khi thuc hien reverse: " + output);
    }

    private static List<String> reverseList(List<String> list) {
        // Diem neo, khi list chi co 1 phan tu
        if (list.size() <= 1) {
            return list;
        }
        List<String> reversed = new ArrayList<>();
        // dua phan tu cuoi list vao mot list moi
        reversed.add(list.get(list.size() - 1));
        // thuc hien de quy voi list moi
        reversed.addAll(reverseList(list.subList(0, list.size() - 1)));
        return reversed;
    }

}

Output:

Thu tu ban dau cua list:[Red, Green, Blue, Black, White]
Thu tu sau khi thuc hien reverse: [White, Black, Blue, Green, Red]

Tất nhiên bài viết này chỉ dùng cho mục đích như đã nói ở trên, khi phải reverse các List thì nên sử dụng phương thức Collections.reverse() và tất nhiên là nếu sử dụng đệ quy cho những List có số lượng phần tử lớn thì nó cũng không khả thi bởi nó chiếm khá nhiều bộ nhớ.

Reference: http://javarevisited.blogspot.com/