Mấy hôm nay do hơi bận công việc nên mình không viết blog được nhiều. Lúc mà mình bắt tay vào viết bài này là 11h hơn vừa xong việc luôn.
Thì hôm trước mình có giới thiệu về ArrayList, bài hôm nay mình sẽ nói qua về LinkedList.LinkedList : (hay còn gọi là Danh sách liên kết). Giống như ArrayList là một lớp triển khai của List Interface trong Collections Framework nên nó sẽ có một vài đặc điểm và phương thức tương đồng với List.
Điểm giống nhau giữa ArrayList và LinkedList :
+ duy trì thứ tự của phần tử được thêm vào.
+ Cả hai lớp này đều là lớp không đồng bộ (non-synchronized).
Ngoài ra thì LinkedList còn là một lớp triển khai của Queue Interface.
Về việc khởi tạo 1 LinkedList, cũng tương tự như ArrayList ta làm như sau.
List<String> myList1 = new LinkedList<>();hoặc
LinkedList<String> linkedList = new LinkedList<>();Bạn có thể khai báo bằng một trong hai cách trên, còn vì sao như vậy mình mình đã nói ở bài trước. Nếu ai chưa đọc bài trước thì có thể ấn vào đây để đọc lại.
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ử.
Một Danh sách liên kết (Linked List) là một dãy các cấu trúc dữ liệu được kết nối với nhau thông qua các liên kết (link). Hiểu một cách đơn giản thì Danh sách liên kết là một cấu trúc dữ liệu bao gồm một nhóm các nút (node) tạo thành một chuỗi. Mỗi nút gồm dữ liệu ở nút đó và tham chiếu đến nút kế tiếp trong chuỗi.
Khác với ArrayList là ArrayList là 1 tập hợp các phần tử liên tiếp nhau trong bộ nhớ còn LinkedList thì không liên tiếp.
Danh sách liên kết là cấu trúc dữ liệu được sử dụng phổ biến thứ hai sau mảng. Dưới đây là các khái niệm cơ bản liên quan tới Danh sách liên kết:
- Link (liên kết): mỗi link của một Danh sách liên kết có thể lưu giữ một dữ liệu được gọi là một phần tử.
- Next: Mỗi liên kết của một Danh sách liên kết chứa một link tới next link được gọi là Next.
- First: một Danh sách liên kết bao gồm các link kết nối tới first link được gọi là First.
Biểu diễn Danh sách liên kết (Linked List)
Danh sách liên kết có thể được biểu diễn như là một chuỗi các nút (node). Mỗi nút sẽ trỏ tới nút kế tiếp.
Dưới đây là một số điểm cần nhớ về Danh sách liên kết:
- Danh sách liên kết chứa một phần tử link thì được gọi là First.
- Mỗi link mang một trường dữ liệu và một trường link được gọi là Next.
- Mỗi link được liên kết với link kế tiếp bởi sử dụng link kế tiếp của nó.
- Link cuối cùng mang một link là null để đánh dấu điểm cuối của danh sách.
Các loại Danh sách liên kết (Linked List)
Dưới đây là các loại Danh sách liên kết (Linked List) đa dạng:
- Danh sách liên kết đơn (Simple Linked List): chỉ duyệt các phần tử theo chiều về trước.
- Danh sách liên kết đôi (Doubly Linked List): các phần tử có thể được duyệt theo chiều về trước hoặc về sau.
- Danh sách liên kết vòng (Circular Linked List): phần tử cuối cùng chứa link của phần tử đầu tiên như là next và phần tử đầu tiên có link tới phần tử cuối cùng như là prev.
Các hoạt động cơ bản trên Danh sách liên kết
Dưới đây là một số hoạt động cơ bản có thể được thực hiện bởi một danh sách liên kết:
- Hoạt động chèn: thêm một phần tử vào đầu danh sách liên kết.
- Hoạt động xóa (phần tử đầu): xóa một phần tử tại đầu danh sách liên kết.
- Hiển thị: hiển thị toàn bộ danh sách.
- Hoạt động tìm kiếm: tìm kiếm phần tử bởi sử dụng khóa (key) đã cung cấp.
- Hoạt động xóa (bởi sử dụng khóa): xóa một phần tử bởi sử dụng khóa (key) đã cung cấp.
Hoạt động chèn trong Danh sách liên kết
Việc thêm một nút mới vào trong danh sách liên kết không chỉ là một hoạt động thêm đơn giản như trong các cấu trúc dữ liệu khác (bởi vì chúng ta có dữ liệu và có link). Chúng ta sẽ tìm hiểu thông qua sơ đồ dưới đây. Đầu tiên, tạo một nút bởi sử dụng cùng cấu trúc và tìm vị trí để chèn nút này.
Giả sử chúng ta cần chèn một nút B vào giữa nút A (nút trái) và C (nút phải). Do đó: B.next trỏ tới C.
NewNode.next −> RightNode;
Hình minh họa như sau:
Bây giờ, next của nút bên trái sẽ trỏ tới nút mới.
LeftNode.next −> NewNode;
Quá trình trên sẽ đặt nút mới vào giữa hai nút. Khi đó danh sách mới sẽ trông như sau:
Các bước tương tự sẽ được thực hiện nếu chèn nút vào đầu danh sách liên kết. Trong khi đặt một nút vào vị trí cuối của danh sách, thì nút thứ hai tính từ nút cuối cùng của danh sách sẽ trỏ tới nút mới và nút mới sẽ trỏ tới NULL.
Hoạt động xóa trong Danh sách liên kết
Hoạt động xóa trong Danh sách liên kết cũng phức tạp hơn trong cấu trúc dữ liệu khác. Đầu tiên chúng ta cần định vị nút cần xóa bởi sử dụng các giải thuật tìm kiếm.
Bây giờ, nút bên trái (prev) của nút cần xóa nên trỏ tới nút kế tiếp (next) của nút cần xóa.
LeftNode.next −> TargetNode.next;
Quá trình này sẽ xóa link trỏ tới nút cần xóa. Bây giờ chúng ta sẽ xóa những gì mà nút cần xóa đang trỏ tới.
TargetNode.next −> NULL;
Nếu bạn cần sử dụng nút đã bị xóa này thì bạn có thể giữ chúng trong bộ nhớ, nếu không bạn có thể xóa hoàn toàn hẳn nó khỏi bộ nhớ.
Hoạt động đảo ngược Danh sách liên kết
Với hoạt động này, bạn cần phải cẩn thận. Chúng ta cần làm cho nút đầu (head) trỏ tới nút cuối cùng và đảo ngược toàn bộ danh sách liên kết.
Chúng ta phải đảm bảo rằng nút cuối cùng này sẽ không bị thất lạc, do đó chúng ta sẽ sử dụng một số nút tạm (temp node – giống như các biến tạm trung gian để lưu giữ giá trị). Tiếp theo, chúng ta sẽ làm cho từng nút bên trái sẽ trỏ tới nút trái của chúng.
Sau đó, nút đầu tiên sau nút head sẽ trỏ tới NULL.
Chúng ta sẽ làm cho nút head trỏ tới nút đầu tiên mới bởi sử dụng các nút tạm.
Bây giờ Danh sách liên kết đã bị đảo ngược.
Đọc đến đây có thể vẫn hơi mung lung đúng không nào =)) nếu chưa hiểu lắm thì quay lại 1 lần nữa đọc để xem cách thức LinkedList nó xử lý và lưu trữ dữ liệu ra sao nhé. Còn bây giờ thì chúng ta đi vào demo về việc xử dụng LinkedList.
Như đã nói bên trên thì LinkedList là 1 thể hiện từ List Interface nên nó cũng chứa các phương thức sau đây.
| Phương thức | Mô tả |
| void add(int index, Object element) | Chèn element đã xác định tại index đã cho. Ném một IndexOutOfBoundsException nếu index đã cho là ở bên ngoài dãy (index < 0 || index > size()) |
| boolean add(Object o) | Phụ thêm phần tử đã cho tới cuối của List này |
| boolean addAll(Collection c) | Phụ thêm tất cả phần tử trong collection đã cho tới cuối của list này, theo thứ tự mà chúng được trả về bởi Iterator của collection đã cho. Ném một NullPointerException nếu collection đã cho là null |
| boolean addAll(int index, Collection c) | Chèn tất cả phần tử trong collection đã cho vào trong List này, bắt đầu từ vị trí đã cho. Ném NullPointerException nếu collection đã cho là null |
| void addFirst(Object o) | Chèn phần tử đã cho vào phần đầu của list này |
| void addLast(Object o) | Phụ thêm phần tử đã cho vào phần cuối của list này |
| void clear() | Gỡ bỏ tất cả phần tử từ list này |
| Object clone() | Trả về một shallow copy của LinkedList này |
| boolean contains(Object o) | Trả về true nếu list này chứa phần tử đã cho. Chính thức hơn, trả về true nếu và chỉ nếu list này chứa ít nhất một phần tử e để mà (o==null ? e==null : o.equals(e)) |
| Object get(int index) | Trả về phần tử tại vị trí đã cho. Ném IndexOutOfBoundsException nếu index ở bên ngoài dãy (index < 0 || index >= size()) |
| Object getFirst() | Trả về phần tử đầu tiên trong list này. Ném NoSuchElementException nếu list này là trống |
| Object getLast() | Trả về phần tử cuối trong list này. Ném NoSuchElementException nếu list này là trống |
| int indexOf(Object o) | Trả về index trong list này cho sự xuất hiện đầu tiên của phần tử đã cho, hoặc -1 nếu List này không chứa phần tử này |
| int lastIndexOf(Object o) | Trả về index trong list này cho sự xuất hiện cuối của phần tử đã cho, hoặc -1 nếu List này không chứa phần tử này |
| ListIterator listIterator(int index) | Trả về một list-iterator của phần tử trong list này (trong dãy chính xác), bắt đầu từ vị trí đã cho trong list. Ném IndexOutOfBoundsException nếu index đã cho ở bên ngoài dãy (index < 0 || index >= size()) |
| Object remove(int index) | Gỡ bỏ phần tử tại vị trí đã cho. Ném NoSuchElementException nếu list này là trống |
| boolean remove(Object o) | Gỡ bỏ sự xuất hiện đầu tiên của phần tử đã cho. Ném NoSuchElementException nếu list này trống. Ném IndexOutOfBoundsException nếu index ở bên ngoài dãy (index < 0 || index >= size()) |
| Object removeFirst() | Gỡ bỏ và trả về phần tử đầu tiên từ list này. Ném NoSuchElementException nếu list là trống |
| Object removeLast() | Gỡ bỏ và trả về phần tử cuối từ list này. Ném NoSuchElementException nếu list là trống |
| Object set(int index, Object element) | Thay thế phần tử tại vị trí đã cho trong list này với phần tử đã cho. Ném IndexOutOfBoundsException nếu index đã cho ở ngoài dãy (index < 0 || index >= size()) |
| int size() | Trả về số phần tử trong list này |
| Object[] toArray() | Trả về một mảng chứa tất cả phần tử trong list này trong đúng thứ tự. Ném NullPointerException nếu mảng đã xác định là null |
| Object[] toArray(Object[] a) | Trả về một mảng chứa tất cả phần tử trong list này trong đúng thứ tự; kiểu runtime của mảng trả về là như của mảng đã xác định |
Mình sẽ đi vào ví dụ cho dễ hiểu nhé.
Ví dụ về việc khởi tạo 1 LinkedList có kiểu dữ liệu là String, sau đó sẽ add các phần tử vào LinkedList.
Tạo 1 LinkedList có kiểu dữ liệu là Student.
Như các bạn thấy thì LinkedList cũng có thể lưu phần tử trùng nhau và cả phần tử null.
Vì đều là thể hiện của List Interface nên các phương thức thao tác cũng gần như ArrayList mình đã giới thiệu ở bài trước, mình sẽ không đi demo hết các phương thức nữa. Các bạn có thể thử, sẽ dễ nhớ và hiểu hơn. Nếu lỗi thì cứ comment ở dưới mình sẽ giải đáp.
Vậy sau khi học qua ArrayList và LinkedList thì các bạn rút ra được những gì. Mình sẽ tổng hợp lại ở bảng bên dưới để các bạn có cái nhìn tổng quan hơn về ArrayList và LinkedList. Từ đó có thể sử dụng để giải các bài toán phù hợp.
| ArrayList | LinkedList | |
| ArrayList sử dụng mảng động để lưu trữ các phần tử | LinkedList sử dụng danh sách liên kết (Doubly Linked List) để lưu trữ các phần tử. | |
| Cấu trúc dữ liệu (Structure) | ArrayList là một cấu trúc dữ liệu dựa trên chỉ mục (index), trong đó mỗi phần tử (element) được liên kết với một chỉ mục | Các phần tử trong LinkedList được gọi là node, mỗi node cần lưu trữ 3 thông tin: tham chiếu phần tử trước nó, giá trị của phần tử và một tham chiếu tới phần tử kế tiếp. |
| Thao tác thêm và xóa (Insertion And Removal) | Thao tác thêm và xóa phần tử với ArrayList là chậm bởi vì nó sử dụng nội bộ mảng. Bởi vì sau khi thêm hoặc xóa các phần tử cần sắp xếp lại. | Thao tác thêm và xóa phần tử với LinkedList nhanh hơn ArrayList. Bởi vì nó không cần sắp xếp lại các phần tử sau khi thêm hoặc xóa. Nó chỉ cần cập nhật lại tham chiếu tới phần tử phía trước và sau nó |
| Độ phức tạp: O(n). | Độ phức tạp: O(1). | |
| Thao tác tìm kiếm hoặc truy xuất phần tử (Retrieval) | Truy xuất phần tử trong ArrayList nhanh hơn LinkedList. Bởi vì các phần tử trong ArrayList được lưu trữ dựa trên chỉ mục (index). | Thao tác truy xuất phần tử trong LinkedList chậm hơn nhiều so với ArrayList. Bởi vì, nó phải duyệt qua lần lượt các phần tử từ đầu tiên cho đến cuối cùng. |
| Độ phức tạp: O(1). | Độ phức tạp: O(n). | |
| Truy xuất ngẫu nhiên (Random Access) | ArrayList có thể truy xuất ngẫu nhiên phần tử. | LinkedList không thể truy xuất ngẫu nhiên. Nó phải duyệt qua tất cả các phần tử từ đầu tiên đến phần tử cuối cùng để tìm phần tử. |
| Trường hợp sử dụng (Usage) | ArrayList chỉ có thể hoạt động như một list vì nó chỉ implements giao tiếp List. | LinkedList có thể hoạt động như một ArrayList, stack (hàng đợi), queue (hàng đợi), Singly Linked List and Doubly Linked List vì nó implements các giao tiếp List và Deque. |
| Sử dụng bộ nhớ | ArrayList yêu cầu ít bộ nhớ hơnso với LinkedList. Bởi vì ArrayList chỉ lưu trữ dữ liệu (data) của nó và chỉ mục (index). | LinkedList yêu cầu nhiều bộ nhớ hơn so với ArrayList. Bởi vì LinkedList lưu giữ thông tin của nó và tham chiếu tới phần tử trước và sau nó. |
Kết luận.
ArrayList tốt hơn trong việc lưu trữ và truy xuất dữ liệu (get).
LinkedList tốt hơn trong việc thao tác dữ liệu (thêm/ xóa).
Cảm ơn các bạn đã đọc blog của mình, nếu thấy hay thì hãy chia sẻ cho mọi người biết hoặc để lại vài lời nhận xét nhé. Đó sẽ là động lực để mình làm các bài viết sau hay hơn.
Đào Văn Đô 
One thought on “LinkedList trong java collection.”