LinkedList trong java

1. Giới thiệu

Danh sách có kết nối ( Linked List) là một trong các cách quản lý danh sách dữ liệu khắc phục được các nhược điểm của mảng.

Lớp LinkedList trong java sử dụng cấu trúc danh sách liên kết Doubly Linked List để lưu trữ các phần tử.

Chi tiết về cấu trúc dữ liệu LinkedList tôi sẽ trình bày ở bài viết khác, trong phạm vi bài này tôi chỉ giới thiệu cách sử dụng LinkedList trong Java.

Những điểm cần ghi nhớ về lớp LinkedList:

• Có thể chứa các phần tử trùng lặp.
• Duy trì thứ tự của phần tử được thêm vào.
• Không đồng bộ (non-synchronized).
• Thao tác thêm/ xóa (add/ remove) phần tử nhanh vì không cần phải dịch chuyển nếu bất kỳ phần tử nào thêm/ xoá khỏi danh sách.
• LinkedList có thể được sử dụng như danh sách (list), stack (ngăn xếp) hoặc queue (hàng đợi).
• Các phần tử trong LinkedList có thể nằm cách ly nhau (không liên tục) trong bộ nhớ. Nó là một liên kết có tính hai chiều giữa các phần tử. Mỗi phần tử trong danh sách cầm giữ một tham chiếu đến đối phần tử đằng trước nó và tham chiếu đến phần tử ngay sau nó.

2. Hierarchy của lớp LinkedList trong java

Lớp java.util.LinkedList được định nghĩa như sau:

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

3. Các phương thức khởi tạo (constructor) của lớp LinkedList

• LinkedList(): khởi tạo một danh sách trống.
• LinkedList(Collection c): khởi tạo một danh sách với các phần tử của collection c.

4. Các phương thức (method) của lớp LinkedList

5. Ví dụ minh họa

Ví dụ sử dụng LinkedList với kiểu dữ liệu cơ bản (Wrapper)

package com.maixuanviet.collection.linkedlist;
 
import java.util.LinkedList;
import java.util.List;
 
public class LinkedListExample {
    public static final int NUM_OF_ELEMENT = 5;
 
    public static void main(String[] args) {
        // Create list with no parameter
        List<String> list1 = new LinkedList<>();
        for (int i = 1; i <= NUM_OF_ELEMENT; i++) {
            // Add element to list
            list1.add("0" + i);
        }
        System.out.print("Init list1 = ");
        printData(list1);
 
        // addAll()
        List<String> list2 = new LinkedList<>();
        list2.addAll(list1);
        list2.add("0" + 3);
        System.out.print("After list1.addAll(03): list2 = ");
        printData(list2);
         
        // IndexOf()
        System.out.println("list2.indexOf(03) = " + list2.indexOf("03"));
        System.out.println("list2.indexOf(06) = " + list2.indexOf("06"));
         
        // lastIndexOf()
        System.out.println("list2.lastIndexOf(03) = " + list2.lastIndexOf("03"));
         
        // Remove
        list2.remove("01");
        System.out.print("After list2.remove(01): list2 = ");
        printData(list2);
         
        // retainAll()
        List<String> list4 = new LinkedList<>(list1);
        LinkedList<String> list3 = new LinkedList<String>();
        list3.add("0" + 3);
        list3.add("0" + 2);
        System.out.print("Init list3 = ");
        printData(list3);
        list4.retainAll(list3);
        System.out.print("After list1.retainAll(list3): list4 = ");
        printData(list4);
         
        // removeAll()
        List<String> list5 = new LinkedList<>(list1);
        list5.removeAll(list3);
        System.out.print("After list1.removeAll(list3): list5 = ");
        printData(list5);
    }
 
    public static void printData(List<String> list) {
        // Show list through for-each
        for (String item : list) {
            System.out.print(item + " ");
        }
        System.out.println();
    }
 
}

Kết quả thực thi chương trình trên:

Init list1 = 01 02 03 04 05
After list1.addAll(03): list2 = 01 02 03 04 05 03
list2.indexOf(03) = 2
list2.indexOf(06) = -1
list2.lastIndexOf(03) = 5
After list2.remove(01): list2 = 02 03 04 05 03
Init list3 = 03 02
After list1.retainAll(list3): list4 = 02 03
After list1.removeAll(list3): list5 = 01 04 05

Ví dụ sử dụng LinkedList với kiểu do người dùng tự định nghĩa (Object)

package com.maixuanviet.collection.linkedlist;
 
import java.util.LinkedList;
import java.util.List;
 
class Student {
    private int id;
    private String name;
 
    public Student(int id, String name) {
        this.id = id;
        this.name = name;
    }
 
    @Override
    public String toString() {
        return "Student [id=" + id + ", name=" + name + "]";
    }
}
 
public class LinkedListExample {
    public static final int NUM_OF_ELEMENT = 5;
 
    public static void main(String[] args) {
        // Create list 
        List<Student> students = new LinkedList<>();
        for (int i = 1; i <= NUM_OF_ELEMENT; i++) {
            // Add element to list
            Student student = new Student(i, "myname" + i);
            students.add(student);
        }
 
        // Show list student
        for (Student student : students) {
            System.out.println(student);
        }
    }
}
&#91;/code&#93;
<!-- /wp:shortcode -->

<!-- wp:paragraph -->
<p>Kết quả thực thi chương trình trên:</p>
<!-- /wp:paragraph -->

<!-- wp:shortcode -->

Student [id=1, name=myname1]
Student [id=2, name=myname2]
Student [id=3, name=myname3]
Student [id=4, name=myname4]
Student [id=5, name=myname5]

Như các bạn thấy, cách khai báo, sử dụng LinkedList hoàn toàn tương tự như ArrayList. Vậy LinkedList và ArrayList có gì khác nhau, chúng ta hãy cùng tìm hiểu ở bài viết kế tiếp nhé.4.8