Simply Linked List

1. Code khởi tạo element trong Linked List

   Code:

   public class Node {
       int value;
       Node next;
   
       public Node(){
       }
       public Node(int value, Node next){
           this.value = value;
           this.next = next;
       }
       public Node(int value){
           this.value = value;
           this.next = null;
       }
   }
   

                   ||
                   ||
                   ||
                   ||
                  \  /
                   \/
   
   +-------------------+--------------+
   |                   |              |
   |       Value       |     Next     |
   |                   |              |
   +-------------------+--------------+
   

   Một phần tử trong list bao gồm 2 phần là value và next:

   • Value: Dùng để lưu trữ thông tin của phần tử trong list
   • Next: Dùng để trỏ đến phần tử tiếp theo trong list

2. Khởi tạo list, thêm, chèn, sửa, xóa phần tử trong list:

   • Khởi tạo:

     Code:

     public class MyList {
         Node head,tail;
         int size;
     
         public MyList(){
             head = tail = null;
             size = 0;
         }
     }
     

     Trong đó:

     • head: phần tử đầu tiên của list
     • tail: phần tử cuối cùng của list
     • size: kích cỡ của list, vì kích cỡ không cố định nên sẽ tạo 1 biến size để kiểm soát kích cỡ

   • Kiểm tra list trống hay không:

     Code:

     boolean isEmpty(){
         return head == null;
     }
     

     Giải thích:

     • So sánh với phần tử head (phần tử đầu tiên), nếu phần tử này không có - tức là null - thì sẽ trả về true, tương đương với list rỗng. Vì phần tử đầu tiên không có nên đồng nghĩa phần tử tail (phần tử cuối cùng) cũng không tồn tại.

   • Thêm:

     • Thêm vào cuối list:

       Code:

       void add(int value){
           Node newItem = new Node(value);
           if(isEmpty()){
               head = tail = newItem;
           } else {
               tail.next = newItem;
               tail = newItem;
           }
           size++;
       }
       

     • Thêm vào đầu list:

       Code:

       void addFirst(int value){
           Node newItem = new Node(value);
           if(isEmpty()){
               head = tail = newItem;
           } else {
               newItem.next = head;
               head = newItem;
           }
           size++;     
       }
       

     • Thêm vào vị trí bất kì trong list:

       Code:

       void add(int value, int index){
           if(index <= 0){
               addFirst(value);
               return;
           } else if(index > size){
               addLast(value);
               return;
           } else {
               int count = 0;
               Node currentItem = head;
               // Tìm phần tử có vị trí trước vị trí muốn chèn
               while(currentItem.next != null && count != index -1){
                   count++;
                   currentItem = currentItem.next;
               }
               // Nếu list trống và vị trí muốn chèn lớn hơn 2 thì sẽ không làm gì cả
               if(currentItem == null){
                   return;
               } else {
                   // Thêm phần tử vào vị trí muốn chèn
                   Node newItem = new Node(value);
                   newItem.next = currentItem.next;
                   currentItem.next = newItem;
                   size++;
               }
           }
       }