[Thực hành] Triển khai lớp LinkedList đơn giản

DSA: Danh sách

Mục tiêu

Luyện tập cài đặt cấu trúc LinkedList đơn giản.

Mô tả

Trong phần này, chúng ta sẽ phát triển một chương trình cho phép cài đặt cấu trúc LinkedList đơn giản để lưu một tập dữ liệu bất kỳ. Chương trình gồm 2 lớp MyLinkedList và MyLinkedListTest như sơ đồ mô tả sau:

Lớp Node chứa thông tin về một node trong danh sách liên kết. Lớp này là thuộc trong lớp MyLinkedList.

Lớp MyLinkedList gồm

Các thuộc tính

  • numNodes size xác định số phần tử trong danh sách, mặc định gán là 0.
  • head đối tượng lớp Node

Các phương thức:

  • Phương thức khởi tạo một tham số khởi tạo node đầu tiên trong danh sách
  • Phương thức thêm một phần tử mới vào danh sách: add()
  • Phương thức thêm một phần tử mới vào đầu danh sách: addFirst()
  • Phương thức truy cập một phần tử trong danh sách: get()
  • Phương thức printList() in các phần tử trong danh sách

Lớp MyLinkedListTest chứa phương thức main() để thực thi ứng dụng

Các bước thực hiện

Bước 1: Tạo lớp MyLinkedList với các thuộc tính như mô tả

Lớp MyLinkedList chứa lớp Node.

 public class MyLinkedList {     private  Node head;     private  int numNodes;      public MyLinkedList(Object data) {         head = new Node(data);     }      private class Node {         private Node next;         private Object data;          public Node(Object data) {             this.data = data;         }          public Object getData() {             return this.data;         }     } }

Bước 2: Cài đặt phương thức add

Mục đích: Thêm đối tượng vào vị trí thứ index trong danh sách

Tham số đầu vào: vị trí thêm (index), đối tượng thêm (data)

Mã lệnh:

public void add(int index, Object data) {     Node temp = head;     Node holder;
     for(int i=0; i < index-1 &amp;&amp; temp.next != null; i++) {         temp = temp.next;     }
    holder = temp.next;     temp.next = new Node(data);     temp.next.next = holder;     numNodes++; }

Bước 3: Cài đặt phương thức addFirst()

Mục đích: Thêm đối tượng vào vị trí đầu tiên trong danh sách

Tham số đầu vào: đối tượng thêm (data)

Mã lệnh:

public void addFirst(Object data) {     Node temp = head;     head = new Node(data);     head.next = temp;     numNodes++; }

Bước 4: Cài đặt phương thức get()

Mục đích: Lấy phần tử ở vị trí index từ danh sách

Tham số đầu vào: vị trí cần lấy (index)

Mã lệnh:

public Node get(int index){     Node temp=head;     for(int i=0; i<index; i++) {         temp = temp.next;     }     return temp; } 

Bước 5: Cài đặt phương thức printList

Mục đích: Hiển thị danh sách các phần tử trong danh sách

public void printList() {     Node temp = head;     while(temp != null) {         System.out.println(temp.data);         temp = temp.next;     } } 

Bước 6: Tạo lớp TestMyLinkedList chứa hàm main
Tạo đối tượng thuộc lớp MyLinkedList.

Lần lượt gọi các phương thức addFist(), add(), printList() chạy ứng dụng quan sát kết quả.

Mã lệnh:

public class TestMyLinkedList {     public static void main(String[] args) {         System.out.println("/=/=/=/= TESTING /=/=/=/=");         MyLinkedList ll = new MyLinkedList(10);         ll.addFirst(11);         ll.addFirst(12);         ll.addFirst(13);          ll.add(4,9);         ll.add(4,9);
         ll.printList();     } }

Bước 7: Chạy chương trình. Với việc gọi phương thức addFist(), add() với các giá trị khác. Hiển thị kết quả.

Mã nguồn tham khảo tại đây: https://github.com/codegym-vn/java-mylinkedlist

Hướng dẫn nộp bài

  • Up bài lên github
  • Paste link github vào phần nộp bài.

Hãy tham gia nhóm Học lập trình để thảo luận thêm về các vấn đề cùng quan tâm.

Leave a Reply

Your email address will not be published. Required fields are marked *