Giới thiệu về cách sử dụng danh sách được liên kết trong Java

Giới thiệu về cách sử dụng danh sách được liên kết trong Java

Cấu trúc dữ liệu sử dụng các phương pháp được xác định trước khác nhau để lưu trữ, truy xuất và xóa dữ liệu, điều này dẫn đến việc tạo ra các chương trình hiệu quả. Danh sách liên kết là một cấu trúc dữ liệu phổ biến, bao gồm danh sách các nút được kết nối (hoặc liên kết).





Nhưng làm thế nào để bạn tạo một danh sách liên kết trong Java? Chúng ta hãy xem xét.



Danh sách liên kết hoạt động như thế nào?

Mọi danh sách được liên kết đều bắt đầu bằng một nút đặc biệt thường được gọi là 'đầu', nút này có nhiệm vụ trỏ đến đầu danh sách mọi lúc. Phần đầu rất quan trọng vì mỗi nút trong danh sách được liên kết không cần phải theo sau nút kế nhiệm về mặt vật lý (có nghĩa là nút tiền nhiệm và nút kế nhiệm không cần phải kề nhau về mặt vật lý).





Giống như mọi cấu trúc dữ liệu, danh sách liên kết tạo điều kiện thuận lợi cho việc tạo, truy xuất, chèn và hủy thông qua một tập hợp các chức năng được xác định trước có thể được sử dụng bởi bất kỳ nhà phát triển nào.

Tạo danh sách liên kết trong Java

Một chương trình Java được thiết kế để tạo và thao tác với danh sách liên kết sẽ có ba phần riêng biệt; lớp nút, lớp danh sách liên kết và trình điều khiển. Mặc dù ba phần này có thể được kết hợp trong một tệp, nhưng có một nguyên tắc thiết kế trong khoa học máy tính được gọi là 'tách các mối quan tâm' mà mọi nhà phát triển nên biết.



Nguyên tắc phân tách các mối quan tâm quy định rằng mỗi phần của mã đề cập đến một mối quan tâm cụ thể phải được tách biệt. Nguyên tắc này sẽ giúp bạn tạo mã sạch hơn (dễ đọc hơn) và lý tưởng để tạo cấu trúc dữ liệu.

Bước đầu tiên trong việc tạo danh sách liên kết trong Java là tạo một lớp nút. Một lớp nút nên có hai thuộc tính; một trong các thuộc tính sẽ đại diện cho phần dữ liệu của nút, trong khi thuộc tính khác sẽ đại diện cho phần được liên kết. Một lớp nút cũng phải có một phương thức khởi tạo, getters và setters.



Có liên quan: Tìm hiểu cách tạo lớp học trong Java

Các getters và setters sẽ cho phép các lớp khác (chẳng hạn như lớp danh sách liên kết) truy cập vào các nút khác nhau trong danh sách được liên kết.



Ví dụ về lớp nút

Dưới đây là một ví dụ về lớp nút để bạn hiểu ý của chúng tôi:


public class Node {
private int Data;
private Node NextNode;
//constructor
public Node() {
Data = 0;
NextNode = null;
}
//getters and setters
public int getData() {
return Data;
}
public void setData(int data) {
Data = data;
}
public Node getNextNode() {
return NextNode;
}
public void setNextNode(Node nextNode) {
NextNode = nextNode;
}
}

Trong ví dụ này, thuộc tính dữ liệu sẽ lưu trữ các giá trị số nguyên. Bây giờ bạn đã có lớp nút, đã đến lúc chuyển sang danh sách được liên kết.

Ví dụ về danh sách được liên kết

Dưới đây là một ví dụ về danh sách liên kết trong Java.

public class LinkedList {
private Node Head;
//constructor
public LinkedList() {
Head = null;
}
}

Đoạn mã trên sẽ tạo ra một lớp danh sách liên kết, tuy nhiên, nếu không có các hoạt động khác nhau của nó, lớp này có thể được coi là tương đương với một trình bao trống. Cấu trúc dữ liệu danh sách liên kết có một số hoạt động có thể được sử dụng để điền nó:

  • Chèn ở phía trước.
  • Chèn vào giữa.
  • Chèn ở phía sau.

Có liên quan: Cách xây dựng cấu trúc dữ liệu với lớp JavaScript ES6

Tập hợp danh sách liên kết của các phương pháp chèn là một lý do tại sao nhà phát triển có thể chọn sử dụng cấu trúc dữ liệu này thay cho cấu trúc dữ liệu khác như ngăn xếp (chỉ cho phép chèn và xóa từ trên cùng).

Sử dụng Chèn ở Phương pháp Phía trước

Phương thức chèn ở phía trước, như tên cho thấy, sẽ chèn dữ liệu mới (hoặc các nút mới) ở phía trước danh sách được liên kết.

Chèn ở ví dụ về phương pháp phía trước

Dưới đây là một ví dụ về cách bạn sẽ chèn dữ liệu mới vào đầu danh sách của mình.

//insert node at front method
public void insertAtFront(int key) {
//create a new node using the node class
Node Temp = new Node();
//check if the Temp node was successfully created
//assign the data that was provides by the user to it
if(Temp != null) {
Temp.setData(key);
Temp.setNextNode(null);

//check if the head of the linked list is empty
//assign the node that was just created to the head position
if(Head == null) {
Head = Temp;
}
//if a node is already at the head position
//add the new node to it and set it as the head
else {
Temp.setNextNode(Head);
Head = Temp;
}
}
}

Các insertAtFront trong ví dụ trên cho phép người dùng thêm các nút mới vào danh sách liên kết nhất định.

Áp dụng Chèn ở ví dụ phía trước

Dưới đây là một ví dụ về cách bạn áp dụng chèn ở phía trước.

public class Driver {
//executes the program
public static void main(String[] args) {
//create a new linked list called List
LinkedList List = new LinkedList();
//add each value to the front of the linked list as a new node
List.insertAtFront(10);
List.insertAtFront(8);
List.insertAtFront(6);
List.insertAtFront(4);
List.insertAtFront(2);
}
}

Các Người lái xe lớp (là tên thường được gán cho lớp thực thi trong Java), sử dụng lớp LinkedList để tạo danh sách liên kết gồm năm số chẵn. Nhìn vào đoạn mã trên, có thể dễ dàng nhận thấy rằng số '2' nằm ở vị trí đầu trong danh sách được liên kết. Nhưng làm thế nào bạn có thể xác nhận điều này?

xbox một người không thể kết nối với internet

Sử dụng phương pháp hiển thị tất cả các nút

Phương thức hiển thị tất cả các nút là một phương pháp danh sách liên kết thiết yếu. Nếu không có nó, một nhà phát triển sẽ không thể nhìn thấy các nút trong danh sách được liên kết. Nó di chuyển qua danh sách được liên kết (bắt đầu từ phần đầu) in dữ liệu được lưu trữ trong mỗi nút tạo thành danh sách.

Ví dụ về phương pháp hiển thị tất cả các nút

Dưới đây là một ví dụ về việc sử dụng phương pháp hiển thị tất cả ghi chú trong Java.

//display all nodes method
public void displayAllNodes() {
//create a new node call Temp and assign it to the head of the linked list
//if the head has a null value then the linked list is empty
Node Temp = Head;
if (Head == null){
System.out.println('The list is empty.');
return;
}
System.out.println('The List:');

while(Temp != null) {
//print the data in each node to the console(starting from the head)
System.out.print(Temp.getData() + ' ');
Temp = Temp.getNextNode();
}
}

Bây giờ displayAllNodes phương pháp đã được thêm vào LinkedList bạn có thể xem danh sách liên kết bằng cách thêm một dòng mã vào lớp trình điều khiển.

Sử dụng ví dụ về phương pháp hiển thị tất cả các nút

Dưới đây, bạn sẽ thấy cách bạn sử dụng phương pháp hiển thị tất cả các nút.

//print the nodes in a linked list
List.displayAllNodes();

Việc thực thi dòng mã trên sẽ tạo ra kết quả sau trong bảng điều khiển:

Danh sách:

2 4 6 8 10

Sử dụng phương pháp tìm nút

Sẽ có những trường hợp khi người dùng muốn tìm một nút cụ thể trong danh sách được liên kết.

Ví dụ: sẽ không thực tế nếu một ngân hàng có hàng triệu khách hàng in tất cả các khách hàng trong cơ sở dữ liệu của họ khi họ chỉ cần xem chi tiết của một khách hàng cụ thể.

Do đó, thay vì sử dụng displayAllNodes phương pháp, một phương pháp hiệu quả hơn là tìm một nút duy nhất chứa dữ liệu cần thiết. Đây là lý do tại sao việc tìm kiếm phương pháp một nút lại quan trọng trong cấu trúc dữ liệu danh sách liên kết.

Ví dụ về phương pháp tìm nút

Dưới đây là một ví dụ về việc sử dụng phương pháp nút tìm.

//search for a single node using a key
public boolean findNode(int key) {
//create a new node and place it at the head of the linked list
Node Temp = Head;
//while the current node is not empty
//check if its data matches the key provided by the user
while (Temp != null) {
if (Temp.getData() == key) {
System.out.println('The node is in the list');
return true;
}
//move to the next node
Temp = Temp.getNextNode();
}
//if the key was not found in the linked list
System.out.println('The node is not in the list');
return false;
}

Với displayAllNodes , bạn đã xác nhận rằng LinkedList chứa 5 số chẵn từ 2 đến 10. findNode Ví dụ trên có thể xác nhận xem một trong những số chẵn đó có phải là số 4 hay không bằng cách chỉ cần gọi phương thức trong lớp trình điều khiển và cung cấp số dưới dạng tham số.

Sử dụng ví dụ về phương pháp tìm nút

Dưới đây là ví dụ về cách bạn sử dụng phương pháp nút tìm trong thực tế.

//check if a node is in the linked list
List.findNode(4);

Đoạn mã trên sẽ tạo ra kết quả sau trong bảng điều khiển:

The node is in the list

Sử dụng phương pháp xóa nút

Sử dụng cùng một ví dụ về ngân hàng ở trên, một khách hàng trong cơ sở dữ liệu của ngân hàng có thể muốn đóng tài khoản của họ. Đây là nơi mà phương thức xóa một nút sẽ hữu ích. Đây là phương pháp danh sách liên kết phức tạp nhất.

Phương thức Delete a Node tìm kiếm một nút nhất định, xóa nút đó và liên kết nút trước đó với nút theo sau nút đã bị xóa.

Ví dụ về phương pháp xóa nút

Dưới đây là một ví dụ về phương pháp xóa một nút.

public void findAndDelete(int key) {
Node Temp = Head;
Node prev = null;
//check if the head node holds the data
//and delete it
if (Temp != null && Temp.getData() == key) {
Head = Temp.getNextNode();
return;
}
//search the other nodes in the list
//and delete it
while (Temp != null) {
if (Temp.getNextNode().getData() == key ) {
prev = Temp.getNextNode().getNextNode();
Temp.setNextNode(prev);
return;
}
Temp = Temp.getNextNode();
}
}

Sử dụng Ví dụ về phương pháp Xóa nút

Dưới đây là một ví dụ về việc sử dụng phương pháp xóa một nút trong thực tế.

tôi có thể xem trực tiếp instagram trên máy tính của mình không
//delete the node that holds the data 4
List.findAndDelete(4);
//print all nodes in the linked list
List.displayAllNodes();

Sử dụng hai dòng mã trên trong lớp Trình điều khiển có sẵn sẽ tạo ra kết quả sau trong bảng điều khiển:

The List:
2 6 8 10

Bây giờ bạn có thể tạo danh sách được liên kết trong Java

Nếu bạn đã làm đến phần cuối của bài viết hướng dẫn này, bạn sẽ học được:

  • Cách tạo một lớp nút.
  • Cách tạo lớp danh sách liên kết.
  • Cách điền một lớp danh sách liên kết với các phương thức được xác định trước của nó.
  • Cách tạo một lớp trình điều khiển và sử dụng các phương pháp danh sách liên kết khác nhau để đạt được kết quả mong muốn.

Danh sách liên kết chỉ là một trong nhiều cấu trúc dữ liệu mà bạn có thể sử dụng để lưu trữ, truy xuất và xóa dữ liệu. Vì bạn đã có mọi thứ cần thiết để bắt đầu, tại sao không thử các ví dụ này cho chính mình trong Java?

Đăng lại Đăng lại tiếng riu ríu E-mail Cách tạo và thực hiện các thao tác trên mảng trong Java

Học Java? Hãy để các mảng xử lý dữ liệu của bạn một cách dễ dàng.

Đọc tiếp Chủ đề liên quan
  • Lập trình
  • Java
  • Lập trình
  • Mẹo mã hóa
Giới thiệu về tác giả Kadeisha Kean(21 bài báo đã xuất bản)

Kadeisha Kean là Nhà phát triển Phần mềm Full-Stack và Người viết Kỹ thuật / Công nghệ. Cô ấy có khả năng khác biệt để đơn giản hóa một số khái niệm công nghệ phức tạp nhất; sản xuất vật liệu có thể dễ dàng hiểu được bởi bất kỳ người mới làm quen với công nghệ. Cô ấy đam mê viết lách, phát triển phần mềm thú vị và đi khắp thế giới (thông qua phim tài liệu).

Xem thêm từ Kadeisha Kean

Theo dõi bản tin của chúng tôi

Tham gia bản tin của chúng tôi để biết các mẹo công nghệ, đánh giá, sách điện tử miễn phí và các ưu đãi độc quyền!

Bấm vào đây để đăng ký