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

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 Node và LinkList 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.

Bao gồm:

• Thuộc tính data
• Thuộc tính node đằng sau.
• Phương thức đọc dữ liệu của node

Lớp LinkList bao gồm:

• Node đầu tiên
• Node cuối cùng
• Số lượng node
• Phương thức thêm một node vào đầu
• Phương thức thêm một nốc vào phía sau
• Phương thức lấy ra số lượng node
• Phương thức đọc linkedlist

Hướng dẫn

Bước 1: Lớp Node: Tạo mới một tệp với tên Node.php

Mã PHP:

class Node{ 
   /* Node data */ 
   public $data;  
  /* Link to next node */ 
   public $next; 
   function __construct($data)    {   
     $this->data = $data;     
   $this->next = NULL;   
 }    function readNode()    {  
      return $this->data;    }
}

Bước 2: Lớp LinkList: Tạo mới một tệp với tên LinkList.php

Mã PHP:

include_once ('Node.php');

class LinkList{ 
   /* Link to the first node in the list */ 
   private $firstNode;   
 /* Link to the last node in the list */ 
   private $lastNode;   
 /* Total nodes in the list */
    private $count;    
function __construct()    {   
     $this->firstNode = NULL; 

       $this->lastNode = NULL;   
     $this->count = 0;    
}
} 

Bước 3: Tạo phương thức thêm node vào đầu Danh sách

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

Tại lớp LinkList tạo phương thức insertFirst() để thêm một node vào phía đầu của danh sách

Mã PHP:

public function insertFirst($data){ 
   $link = new Node($data); 
   $link->next = $this->firstNode;
    $this->firstNode = $link;  
  /* If this is the first node inserted in the list       then set the lastNode pointer to it.    */ 
   if($this->lastNode == NULL)    
    $this->lastNode = $link;   
 $this->count++;
}

Ở đoạn code trên, ban đầu sẽ khởi tạo một node mới : $link = new Node($data);

Sau đó sẽ gán node kế sau của node mới khởi tạo là node đầu tiên của linklist: $link->next = $this->firstNode;

Câu lệnh $this->firstNode = $link; sẽ gán tiếp node đầu của danh sách là node mới khởi tạo.

Kiểm tra, nếu node mới khởi tạo là node đầu tiên được thêm vào danh sách thì sẽ đặt node đó là node cuối cùng của danh sách.

if($this->lastNode == NULL)   
     $this->lastNode = $link;

Cuối cùng ta tăng kích thước của danh sách lên 1 đơn vị.

Bước 4: Tạo phương thức thêm node vào phía sau Danh sách

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

Mã PHP:

public function insertLast($data){ 
   if($this->firstNode != NULL) { 
       $link = new Node($data); 
       $this->lastNode->next = $link;   
     $link->next = NULL;   
     $this->lastNode = $link;    
    $this->count++;   
 }else {        $this->insertFirst($data);   
 }
}

Ở đoạn code trên, sẽ kiểm tra nếu danh sách đã tồn tại node bên trong thì sẽ khởi tạo một node mới  ($link = new Node($data);).

Sau đó gán node kế tiếp phía sau của node cuối cùng hiện tại là node mới khởi tạo ($this->lastNode->next = $link;).

Vì là node cuối cùng nên node kế phía sau sẽ được gán giá trị NULL ($link->next = NULL;).

Câu lệnh $this->lastNode = $link; có nghĩa là gán node mới khởi tạo là node cuối cùng của danh sách.

Sau đó tăng kích thước của danh sách lên một đơn vị.

Bước 5: Tạo phương thức lấy ra số lượng node

Mục đích: Lấy ra số lượng các node được thêm vào danh sách

Mã PHP:

public function totalNodes(){ 
   return $this->count;}

Bước 6: Tạo phương thức đọc ra Danh sách

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

Mã PHP:

public function readList(){  
  $listData = array();  
  $current = $this->firstNode;  
  while($current != NULL)    {   
     array_push($listData, $current->readNode()); 
       $current = $current->next; 
   }   
 return $listData;
} 

Bước 7: Tạo lớp để chạy thử

Tạo một file với tên LinkedListMain.php và khởi tạo một đối tượng LinkedList. Sau đó gọi đến các phương thức để thêm các phần tử mới vào phía đầu và cuối , sau đó lấy ra tổng số lượng node, cuối cùng hiển thị toàn bộ các phần tử của LinkedList ra.

Mã PHP:

include_once ('LinkList.php');
$linkedList = new LinkList();
$linkedList->insertFirst(11);
$linkedList->insertFirst(22);
$linkedList->insertLast(33);
$linkedList->insertLast(44);
$totalNodes = $linkedList->totalNodes();
$linkData = $linkedList->readList();
echo $totalNodes;echo implode ('-' , $linkData);
 Chạy chương trình, quan sát kết quả.

Mã nguồn tham khảo: https://github.com/codegym-vn/php-linkedlist

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

– Up bài lên Github

– Paste link vào phần nộp bài và nhấn submit

Tổng kết

Qua bài tập trên chúng ta đã luyện tập:

• Kỹ năng cài đặt một LinkedList đơn giản