LinkedList là một cấu trúc dữ liệu quan trọng trong ngôn ngữ lập trình Java, nó cung cấp một cách linh hoạt để lưu trữ và quản lý dữ liệu. LinkedList được hình thành bởi chuỗi các nút liên kết với nhau qua các con trỏ được tham chiếu từ nút này tới nút kế tiếp trong danh sách. Điều này cho phép chèn và xóa dữ liệu một cách hiệu quả, phù hợp với các cấu trúc dữ liệu động.

Trong bài viết này, chúng ta sẽ khám phá chi tiết về cấu trúc LinkedList trong Java.

Lớp LinkedList trong Java

Lớp LinkedList trong Java là một phần của Collections Frameworks, nó sử dụng cấu trúc danh sách kép(doubly linked-list) để lưu trữ các phần tử và cung cấp một cấu trúc lưu trữ có dạng danh sách liên kết. LinkedList trong Java là một lớp kế thừa lớp AbstractSequentialList và triển khai của interface List, Queue trong Collections Framework.

Một số đặc điểm cần lưu ý về LinkedList:

- Lớp LinkedList có thể chứa nhiều phần tử trùng lặp.

- Lớp LinkedList duy trì thứ tự điền các phần tử của nó.

- Lớp LinkedList không có tính tuần đồng bộ(non-synchronized), các thao tác bất đồng bộ lên nó có thể gây ra các sai sót

- Thao tác với các phần tử trong LinkedList là nhanh vì không cần phải thực hiện dịch chuyển bất kỳ phần tử nào

- Có thể sử dụng LinkedList như một List(danh sách), Stack(ngăn xếp) hay là Queue(hàng đợi)

LinkedList hoạt động như thế nào ?

Vì LinkedList hoạt động như một mảng động và chúng ta không cần thực hiện định nghĩa kích thước khi khởi tạo nó, kích thước của list sẽ tự động tăng khi chúng ta thực hiện thêm và xóa phần tử. Các phần tử trong danh sách không được lưu trữ liền kề nhau. Chính vì vậy, việc tăng kích thước của nó là không thực sự cần thiết.

LinkedList sử dụng một danh sách liên kết kép. Ở đây chúng ta thấy có một sự khác biệt lớn giữa danh sách liên kết kép và danh sách liên kết đó là danh sách liên kết kép có nhiều hơn một con trỏ so với danh sách liên kết đơn, gọi là con trỏ trước trỏ tới phần tử trước phần tử hiện trọng trong danh sách. Trong khi đó danh sách liên kết đơn thì chỉ có duy nhất một con trỏ gọi là con trỏ kế tiếp luôn luôn trỏ tới phần tử tiếp theo trong danh sách.

Định nghĩa của LinkedList trong Java

LinkedList là một lớp thuộc package java.util và có định nghĩa như sau:

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, Serializable

Hãy cùng xem Hierarchy của LinkedList để thấy rõ hơn quan hệ của nó trong Java

{width="3.7604166666666665in" height="5.635416666666667in"}

Constructor của lớp LinkedList trong Java

Để tạo một LinkedList, chúng ta cần tạo một đối tượng thuộc lớp LinkedList. Lớp LinkedList cung cấp cho chúng ta nhiều constructor để thực hiện khởi tạo một danh sách. Sau đây là ví dụ về một số constructor có thể sử dụng được:

1. LinkedList(): constructor này được sử dụng để khởi tạo một LinkedList rỗng. Nếu chúng ta muốn khởi tạo một LinkedList với tên là list, well, chúng ta có thể khởi tạo như sau:

LinkedList list = new LinkedList();

2. LinkedList(Collection c): constructor này được sử dụng để tạo mộtdanh sách đã được sắp xếp với toàn bộ các phần tử của một collection, các phần tử sẽ được sắp xếp theo iterator của collection.

LinkedList list = new LinkedList(c);

Các phương thức của lớp LinkedList trong Java:

6. Thực hiện một số ví dụ với LinkedList trong Java

Trong phần này chúng ta sẽ tìm hiểu một số ví dụ với LinkedList trong Java qua các ví dụ dưới đây:

- Thêm phần tử

- Thay đổi phần tử

- Xóa phần tử

- Duyệt qua các phần tử

- Chuyển danh sách thành mảng

- Trả về kích thước của danh sách

- Xóa phần tử đầu

- Xóa phần tử cuối

6.1 Thêm phần tử vào danh sách

Để có thể thực hiện thêm phần tử vào danh sách, chúng ta có thể sử dụng phương thức add(). Phương thức này được thực hiện nạp chồng(overload) để thực hiện nhiều thao tác dựa trên các giá trị đầu vào khác nhau. Các phương thức add() được cung cấp gồm có:

- add(Object): Phương thức này cho phép thêm một phần tử vào cuối của LinkedList.

- add(int index, Object): Phương thức này được sử dụng để thêm một phần tử vào một vị trí được chỉ định trong LinkedList.

public class ListMain1 {

    public static void main(String[] args) {

        // initiated a list
        LinkedList<String> list = new LinkedList<>();

        // add element to list
        list.add("A");

        list.add("B");

        list.add("C");

        list.add(3, "D");

        // print out the list
        System.out.println(list);

    }

}

Kết quả chạy chương trình

[A, B, C, D]

6.2 Thay đổi phần tử trong danh sách

Sau khi đã thực hiện thêm phần tử vào trong danh sách, nếu chúng ta muốn thực hiện thay đổi một phần tử, ta có thể sử dụng phương thức set().

Vì LinkedList đã được đánh chỉ mục, các phần tử chúng ta muốn thực hiện thay đổi sẽ được truy cập tới bằng chỉ mục của nó. Vì vậy, phương thức này nhận đầu vào là chỉ mục của phần tử cần thực hiện thay đổi và giá trị được cập nhật sẽ được điền vào vị trí chỉ mục đó.

public class ListMain2 {

    public static void main(String[] args) {

        LinkedList<String> list = new LinkedList<>();

        list.add("Foo");
        list.add("Bar");

        System.out.println("First List " + list);

        list.set(1, "Foo");

        System.out.println("Updated List " + list);

    }

}

Kết quả chạy chương trình

First List [Foo, Bar]
Updated List [Foo, Foo]

6.3 Xóa phần tử

Để xóa phần tử khỏi danh một LinkedList, chúng ta có thể sử dụng phương thức remove(). Phương thức này được nạp chồng để thực hiện nhiều phương thức dựa trên các đầu vào khác nhau. Các phương thức nạp chồng của remove() là:

• remove(Object): Phương thức này được sử dụng để xóa một đối tượng khỏi LinkedList. Nếu có nhiều phần tử là đối tượng này trong LinkedList thì phần tử đầu tiên xuất hiện sẽ bị xóa bỏ

• remove(int index): Vì LinkedList đã được đánh chỉ mục, phương thức này nhận một giá trị số nguyên và sẽ xóa bỏ phần tử ở vị trí đó trong LinkedList. Sau khi đã xóa phần tử và các chỉ mục còn lại được cập nhật thì các đối tượng được lưu trữ trong LinkedList cũng được cập nhật, kết quả trả về cho chúng ta là một List sau khi hoàn thành quá trình xóa bỏ (các) phần tử

public class ListMain3 {

    public static void main(String[] args) {

        LinkedList<String> list = new LinkedList<>();

        list.add("Foo");
        list.add("Foo");
        list.add("Bar");

        System.out.println("First List " + list);

        list.remove(0);

        System.out.println("List after Index removal " + list);

        list.remove("Foo");

        System.out.println("List after Object removal " + list);

    }

}

Kết quả chạy chương trình

First List [Foo, Foo, Bar]

List after Index removal [Foo, Bar]

List after Object removal [Bar]

6.4 Duyệt qua các phần tử trong LinkedList

Có nhiều cách để thực hiện duyệt qua các phần tử của LinkedList. Ở đây, chúng ta sẽ sử dụng cách được sử dụng rộng rãi nhất đó là sử dụng một vòng lặp với phương thức get() để truy cập từng phần tử trong danh sách qua chỉ mục của từng phần tử

public class ListMain4 {

    public static void main(String[] args) {

        LinkedList<String> list = new LinkedList<>(

                Arrays.asList("A", "B", "C", "D", "E")

        );

        // using index to iterate through the list

        for(int index = -1; ++index < list.size();) {

            System.out.println("Element of list at index " + index + " is: " + list.get(index));

        }

        // using foreach to iterate through the list

        for(String val : list) {

            System.out.print(val + "\t");

        }

    }

}

Kết quả chạy chương trình

Element of list at index 0 is: A

Element of list at index 1 is: B

Element of list at index 2 is: C

Element of list at index 3 is: D

Element of list at index 4 is: E

A B C D E

6.5 Chuyển danh sách thành mảng

public class ListMain5 {

    public static void main(String[] args) {

        LinkedList<String> list = new LinkedList<>();

        list.add("A");
        list.add("B");
        list.add("C");

        System.out.println("LinkedList: " + list);

        Object[] arr = list.toArray();

        System.out.println("From LinkedList to array: " + arr);

        for (Object val : arr) {
            System.out.print(val + "\t");
        }

    }

}

Kết quả chạy chương trình

LinkedList: [A, B, C]

From LinkedList to array: [Ljava.lang.Object;@3cd1f1c8

A B C

6.6 Trả về kích thước của danh sách

public class ListMain6 {

    public static void main(String[] args) {

        LinkedList<String> list = new LinkedList<>();

        list.add("This");
        list.add("is");
        list.add("a");
        list.add("LinkedList");

        System.out.println("The size of the list is " + list.size());

    }

}

Kết quả chạy chương trình:

The size of the list is 4

6.7 Xóa phần tử đầu tiên

public class ListMain7 {

    public static void main(String[] args) {

        LinkedList<Integer> list = new LinkedList<>();

        list.add(1);
        list.add(2);
        list.add(3);

        System.out.println("LinkedList " + list);

        list.removeFirst();

        System.out.println("LinkedList after removal " + list);

    }

}

Kết quả sau khi chạy chương trình

LinkedList [1, 2, 3]

LinkedList after removal [2, 3]

6.8 Xóa phần tử cuối cùng

public class ListMain8 {

    public static void main(String[] args) {

        LinkedList<Integer> list = new LinkedList<>();

        list.add(1);
        list.add(2);
        list.add(3);

        System.out.println("LinkedList " + list);

        list.removeLast();

        System.out.println("LinkedList after removal " + list);

    }

}

Kết quả sau khi chạy chương trình

LinkedList [1, 2, 3]

LinkedList after removal [1, 2]

LinkedList cung cấp một cách linh hoạt và hiệu quả để lưu trữ và quản lý dữ liệu. Với các tác vụ cần thực hiện chèn và xóa dữ liệu hiệu quả thì LinkedList luôn là một sự lựa chọn lý tưởng với các lập trình viên nhấtlà với nhu cầu thao tác với các cấu trúc dữ liệu động. Với những ưu điểm đặc trưng này, LinkedList là một phần quan trọng trong công cụ phát triển Java.

Stringee API cung cấp các tính năng như gọi thoại, gọi video, tin nhắn chat, SMS hay tổng đài chăm sóc khách hàng (CSKH) có thể được nhúng trực tiếp vào các ứng dụng/website của doanh nghiệp nhanh chóng. Điều này giúp tiết kiệm đến 80% thời gian và chi phí cho doanh nghiệp, trong khi nếu tự phát triển các tính năng này có thể mất từ 1 - 3 năm.