Cấu Trúc Dữ Liệu Trong Java Bài 1: Danh Sách Liên Kết Và Các Thao Tác Cơ Bản Trên Danh Sách Liên Kết

1. Định nghĩa

Danh sách liên kết (linked list) là một kiểu danh sách tuyến tính bao gồm các phần tử liên kết với nhau. Mỗi phần tử có 2 vùng chính: vùng dữ liệu và vùng tham chiếu. 

Cấu trúc một nút có dạng như sau:

class Node 
{   
   [Kiểu dữ liệu] data;   
   Node nextNode;  
}

Hình 1: Một dạng danh sách liên kết

Có các loại danh sách liên kết sau:
- Danh sách liên kết đơn
- Danh sách liên kết kép
- Danh sách liên kết vòng
- Danh sách liên kết vòng kép

Hình 2: Bốn kiểu danh sách liên kết

2. Các thao tác cơ bản trên danh sách liên kết đơn

Ở đây mình sẽ thực hiện các thao tác trên danh sách liên kết đơn chứa các phần tử là các số nguyên. Các kiểu dữ liệu khác hoàn toàn tương tự.

Khởi tạo danh sách liên kết:

clast list
{   
   Node pHead;   //Head là phần tử đầu tiên của danh sách liên kết
   Node pTail;   //Tail là phần tử cuối của danh sách liên kết
}

Thêm một phần tử vào cuối danh sách liên kết:

public static void insertatTail(int data, list lst)
{   
   if(lst.pHead==null) {
      lst.pHead = new node();
      lst.pHead.data = data;
      lst.pHead.next = null;
      
      lst.pTail = lst.pHead;
   }
   else{
      node newnode = new node();
      newnode.data = data;
      newnode.next = null;
   
      lst.pTail.next = newnode;
      lst.pTail = newnode;
   }
}

Thêm một phần tử vào đầu danh sách liên kết:

public static void insertatHead(int data, list lst)
{   
   if(lst.pHead==null) {
      lst.pHead = new node();
      lst.pHead.data = data;
      lst.pHead.next = null;
      
      lst.pTail = lst.pHead;
   }
   else{
      node newnode = new node();
      newnode.data = data;
      newnode.next = null;
   
      newnode.next = lst.pHead;
      lst.pHead = newnode;
  }
}

Xóa một phần tử khỏi danh sách liên kết:

public static void deletenode (int data, list lst)
{   
  if(lst.pHead.data == data){  
          node pTemp = lst.pHead;
   lst.pHead = lst.pHead.next;
   pTemp = null;
   }
   else{
          node pTemp = lst.pHead;
   while(pTemp != null){
  if(pTemp.next.data == data){
          if(pTemp.next == lst.pTail){
           pTemp.next = null;
           lst.pTail = pTemp;
           break;
           }
           else{
     pTemp.next = pTemp.next.next;
     break;
            }
   }
   pTemp = pTemp.next;
    }
   }
}

Duyệt danh sách liên kết:

static void print_out (list lst){
  node pTemp = lst.pHead;
  while(pTemp != null){
   if(pTemp != lst.pTail){
       System.out.print(pTemp.data + " -> "); 
   }
   else{
       System.out.print(pTemp.data); 
   }
   pTemp = pTemp.next;
  }
 }