Linked List
1. Giới thiệu
Linked List là một phần của Collection Framework có trong gói java.util. Lớp này là một triển khai của cấu trúc dữ liệu tuyến tính trong đó các phần tử không được lưu trữ ở các vị trí liền kề mà mỗi phần tử là một đối tượng riêng biệt bao gồm dữ liệu và địa chỉ. Các phần tử được liên kết bằng cách sử dụng con trỏ và địa chỉ. Mỗi phần tử được gọi là một nút. Do tính linh động, dễ dàng chèn và xóa nên chúng được ưu tiên hơn các mảng. Linked List cũng có một số nhược điểm như không thể truy cập trực tiếp các nút thay vào đó chúng ta cần bắt đầu từ phần đầu và đi theo liên kết để đến được nút mà chúng ta muốn truy cập.
Ví dụ sau làm rõ về việc tạo và sử dụng Linked List
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.LinkedList;
public class TestLinkedList {
public static void main(String args[]) {
// Tạo đối tượng của danh sách liên kết
LinkedList<String> ll = new LinkedList<String>();
// Thêm các phần tử vào Linked List
ll.add("A");
ll.add("B");
ll.addLast("C");
ll.addFirst("D");
ll.add(2, "E");
System.out.println(ll);
ll.remove("B");
ll.remove(3);
ll.removeFirst();
ll.removeLast();
System.out.println(ll);
}
}
LinkedList hoạt động như thế nào?
Vì LinkedList hoạt động như một mảng động và chúng ta không phải chỉ định kích thước trong khi tạo nó, nên kích thước của danh sách sẽ tự động tăng khi chúng ta thêm và xóa động các mục.
Ngoài ra, các phần tử không được lưu trữ theo kiểu liên tục. Do đó, không cần thiết phải tăng kích thước. LinkedList được triển khai bằng cách sử dụng cấu trúc dữ liệu danh sách được liên kết kép. Sự khác biệt chính giữa danh sách liên kết bình thường và danh sách liên kết kép là danh sách được liên kết kép chứa một con trỏ phụ, thường được gọi là con trỏ trước, cùng với con trỏ tiếp theo và dữ liệu có trong danh sách được liên kết đơn lẻ.
2. Các thao tác với LinkedList
1-Thêm phần tử
Để thêm phần tử vào ArrayList, chúng ta có thể sử dụng phương thức add(). Phương thức này được nạp chồng để thực hiện nhiều hoạt động dựa trên các tham số khác nhau. Bao gồm:
- add (Object): Phương thức này được sử dụng để thêm một phần tử vào cuối LinkedList.
- add (int index, Object): Phương thức này được sử dụng để thêm một phần tử tại một chỉ mục cụ thể trong LinkedList.
1
2
3
4
5
6
7
8
9
10
11
12
13
import java.util.LinkedList;
public class AddMethod {
public static void main(String args[]) {
LinkedList<String> ll = new LinkedList<>();
ll.add("Michael");
ll.add("Corleone");
ll.add(1, "Jr.");
System.out.println(ll);
}
}
2-Thay đổi phần tử
Sau khi thêm phần tử, nếu chúng ta muốn thay đổi nó thì có thể được thực hiện bằng cách sử dụng phương thức set(). Vì LinkedList được thiết lập dựa trên chỉ mục nên phần tử mà ta muốn thay đổi sẽ được tham chiếu bởi chỉ mục của phần tử đó. Do vậy, phương thức này lấy một chỉ mục và phần tử cập nhật cần được chèn vào chỉ mục đó.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.LinkedList;
public class ChangingElements {
public static void main(String args[]) {
LinkedList<String> ll = new LinkedList<>();
ll.add("Michael");
ll.add("Corleone");
ll.add(1, "TheGodFather");
System.out.println("LinkedList ban đầu " + ll);
ll.set(1, "Jackson");
System.out.println("LinkedList sau cập nhật " + ll);
}
}
3-Loại bỏ phần tử
Để loại bỏ một phần tử khỏi LinkedList, chúng ta có thể sử dụng phương thức remove(). Phương thức này được nạp chồng để thực hiện nhiều hoạt động dựa trên các tham số khác nhau. Bao gồm:
- remove(Object): Phương thức này được sử dụng để loại bỏ một đối tượng khỏi LinkedList. Nếu có nhiều đối tượng như vậy, thì lần xuất hiện đầu tiên của đối tượng sẽ bị loại bỏ.
- remove(int index): Vì LinkedList được thiết lập dựa trên chỉ mục nên phương thức này nhận một giá trị số nguyên, chỉ cần loại bỏ phần tử hiện diện tại chỉ mục cụ thể đó trong LinkedList. Sau khi loại bỏ phần tử, tất cả các phần tử được chuyển sang bên trái để lấp đầy khoảng trống và chỉ số của các đối tượng được cập nhật.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.LinkedList;
public class RemovingElements {
public static void main(String args[]) {
LinkedList<String> ll = new LinkedList<>();
ll.add("Michael");
ll.add("TheGodFather");
ll.add(1, "Corleone");
System.out.println("LinkedList ban đầu " + ll);
ll.remove(1);
System.out.println("Sau khi loại bỏ chỉ mục " + ll);
ll.remove("Michael");
System.out.println("Sau khi loại bỏ đối tượng " + ll);
}
}
4-Lặp lại LinkedList
Có nhiều cách để lặp lại LinkedList. Các cách nổi tiếng nhất là sử dụng vòng lặp FOR cơ bản kết hợp với phương thức get() để lấy phần tử tại một chỉ mục cụ thể và vòng lặp FOR nâng cao.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.LinkedList;
public class IteratingLinkedList {
public static void main(String args[]) {
LinkedList<String> ll = new LinkedList<>();
ll.add("Michael");
ll.add("TheGodFather");
ll.add(1, "Corleone");
// Sử dụng phương thức GET và vòng lặp
for (int i = 0; i < ll.size(); i++) {
System.out.print(ll.get(i) + " ");
}
System.out.println();
// Sử dụng vòng lặp FOR-EACH
for (String str : ll)
System.out.print(str + " ");
}
}
Trong hình minh dưới đây, AbstractList, CopyOnWriteArrayList và AbstractSequentialList là các lớp implement (triển khai) các list interface. Mỗi lớp có một chức năng riêng biệt, cụ thể như sau:
- AbstractList: Lớp này được sử dụng để implement một danh sách cố định – do đó cần mở rộng lớp AbstractList và chỉ implementcác phương thức
get()vàsize(). - CopyOnWriteArrayList: Lớp này implements các list interface.. Đây là phiên bản nâng cao của ArrayList trong đó tất cả các sửa đổi (thêm, đặt, xóa, v.v.) được thực hiện bằng cách tạo một bản sao mới của danh sách.
- AbstractSequentialList: Lớp này implements các
Collection interfacevà các lớpAbstractCollection. Lớp này được sử dụng để implement một danh sách cố định – do đó cần mở rộng lớp AbstractList và chỉ implement các phương thứcget()vàsize().
3. Hàm xây dựng trong LinkedList
Để tạo một LinkedList, chúng ta cần tạo một đối tượng của lớp LinkedList. Lớp LinkedList bao gồm các hàm xây dựng khác nhau cho phép tạo danh sách. Sau đây là các hàm xây dựng có sẵn trong lớp này:
LinkedList(): Hàm xây dựng này được sử dụng để tạo một danh sách liên kết trống. Nếu chúng ta muốn tạo một LinkedList trống với tên linkedList, thì nó có thể được tạo như sau:
1
LinkedList linkedList = new LinkedList();
LinkedList(Collection C): Hàm xây dựng này được sử dụng để tạo một danh sách có thứ tự chứa tất cả các phần tử của một Collection. Nếu chúng ta muốn tạo một danh sách liên kết với tên linkedList, thì nó có thể được tạo như sau:
1
LinkedList linkedList = new LinkedList(C);
4. Các hàm/phương thức của Java Linked List
- add(E e): Phương thức này Thêm phần tử được chỉ định vào cuối danh sách.
- add(int index, E element): Phương thức này Chèn phần tử được chỉ định vào vị trí đã chỉ định trong danh sách.
Phương thức này chấp nhận hai tham số:
- index: Chỉ mục mà tại đó phần tử được chỉ định sẽ được chèn vào.
- element: Phần tử cần được chèn vào.
- Phương thức này không trả về bất kỳ giá trị nào.
Ví dụ 1: (Không index)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.LinkedList;
public class PhuongThucAdd {
public static void main(String args[]) {
// khởi tạo Linked List rỗng
LinkedList list = new LinkedList();
// sử dụng phương thức add() method để thêm phần tử vào danh sách
list.add("Michael");
list.add("Corleone");
list.add("TheGodfather");
list.add("Mario");
list.add("Puzo");
// In danh sách hiệ tại
System.out.println("Danh sách hiện tại:" + list);
// Thêm các phần tử mới vào cuối danh sách
list.add("Last");
list.add("Element");
// In danh sách mới
System.out.println("Danh sách mới:" + list);
}
}
Ví dụ 2: (Có index)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.LinkedList;
public class PhuongThucAdd2 {
public static void main(String args[]) {
// khởi tạo Linked List rỗng
LinkedList<String> list = new LinkedList<String>();
// sử dụng phương thức add() method để thêm phần tử vào danh sách
list.add("Michael");
list.add("Corleone");
list.add("TheGodfather");
list.add("Mario");
list.add("Puzo");
// In danh sách hiệ tại
System.out.println("Danh sách hiện tại:" + list);
// Adding new elements to the end
list.add(2, "Hello");
list.add(4, "End");
// In danh sách mới
System.out.println("Danh sách mới:" + list);
}
}
**addAll(Collection
**addAll(int index, Collection
Trong đó:
- C: là một tập hợp các ArrayList. Đây là tập hợp có các phần tử cần được thêm vào ở cuối danh sách.
- index: Tham số này có kiểu dữ liệu số nguyên và chỉ định vị trí trong danh sách bắt đầu từ nơi các phần tử từ vùng chứa sẽ được chèn vào.
- Phương thức trả về true nếu ít nhất một hành động “treo cờ” được thực hiện.
Ví dụ 1: (Không index)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedList;
public class PhuongThucAddAll {
public static void main(String args[]) {
// Tạo Linked List rỗng
LinkedList<String> list = new LinkedList<String>();
// Sử dụng phương thức add để thêm phần tử vào danh sách
list.add("Michael");
list.add("Corleone");
list.add("TheGodfather");
list.add("Mario");
list.add("Puzo");
// Một collection được tạo
Collection<String> collect = new ArrayList<String>();
collect.add("This");
collect.add("is");
collect.add("my");
collect.add("favorite");
collect.add("book");
// In danh sách
System.out.println("The LinkedList is: " + list);
// Thêm collection vào danh sách
list.addAll(collect);
// In danh sách mới
System.out.println("The new linked list is: " + list);
}
}
Ví dụ 2: (Có index)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedList;
public class PhuongThucAddAll2 {
public static void main(String args[]) {
// Tạo Linked List rỗng
LinkedList<String> list = new LinkedList<String>();
// Sử dụng phương thức add để thêm phần tử vào danh sách
list.add("Michael");
list.add("Corleone");
list.add("TheGodfather");
list.add("Mario");
list.add("Puzo");
// Một collection được tạo
Collection<String> collect = new ArrayList<String>();
collect.add("This");
collect.add("is");
collect.add("my");
collect.add("favorite");
collect.add("book");
// In danh sách
System.out.println("The LinkedList is: " + list);
// Thêm collection vào danh sách
list.addAll(1, collect);
// In danh sách mới
System.out.println("The new linked list is: " + list);
}
}
addFirst(E e): Phương thức này dùng để chèn phần tử được chỉ định vào đầu danh sách.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.LinkedList;
public class PhuongThucAddFirst {
public static void main(String args[]) {
// Tạo Linked List rỗng
LinkedList<String> list = new LinkedList<String>();
// sử dụng phương thức add() để thêm phần tử vào danh sách
list.add("Michael");
list.add("Corleone");
list.add("TheGodfather");
list.add("Mario");
list.add("Puzo");
// In danh sách hiện tại
System.out.println("The list is:" + list);
// Thêm các phần tử ở đầu
list.addFirst("First");
list.addFirst("At");
// Danh sách sau khi thêm
System.out.println("The new List is:" + list);
}
}
addLast(E e): Phương thức này Thêm phần tử được chỉ định vào cuối danh sách
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.LinkedList;
public class PhuongThucAddLast {
public static void main(String args[]) {
// Tạo Linked List rỗng
LinkedList<String> list = new LinkedList<String>();
// sử dụng phương thức add() để thêm phần tử vào danh sách
list.add("Michael");
list.add("Corleone");
list.add("TheGodfather");
list.add("Mario");
list.add("Puzo");
// In danh sách hiện tại
System.out.println("The list is:" + list);
// Thêm các phần tử vào cuối sử dụng addLast()
list.addLast("At");
list.addLast("Last");
// In danh sách mới
System.out.println("The new List is:" + list);
}
}
clear(): Phương pháp này xóa tất cả các phần tử khỏi danh sách.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import java.util.LinkedList;
public class PhuongThucClear {
public static void main(String args[]) {
// Tạo một LinkedList rỗng
LinkedList<String> list = new LinkedList<String>();
// Using add() method to add elements in the list
list.add("Michael");
list.add("Corleone");
list.add("TheGodfather");
list.add("Mario");
list.add("Puzo");
// In danh sách ban đầu
System.out.println("Original LinkedList:" + list);
// Thực hiện xoá danh sách
list.clear();
// Truy cập danh sách sau khi xoá
System.out.println("List after clearing all elements: " + list);
// Thêm lại các phần tử mới
list.add("Vito");
list.add("Sony");
list.add("Tom");
// In danh sách mới nhất
System.out.println("After adding elements to empty list:" + list);
}
}
clone(): Phương thức này trả về một bản sao chép cạn của LinkedList.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.LinkedList;
public class PhuongThucClone {
public static void main(String args[]) {
// Tạo Linked List rỗng
LinkedList<String> list = new LinkedList<String>();
// sử dụng phương thức add() để thêm phần tử vào danh sách
list.add("Michael");
list.add("Corleone");
list.add("TheGodfather");
list.add("Mario");
list.add("Puzo");
// In danh sách hiện tại
System.out.println("The list is:" + list);
// Tạo Linked List khác để thực hiện copy
LinkedList second_list = new LinkedList();
second_list = (LinkedList) list.clone();
// Danh sách sao chép được
System.out.println("Second LinkedList is:" + second_list);
}
}
contains(Object o): Phương thức này trả về true nếu danh sách chứa phần tử được chỉ định.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.LinkedList;
public class PhuongThucContains {
public static void main(String args[]) {
// Tạo Linked List rỗng
LinkedList<String> list = new LinkedList<String>();
// sử dụng phương thức add() để thêm phần tử vào danh sách
list.add("Michael");
list.add("Corleone");
list.add("TheGodfather");
list.add("Mario");
list.add("Puzo");
// In danh sách
System.out.println("LinkedList:" + list);
// Kiểm tra xem danh sách có chứa "Michael" không ?
System.out.println("\nDoes the List contains 'Michael': " + list.contains("Michael"));
// Kiểm tra xem danh sách có chứa "Steve Jobs" không ?
System.out.println("Does the List contains 'Steve Jobs': " + list.contains("Steve Jobs"));
// Kiểm tra xem danh sách có chứa "99" không ?
System.out.println("Does the List contains '99': " + list.contains("99"));
}
}
descendingIterator(): Phương thức này trả về các giá trị theo chiều ngược lại của danh sách một cách có thứ tự.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.util.*;
public class PhuongThucDescendingIterator {
public static void main(String[] argv) throws Exception {
try {
// tạo đối tượng TreeMap<Integer, String>
LinkedList<String> list = new LinkedList<String>();
// thêm phần tử vào danh sách
list.add("A");
list.add("B");
list.add("C");
// In danh sách
System.out.println("LinkedList:" + list);
// thiết lặp các Iterator giảm dần sử dụng descendingIterator()
Iterator x = list.descendingIterator();
//In danh sách với thứ tự giảm dần
while (x.hasNext()) {
System.out.println("Value is : " + x.next());
}
}
catch (NullPointerException e) {
System.out.println("Exception thrown : " + e);
}
}
}
get(int index): Phương thức này trả về phần tử ở vị trí được chỉ định trong danh sách.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.LinkedList;
public class PhuongThucGet {
public static void main(String args[]) {
// Tạo một LinkedList rỗng
LinkedList<String> list = new LinkedList<String>();
// sử dụng phương thức add() để thêm phần tử vào danh sách
list.add("Michael");
list.add("Corleone");
list.add("TheGodfather");
list.add("Mario");
list.add("Puzo");
// In danh sách
System.out.println("LinkedList:" + list);
// Tìm phần tử theo chỉ mục được chỉ định
System.out.println("The element is: " + list.get(3));
}
}
getFirst(): Phương thức này trả về phần tử đầu tiên trong danh sách.
getLast(): Phương thức này trả về phần tử cuối cùng trong danh sách.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.LinkedList;
public class PhuongThucGetFirstLast {
public static void main(String[] args) {
// Tạo một LinkedList rỗng
LinkedList<String> list = new LinkedList<String>();
// sử dụng phương thức add() để thêm phần tử vào danh sách
list.add("Michael");
list.add("Corleone");
list.add("TheGodfather");
list.add("Mario");
list.add("Puzo");
// In danh sách hiện tại
System.out.println("The elements in List are : " + list);
// Sử dụng Get để in phần tử đầu và cuối
System.out.println("Element at 1st index is : " + list.getFirst());
System.out.println("Element at last index is : " + list.getLast());
}
}
indexOf(Object o): Phương thức này trả về chỉ số của lần xuất hiện đầu tiên của phần tử được chỉ định trong danh sách này hoặc -1 nếu danh sách này không chứa phần tử.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.LinkedList;
public class PhuongThucIndexOf {
public static void main(String args[]) {
// Tạo một LinkedList rỗng
LinkedList<String> list = new LinkedList<String>();
// sử dụng phương thức add() để thêm phần tử vào danh sách
list.add("Michael");
list.add("Corleone");
list.add("TheGodfather");
list.add("Vito");
list.add("Corleone");
// In danh sách hiện tại
System.out.println("The elements in List are : " + list);
// Vị trị đầu tiên của phần từ
System.out.println("The first occurrence of Corleone is at index:" + list.indexOf("Corleone"));
System.out.println("The first occurrence of Vito is at index: " + list.indexOf("Vito"));
}
}
lastIndexOf(Object o): Phương thức này trả về chỉ mục của lần xuất hiện cuối cùng của phần tử được chỉ định trong danh sách này hoặc -1 nếu danh sách này không chứa phần tử.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.LinkedList;
public class PhuongThucLastIndexOf {
public static void main(String args[]) {
// Tạo một LinkedList rỗng
LinkedList<String> list = new LinkedList<String>();
// sử dụng phương thức add() để thêm phần tử vào danh sách
list.add("Michael");
list.add("Corleone");
list.add("TheGodfather");
list.add("Vito");
list.add("Corleone");
// In danh sách hiện tại
System.out.println("The elements in List are : " + list);
// Vị trị đầu tiên của phần từ
System.out.println("The first occurrence of Corleone is at index:" + list.lastIndexOf("Corleone"));
System.out.println("The first occurrence of Vito is at index: " + list.lastIndexOf("Vito"));
}
}
listIterator(int index): Phương thức này trả về ListIterator của các phần tử trong danh sách (theo trình tự thích hợp), bắt đầu từ vị trí đã chỉ định trong danh sách.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.LinkedList;
import java.util.ListIterator;
public class PhuongThucListIterator {
public static void main(String args[]) {
// Tạo một LinkedList rỗng
LinkedList<String> list = new LinkedList<String>();
// sử dụng phương thức add() để thêm phần tử vào danh sách
list.add("Michael");
list.add("Corleone");
list.add("TheGodfather");
list.add("Vito");
list.add("Corleone");
// In danh sách hiện tại
System.out.println("The elements in List are : " + list);
// thiết lập ListIterator ở vị trí chỉ định
ListIterator<String> list_Iter = list.listIterator(2);
// Lặp lại danh sách đã tạo từ vị trí chỉ định
System.out.println("The list is as follows:");
while (list_Iter.hasNext()) {
System.out.println(list_Iter.next());
}
}
}
offer(E e): Phương thức này Thêm phần tử được chỉ định làm phần đuôi (phần tử cuối cùng) của danh sách.
offerFirst(E e): Phương thức này Chèn phần tử được chỉ định ở đầu danh sách.
offerLast(E e): Phương thức này Chèn phần tử được chỉ định ở cuối danh sách.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.LinkedList;
public class PhuongThucOffer {
public static void main(String[] args) {
// Tạo một LinkedList rỗng
LinkedList<String> list = new LinkedList<String>();
// sử dụng phương thức add() để thêm phần tử vào danh sách
list.add("Michael");
list.add("Corleone");
list.add("TheGodfather");
list.add("Vito");
list.add("Corleone");
// In danh sách hiện tại
System.out.println("The elements in List are : " + list);
// thêm phần tử mới
list.offer("Tom-Hagen");
list.offerFirst("Sony");
list.offerLast("Feric");
// In danh sách mới
System.out.println("LinkedList after insertion using offer() : " + list);
}
}
peek(): Phương thức này truy xuất, nhưng không loại bỏ phần đầu (phần tử đầu tiên) của danh sách.
peekFirst(): Phương thức này truy xuất, nhưng không loại bỏ phần tử đầu tiên của danh sách hoặc trả về null nếu danh sách này trống.
peekLast(): Phương thức này truy xuất, nhưng không loại bỏ phần tử cuối cùng của danh sách hoặc trả về null nếu danh sách này trống.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.LinkedList;
public class PhuongThucPeek {
public static void main(String[] args) {
// Tạo một LinkedList rỗng
LinkedList<String> list = new LinkedList<String>();
// sử dụng phương thức add() để thêm phần tử vào danh sách
list.add("Michael");
list.add("Corleone");
list.add("TheGodfather");
list.add("Vito");
list.add("Corleone");
// In danh sách hiện tại
System.out.println("The elements in List are : " + list);
// peek ở đầu danh sách
System.out.println("Head of the list : " + list.peek());
// peek phần tử đầu tiên của danh sách
System.out.println("First element of the list is : " + list.peekFirst());
// peek phần tử cuối của danh sách
System.out.println("Last element of the list is : " + list.peekLast());
}
}
poll(): Phương thức này truy xuất và loại bỏ phần đầu (phần tử đầu tiên) của danh sách.
pollFirst(): Phương thức này truy xuất và loại bỏ phần tử đầu tiên của danh sách hoặc trả về null nếu danh sách này trống.
pollLast(): Phương thức này truy xuất và loại bỏ phần tử cuối cùng của danh sách hoặc trả về null nếu danh sách này trống.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.LinkedList;
public class PhuongThucPoll {
public static void main(String[] args) {
// Tạo một LinkedList rỗng
LinkedList<String> list = new LinkedList<String>();
// sử dụng phương thức add() để thêm phần tử vào danh sách
list.add("Michael");
list.add("Corleone");
list.add("TheGodfather");
list.add("Vito");
list.add("Corleone");
// In danh sách hiện tại
System.out.println("The elements in List are : " + list);
// peek ở đầu danh sách
System.out.println("Head of the list : " + list.poll());
// peek phần tử đầu tiên của danh sách
System.out.println("First element of the list is : " + list.pollFirst());
// peek phần tử cuối của danh sách
System.out.println("Last element of the list is : " + list.pollLast());
}
}
pop(): Phương thức này được dùng lấy (Kéo ra) một phần tử ở đầu ngăn xếp stack. push(): Phương thức này thêm (Đẩy) một phần tử vào đầu ngăn xếp Stack.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.LinkedList;
public class PhuongThucPushPop {
public static void main(String[] args) {
// Tạo một đối tượng LinkedList đại diện cho một ngăn xếp
LinkedList<String> stack = new LinkedList<>();
// Push phần tử vào Stack
stack.push("Michael");
stack.push("Corleone");
// Pop phần tử ra khỏi danh sách
String s = stack.pop();
// in phần tử đã Pop
System.out.println(s);
// Push phần tử vào Stack
stack.push("TheGodfather");
// In stack
System.out.println(stack);
}
}
remove(): Phương thức này truy xuất và loại bỏ phần đầu (phần tử đầu tiên) của danh sách.
remove(int index): Phương thức này loại bỏ phần tử tại vị trí được chỉ định trong danh sách.
remove(Object o): Phương thức này xóa lần xuất hiện đầu tiên của phần tử được chỉ định khỏi danh sách, nếu nó có mặt.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.LinkedList;
public class PhuongThucRemove {
public static void main(String args[]) {
// Tạo một LinkedList rỗng
LinkedList<String> list = new LinkedList<String>();
// sử dụng phương thức add() để thêm phần tử vào danh sách
list.add("Michael");
list.add("Corleone");
list.add("TheGodfather");
list.add("Vito");
list.add("Corleone");
// In danh sách hiện tại
System.out.println("The elements in List are : " + list);
// Xoá phần tử đầu sử dụng remove()
list.remove();
// Xoá phần tử tại index thứ 3
list.remove(3);
// Xoá phần tử theo Object
list.remove("Vito");
// In danh sách
System.out.println("Final LinkedList:" + list);
}
}
removeFirst(): Phương thức này loại bỏ và trả về phần tử đầu tiên từ danh sách.
removeLast(): Phương thức này loại bỏ và trả về phần tử cuối cùng từ danh sách.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.LinkedList;
public class PhuongThucRemoveFirstLast {
public static void main(String args[]) {
// Tạo một LinkedList rỗng
LinkedList<String> list = new LinkedList<String>();
// sử dụng phương thức add() để thêm phần tử vào danh sách
list.add("Michael");
list.add("Corleone");
list.add("TheGodfather");
list.add("Vito");
list.add("Corleone");
// In danh sách hiện tại
System.out.println("The elements in List are : " + list);
// Xoá phần tử đầu sử dụng removeFirst()
System.out.println("The first element is: " + list.removeFirst());
// In danh sách
System.out.println("The elements in List are:" + list);
// Xoá phần tử cuối sử dụng removeLast()
System.out.println("The last element is removed: " + list.removeLast());
// In danh sách
System.out.println("Final LinkedList:" + list);
}
}
removeFirstOccurrence(Object o): Phương thức này loại bỏ sự xuất hiện đầu tiên của phần tử được chỉ định trong danh sách (khi duyệt qua danh sách từ đầu đến đuôi).
removeLastOccurrence(Object o): Phương thức này loại bỏ lần xuất hiện cuối cùng của phần tử được chỉ định trong danh sách (khi duyệt qua danh sách từ đầu đến đuôi).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.LinkedList;
public class PhuongThucRemoveLFirstLastOccurrence {
public static void main(String args[]) {
// Tạo một LinkedList rỗng
LinkedList<String> list = new LinkedList<String>();
// sử dụng phương thức add() để thêm phần tử vào danh sách
list.add("Michael");
list.add("Corleone");
list.add("TheGodfather");
list.add("Vito");
list.add("Corleone");
// In danh sách hiện tại
System.out.println("The elements in List are : " + list);
// Xoá phần tử xuất hiện đầu tiên
list.removeFirstOccurrence("Corleone");
// Danh sách sau khi removeFirstOccurrence
System.out.println("LinkedList removeFirstOccurrence: " + list);
// Xoá phần tử xuất hiện cuối cùng
list.removeLastOccurrence("Vito");
// Danh sách sau khi removeLastOccurrence
System.out.println("LinkedList removeLastOccurrence: " + list);
}
}
set(int index, E element): Phương thức này thay thế phần tử ở vị trí được chỉ định trong danh sách bằng phần tử được chỉ định.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.LinkedList;
public class PhuongThucSet {
public static void main(String args[]) {
// Tạo một LinkedList rỗng
LinkedList<String> list = new LinkedList<String>();
// sử dụng phương thức add() để thêm phần tử vào danh sách
list.add("Michael");
list.add("Corleone");
list.add("TheGodfather");
list.add("Vito");
list.add("Corleone");
// In danh sách hiện tại
System.out.println("The elements in List are : " + list);
// Sử dụng set() để thay thế Vito với Sony
System.out.println("The Object that is replaced is: " + list.set(3, "Sony"));
// Sử dụng set() để thay thế TheGodfather với MarioPuzo
System.out.println("The Object that is replaced is: " + list.set(2, "MarioPuzo"));
// In danh sách mới
System.out.println("The new LinkedList is:" + list);
}
}
size(): Phương thức này trả về số phần tử trong danh sách.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.LinkedList;
public class PhuongThucSize {
public static void main(String args[]) {
// Tạo một LinkedList rỗng
LinkedList<String> list = new LinkedList<String>();
// sử dụng phương thức add() để thêm phần tử vào danh sách
list.add("Michael");
list.add("Corleone");
list.add("TheGodfather");
list.add("Vito");
list.add("Corleone");
// In danh sách hiện tại
System.out.println("The elements in List are : " + list);
// Kích thước của danh sách
System.out.println("The size of the linked list is: " + list.size());
}
}
spliterator(): Phương pháp này tạo một Spliterator “ràng buộc” trên các phần tử trong danh sách.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import java.util.LinkedList;
import java.util.Spliterator;
public class PhuongThucSpliterator {
public static void main(String[] args) {
// Tạo LinkedList chứa danh sách các số
LinkedList<Shape> shapes = new LinkedList<Shape>();
// Thêm các hình khác nhau vào Linkedlist
shapes.add(new Shape("Circle", 239));
shapes.add(new Shape("Square", 368));
shapes.add(new Shape("Cone", 379));
shapes.add(new Shape("Rectangle", 888));
// Sử dụng spliterator() tạo Spliterator cho LinkedList
Spliterator<Shape> spliter = shapes.spliterator();
// In kết quả từ Spliterator
System.out.println("List of Shapes:");
// Phương thức forEachRemaining của Spliterator
spliter.forEachRemaining((Value) -> printDetails(Value));
}
// In chi tiết
public static void printDetails(Shape s) {
System.out.println("************************");
System.out.println("Shape Name : " + s.shapename);
System.out.println("Shape Area : " + s.area);
}
}
// Tạo lớp Shape
class Shape {
// Lớp shape có 2 thuộc tính
String shapename;
int area;
public Shape(String shapename, int area) {
super();
this.shapename = shapename;
this.area = area;
}
}
toString(): Phương thức này trả về một Chuỗi chứa tất cả các phần tử trong danh sách theo thứ tự thích hợp (từ phần tử đầu tiên đến phần tử cuối cùng), mỗi phần tử được phân tách bằng dấu phẩy và Chuỗi được đặt trong dấu ngoặc vuông.
toArray(): Phương thức này trả về một mảng chứa tất cả các phần tử trong danh sách theo thứ tự thích hợp (từ phần tử đầu tiên đến phần tử cuối cùng).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.Arrays;
import java.util.LinkedList;
public class PhuongThucToArray1 {
public static void main(String[] args) throws IllegalStateException {
// Tạo đối tượng LinkedList
LinkedList<Integer> list = new LinkedList<Integer>();
// Thêm dữ liệu số vào LinkedList
list.add(7855642);
list.add(35658786);
list.add(5278367);
list.add(74381793);
// In danh sách
System.out.println("LinkedList: " + list);
Object[] a = list.toArray();
// Mảng trả về
System.out.println("Returned Array: " + Arrays.toString(a));
}
}
toArray(T[] a): Phương thức này trả về một mảng chứa tất cả các phần tử trong danh sách theo thứ tự thích hợp (từ phần tử đầu tiên đến phần tử cuối cùng); kiểu thời gian chạy của mảng được trả về là kiểu của mảng được chỉ định.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.Arrays;
import java.util.LinkedList;
public class PhuongThucToArray2 {
public static void main(String args[]) {
// Tạo một LinkedList rỗng
LinkedList<String> list = new LinkedList<String>();
// sử dụng phương thức add() để thêm phần tử vào danh sách
list.add("Michael");
list.add("Corleone");
list.add("TheGodfather");
list.add("Vito");
list.add("Corleone");
// In danh sách hiện tại
System.out.println("The elements in List are : " + list);
String[] arr = new String[5];
arr = list.toArray(arr);
// Mảng trả về
System.out.println("Returned Array: " + Arrays.toString(arr));
}
}
Túm lại, Những điểm cần ghi nhớ về lớp LinkedList:
- Có thể chứa các phần tử trùng lặp.
- Duy trì thứ tự của phần tử được thêm vào.
- Không đồng bộ (non-synchronized).
- Thao tác thêm/ xóa (add/ remove) phần tử nhanh vì không cần phải dịch chuyển nếu bất kỳ phần tử nào thêm/ xoá khỏi danh sách.
- LinkedList có thể được sử dụng như danh sách (list), stack (ngăn xếp) hoặc queue (hàng đợi).
- Các phần tử trong LinkedList có thể nằm cách ly nhau (không liên tục) trong bộ nhớ. Nó là một liên kết có tính hai chiều giữa các phần tử. Mỗi phần tử trong danh sách cầm giữ một tham chiếu đến đối phần tử đằng trước nó và tham chiếu đến phần tử ngay sau nó.
Này, bạn đừng choáng ngợp trước số lượng các hàm và phương thức đồ sộ mà Linked List cung cấp nhé – Hãy luyện tập cho thao tác được nhuần nhuyễn và tư duy thêm nhạy bén để áp dụng các kiến thức được mình chia sẻ bên trên đúng nơi – đúng thời điểm mới không uổng công lao mà chúng ta đã bỏ ra. Sao rồi? Bạn thấy Linked List so với Array thế nào? Hãy tự vấn mình và rút ra các khác biệt nhé.
Bài viết mang tính chất “ghi chú, lưu trữ, chia sẻ và phi lợi nhuận”.
Nếu bạn thấy hữu ích, đừng quên chia sẻ với bạn bè và đồng nghiệp của mình nhé!
Happy coding! 😎 👍🏻 🚀 🔥