List (danh sách liên kết) trong C++

  • List được thực hiện như danh sách nối kép (doubly-linked list). Mỗi phần tử trong danh sách nối kép có liên kết đến một phần tử trước đó và một phần tử sau nó.
  • Do đó, list có các ưu điểm như sau:
    1. Chèn và loại bỏ phần tử ở bất cứ vị trí nào trong container. O(1).
  • Điểm yếu của list là khả năng truy cập tới phần tử thông qua vị trí. O(n).
  • Khai báo: #include <list>

Các hàm thành viên:

Capacity:

  • size : trả về số lượng phần tử của list. ĐPT O(1).
  • empty : trả về true(1) nếu list rỗng, ngược lại là false(0). ĐPT O(1).

 

Truy cập phần tử:

  • front: trả về giá trị phần tử đầu tiên. ĐPT O(1).
  • back: trả về giá trị phần tử cuối cùng. ĐPT O(1).

 

Chỉnh sửa:

  • push_back : thêm phần tử vào ở cuối list. ĐPT O(1).
  • push_front : thêm phần tử vào đầu list. ĐPT O(1).
  • pop_back : loại bỏ phần tử ở cuối list. ĐPT O(1).
  • pop_front : loại bỏ phần tử ở đầu list. ĐPT O(1).
  • insert (iterator,x): chèn “x” vào trước vị trí “iterator” ( x có thể là phần tử hay iterator của 1 đoạn phần tử…). ĐPT là số phần tử thêm vào.
  • erase : xóa phần tử ở vị trí iterator. ĐPT là số phần tử bị xóa đi.
  • swap : đổi 2 list cho nhau (ví dụ: first.swap(second);). ĐPT O(1).
  • clear: xóa list. ĐPT O(n).

 

Operations:

  • splice : di chuyển phần tử từ list này sang list khác. ĐPT O(n).
  • remove (const) : loại bỏ tất cả phần tử trong list bằng const. ĐPT O(n).
  • remove_if (function) : loại bỏ tất các phần tử trong list nếu hàm function return true . ĐPT O(n).
  • unique : loại bỏ các phần tử bị trùng lặp hoặc thỏa mãn hàm nào đó. ĐPT O(n). Lưu ý: Các phần tử trong list phải được sắp xếp.
  • sort : sắp xếp các phần tử của list. O(NlogN)
  • reverse : đảo ngược lại các phần tử của list. O(n).
Khuyên dùng

 

Speak Your Mind

*