1. LinkedList là gì?
LinkedList trong Java là một trong những cấu trúc dữ liệu thuộc thư viện Java Collections Framework. Nó thực hiện cả hai giao diện List và Deque, vì vậy nó có thể hoạt động như một danh sách hoặc một hàng đợi.
2. Đặc điểm chính của LinkedList
- Cấu trúc: LinkedList được triển khai theo kiểu danh sách liên kết kép (Doubly Linked List), tức là mỗi phần tử (
Node) có hai con trỏ, một trỏ đến phần tử phía trước và một trỏ đến phần tử phía sau. - Thao tác: So với
ArrayList,LinkedListcó khả năng thêm và xóa phần tử ở đầu hoặc cuối danh sách hiệu quả hơn (O(1)) vì chỉ cần cập nhật các liên kết giữa các phần tử mà không cần di chuyển dữ liệu. Tuy nhiên, việc truy cập phần tử ở một vị trí bất kỳ chậm hơnArrayList(O(n)) vì cần phải duyệt qua các phần tử trong danh sách. - Các phương thức quan trọng:
addFirst(),addLast(): Thêm phần tử vào đầu/cuối danh sách.removeFirst(),removeLast(): Xóa phần tử đầu/cuối danh sách.getFirst(),getLast(): Truy cập phần tử đầu/cuối.add(index, element): Thêm phần tử vào vị trí chỉ định.remove(index): Xóa phần tử tại vị trí chỉ định.
- Ưu điểm và nhược điểm:
- Ưu điểm: Thêm và xóa phần tử nhanh ở đầu hoặc cuối danh sách.
- Nhược điểm: Truy cập phần tử chậm khi so sánh với
ArrayList, vìLinkedListkhông hỗ trợ truy cập ngẫu nhiên trực tiếp.
– Ví dụ:
import java.util.LinkedList;
public class App {
public static void main(String[] args) {
LinkedList list = new LinkedList<>();
// Thêm phần tử
list.add("Cam");
list.add("Quýt");
list.addFirst("Mít");
list.addLast("Dừa");
// In ra danh sách
System.out.println("Danh sách: " + list);
// Xóa phần tử đầu và cuối
list.removeFirst();
list.removeLast();
// Truy cập phần tử
String firstElement = list.getFirst();
String lastElement = list.getLast();
System.out.println("Phần tử đầu: " + firstElement);
System.out.println("Phần tử cuối: " + lastElement);
}
}
– Kết quả:
Danh sách: [Mít, Cam, Quýt, Dừa] Phần tử đầu: Cam Phần tử cuối: Quýt
3. Câu hỏi phỏng vấn LinkedList
3.1 Câu hỏi lý thuyết
- LinkedList trong Java là gì? So sánh LinkedList với ArrayList.
- Doubly Linked List và Singly Linked List khác nhau như thế nào? Java LinkedList thuộc loại nào?
- Các ưu và nhược điểm của LinkedList là gì? Khi nào nên dùng LinkedList thay vì ArrayList?
- LinkedList có hỗ trợ truy cập ngẫu nhiên (random access) không? Giải thích tại sao.
- LinkedList là synchronized hay không? Nếu không, làm thế nào để tạo một phiên bản LinkedList an toàn cho đa luồng (thread-safe)?
3.2 Câu hỏi thao tác với LinkedList
- Làm thế nào để thêm/xóa phần tử đầu hoặc cuối trong LinkedList? Cho biết thời gian thực thi của các thao tác này.
- Giải thích các phương thức addFirst(), addLast(), removeFirst(), removeLast() trong LinkedList.
- Viết code để đảo ngược một LinkedList.
- Làm thế nào để tìm phần tử ở giữa của một LinkedList mà không dùng size()?
3.3 Câu hỏi thực hành và thuật toán
- Đảo ngược LinkedList: Viết code Java để đảo ngược một LinkedList.
- Xác định vòng lặp trong LinkedList: Làm thế nào để biết một LinkedList có vòng lặp hay không? Hãy giải thích thuật toán Floyd’s Cycle Detection (hay còn gọi là thuật toán “Tortoise and Hare”).
- Tìm phần tử ở giữa của một LinkedList: Viết code tìm phần tử ở giữa LinkedList
- Tìm phần tử thứ k từ cuối: Viết code để tìm phần tử k từ cuối trong một LinkedList.
- Xóa các phần tử trùng lặp trong LinkedList không có thứ tự: Viết code để xóa các phần tử trùng lặp trong một LinkedList không có thứ tự.
- Kết hợp hai LinkedList đã sắp xếp: Cho hai LinkedList đã sắp xếp, hãy viết code để hợp nhất chúng thành một danh sách đã sắp xếp.
3.4 Câu hỏi nâng cao
- Thiết kế cấu trúc dữ liệu LinkedList: Bạn sẽ thiết kế một LinkedList tùy chỉnh như thế nào nếu Java không có sẵn?
- Tối ưu hóa bộ nhớ: Giả sử bạn có một LinkedList rất lớn, bạn sẽ tối ưu hóa nó như thế nào để tiết kiệm bộ nhớ?
- Triển khai stack và queue bằng LinkedList: Bạn sẽ triển khai stack và queue bằng LinkedList như thế nào? Giải thích các thao tác push, pop, enqueue, dequeue.
