Câu hỏi phỏng vấn Linked Lists
Câu hỏi

So sánh việc triển khai Stack dựa trên mảng (Array) và dựa trên Linked List?

Câu trả lời

Có những khác biệt quan trọng giữa việc triển khai Stack dựa trên mảng và Linked List:

  1. Độ phức tạp thời gian:

    • Dựa trên mảng: Thêm và xóa phần tử ở đỉnh Stack có thể là O(1) nếu có đủ không gian, nhưng nếu mảng đầy và cần phải thay đổi kích thước, thì thời gian có thể là O(n) vì việc sao chép dữ liệu sang mảng mới.
    • Dựa trên Linked List: Thêm và xóa phần tử ở đỉnh Stack thường là O(1) vì chỉ cần thay đổi con trỏ, không cần phải sao chép dữ liệu.
  2. Khả năng mở rộng:

    • Dựa trên mảng: Có thể cần phải thay đổi kích thước mảng khi ...
middle

middle

Gợi ý câu hỏi phỏng vấn

junior

Liệt kê một số nhược điểm của Linked Lists?

middle

Khi nào thì nên sử dụng Danh sách (List) so với Danh sách Liên kết (LinkedList)?

junior

Trong singly-linked list, vòng lặp (cycle/loop) là gì?

Bình luận

Chưa có bình luận nào

Chưa có bình luận nào