Skip to main content

LinkedList trong Java

LinkedList là một lớp trong Java Collections Framework, cung cấp một cấu trúc dữ liệu danh sách liên kết kép. Mỗi phần tử trong LinkedList chứa dữ liệu và hai tham chiếu đến phần tử trước và sau nó.

1. Khai báo và khởi tạo LinkedList​

Khai báo LinkedList​

// Khai báo LinkedList kiểu Integer
LinkedList<Integer> numbers;

// Khai báo LinkedList kiểu String
LinkedList<String> names;

// Khai báo LinkedList kiểu Object
LinkedList<Object> objects;

Khởi tạo LinkedList​

// Khởi tạo LinkedList rỗng
LinkedList<Integer> numbers = new LinkedList<>();

// Khởi tạo LinkedList từ Collection khác
List<Integer> list = Arrays.asList(1, 2, 3);
LinkedList<Integer> numbers = new LinkedList<>(list);

2. Các phương thức cơ bản​

Thêm phần tử​

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

// Thêm vào đầu danh sách
names.addFirst("John");

// Thêm vào cuối danh sách
names.addLast("Alice");

// Thêm vào vị trí chỉ định
names.add(1, "Bob");

// Thêm nhiều phần tử
names.addAll(Arrays.asList("Charlie", "David"));

Xóa phần tử​

LinkedList<String> names = new LinkedList<>();
names.add("John");
names.add("Alice");
names.add("Bob");

// Xóa phần tử đầu tiên
names.removeFirst();

// Xóa phần tử cuối cùng
names.removeLast();

// Xóa theo vị trí
names.remove(0);

// Xóa theo giá trị
names.remove("Alice");

// Xóa tất cả phần tử
names.clear();

Truy cập phần tử​

LinkedList<String> names = new LinkedList<>();
names.add("John");
names.add("Alice");

// Lấy phần tử đầu tiên
String first = names.getFirst();

// Lấy phần tử cuối cùng
String last = names.getLast();

// Lấy phần tử theo vị trí
String element = names.get(1);

// Thay đổi phần tử tại vị trí
names.set(0, "Johnny");

3. Các phương thức đặc biệt​

Thao tác với đầu và cuối danh sách​

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

// Thêm vào đầu
names.offerFirst("John");

// Thêm vào cuối
names.offerLast("Alice");

// Lấy và xóa phần tử đầu tiên
String first = names.pollFirst();

// Lấy và xóa phần tử cuối cùng
String last = names.pollLast();

// Xem phần tử đầu tiên không xóa
String peekFirst = names.peekFirst();

// Xem phần tử cuối cùng không xóa
String peekLast = names.peekLast();

Chuyển đổi​

LinkedList<String> names = new LinkedList<>();
names.add("John");
names.add("Alice");

// Chuyển thành mảng
String[] array = names.toArray(new String[0]);

// Chuyển thành List
List<String> list = names.subList(0, names.size());

Sắp xếp​

LinkedList<Integer> numbers = new LinkedList<>();
numbers.add(5);
numbers.add(2);
numbers.add(8);

// Sắp xếp tăng dần
Collections.sort(numbers);

// Sắp xếp giảm dần
Collections.sort(numbers, Collections.reverseOrder());

4. Duyệt LinkedList​

Sử dụng vòng lặp for​

LinkedList<String> names = new LinkedList<>();
names.add("John");
names.add("Alice");

// Duyệt theo chỉ số
for (int i = 0; i < names.size(); i++) {
    System.out.println(names.get(i));
}

// Duyệt theo phần tử
for (String name : names) {
    System.out.println(name);
}

Sử dụng Iterator​

LinkedList<String> names = new LinkedList<>();
names.add("John");
names.add("Alice");

// Sử dụng Iterator
Iterator<String> iterator = names.iterator();
while (iterator.hasNext()) {
    String name = iterator.next();
    System.out.println(name);
}

// Sử dụng ListIterator
ListIterator<String> listIterator = names.listIterator();
while (listIterator.hasNext()) {
    String name = listIterator.next();
    System.out.println(name);
}

5. Ví dụ thực tế​

Quản lý hàng đợi​

public class QueueManager {
    private LinkedList<Task> queue;
    
    public QueueManager() {
        queue = new LinkedList<>();
    }
    
    public void addTask(Task task) {
        queue.offerLast(task);
    }
    
    public Task processNextTask() {
        return queue.pollFirst();
    }
    
    public Task peekNextTask() {
        return queue.peekFirst();
    }
    
    public boolean isEmpty() {
        return queue.isEmpty();
    }
}

Quản lý lịch sử duyệt web​

public class BrowserHistory {
    private LinkedList<String> history;
    
    public BrowserHistory() {
        history = new LinkedList<>();
    }
    
    public void visit(String url) {
        history.offerLast(url);
    }
    
    public String goBack() {
        return history.pollLast();
    }
    
    public String goForward() {
        return history.pollFirst();
    }
    
    public void clearHistory() {
        history.clear();
    }
}

6. Best Practices​

  1. Chọn LinkedList khi cần thao tác với đầu và cuối danh sách

    // Không nên
    ArrayList<String> names = new ArrayList<>();
    names.add(0, "John"); // Chậm hơn với ArrayList

    // Nên
    LinkedList<String> names = new LinkedList<>();
    names.addFirst("John"); // Nhanh hơn với LinkedList

  2. Sử dụng các phương thức đặc biệt của LinkedList

    // Không nên
    LinkedList<String> names = new LinkedList<>();
    names.add(names.size(), "John");

    // Nên
    LinkedList<String> names = new LinkedList<>();
    names.addLast("John");

  3. Tránh truy cập ngẫu nhiên với LinkedList

    // Không nên
    LinkedList<String> names = new LinkedList<>();
    for (int i = 0; i < names.size(); i++) {
        System.out.println(names.get(i)); // Chậm với LinkedList
    }

    // Nên
    LinkedList<String> names = new LinkedList<>();
    for (String name : names) {
        System.out.println(name); // Nhanh hơn
    }

7. Lỗi thường gặp​

  1. NoSuchElementException

    LinkedList<String> names = new LinkedList<>();
    names.getFirst(); // Lỗi: LinkedList rỗng

  2. ConcurrentModificationException

    LinkedList<String> names = new LinkedList<>();
    names.add("John");

    for (String name : names) {
        names.remove(name); // Lỗi: sửa đổi trong khi duyệt
    }

  3. NullPointerException

    LinkedList<String> names = null;
    names.add("John"); // Lỗi: LinkedList chưa được khởi tạo