[Bài đọc] Cấu trúc dữ liệu LinkedList

LinkedList là một cấu trúc dữ liệu danh sách, trong đó, các phần tử được liên kết thông qua các tham chiếu tuyến tính giữa các phần tử liên tiếp nhau.

Phần tử đầu tiên sẽ có một liên kết trỏ đến phần tử thứ 2, phần tử thứ 2 sẽ có liên kết trỏ đến phần tử thứ 3, và cứ như vậy cho đến phần tử cuối cùng.

Đặc trưng cơ bản của LinkedList đó là việc truy xuất ngẫu nhiên chậm, do phải duyệt lần lượt các phần tử trước khi đến được vị trí muốn truy xuất

Ngược lại, thao tác thêm và xoá phần tử trong LinkedList lại rất hiệu quả, bởi vì chỉ cần thay đổi tham chiếu của các phần tử.

Cấu trúc của LinkedList

LinkedList hoạt động dựa trên cơ chế liên kết giữa các Node. Mỗi node chứa dữ liệu của node đó và liên kết đến node kế tiếp nó.

Ví dụ đoạn mã sau khai báo 1 lớp có tên là Node để đại diện cho một phần tử trong trong LinkedList.

class ListNode { public $data = NULL; public $next = NULL; public function __construct(string $data = NULL) { $this->data = $data; } }

Head là phần tử đầu tiên của LinkedList, tức là phần tử Node1.

Tail là phần tử cuối cùng của LinkedList, tức là phần tử Node n.

Bên trong Node 1 có chứa phần tử element 1 và tham chiếu đến Node 2. Bên trong Node 2 chứa phần tử element 2 và tham chiếu đến Node tiếp theo, cứ như thế cho đến phần tử cuối cùng, có tham chiếu trỏ đến null, tức là không có phần tử tiếp theo.

class LinkedList {
private $_firstNode = NULL;
private $_totalNodes = 0;

public function insert(string $data = NULL) {
$newNode = new ListNode($data);

if ($this->_firstNode === NULL) {
$this->_firstNode = &$newNode;
} else {
$currentNode = $this->_firstNode;
while ($currentNode->next !== NULL) {
$currentNode = $currentNode->next;
}
$currentNode->next = $newNode;
}
$this->_totalNode++;
return TRUE;
}

public function display() {
echo “Total book titles: “.$this->_totalNode.”\n”;
$currentNode = $this->_firstNode;
while ($currentNode !== NULL) {
echo $currentNode->data . “\n”;
$currentNode = $currentNode->next;
}
}
}

Sử dụng LinkedList

$BookTitles = new LinkedList();
$BookTitles->insert(“Introduction to Algorithm”);
$BookTitles->insert(“Introduction to PHP and Data structures”);
$BookTitles->insert(“Programming Intelligence”);
$BookTitles->display();

Kết quả:

Total book titles: 3
Introduction to Algorithm
Introduction to PHP and Data structures
Programming Intelligence

Thêm phần tử vào phần đầu của LinkedList

Để thực hiện thao tác thêm một phần tử vào đầu của LinkedList, chúng ta cần trỏ tham chiếu ở phần tử mới vào ngay phần tử đầu tiên của mảng. Phần tử mới được thêm vào sẽ trở thành phần tử đầu tiên của LinkedList. Hay nói cách khác nó chính là head của LinkedList. Không có sự thay đổi nào ở các phần tử còn lại.Thêm phần tử vào phần cuối của LinkedList.

public function insertAtFirst(string $data = NULL) {
$newNode = new ListNode($data);
if ($this->_firstNode === NULL) {
$this->_firstNode = &$newNode;
} else {
$currentFirstNode = $this->_firstNode;
$this->_firstNode = &$newNode;
$newNode->next = $currentFirstNode;
}
$this->_totalNode++;
return TRUE;
}

Thêm phần tử vào phần đuôi của LịnkedList.

Để thực hiện thao tác thêm phần tử vào đuôi của LinkedList, chúng ta thực hiện trỏ tham chiếu ở phần tử cuối cùng vào phần tử mới. Như vậy, phần tử mới sẽ trở thành phần tử cuối cùng của LinkedList, hay nói cách khác nó chính là tail của LinkedList.

Thêm phần tử vào một vị trí nhất định trong LinkedList

Để thực hiện thao tác thêm một phần tử vào một vị trí bất kỳ, chúng ta chỉ cần thay đổi tham chiếu đến 2 node trước và sau vị trí đó.

Chẳng hạn, để thêm một phần tử vào sau phần tử thứ i, chúng ta sẽ thay đổi tham chiếu ở các phần tử ở vị trí i và và i + 1.

Gắn tham chiếu ở phần tử ei vào phần tử mới, sau đó gán tham chiếu ở phần tử mới trỏ sang phần tử ei+1. Như vậy, phần tử mới đã được thêm vào trong LinkedList mà không làm thay đổi bất cứ phần tử nào còn lại.

Như vậy, chúng ta có thể dễ dàng thấy rằng thao tác thêm phần tử vào LinkedList là dễ dàng và hiệu quả hơn nhiều so với khi thực hiện ở trên ArrayList.

Tìm một phần tử trong LinkedList

Để tìm một phần tử trong danh sách, chúng ta duyệt qua từng node và kiểm tra xem dữ liệu của node đó có trùng với dữ liệu muốn tìm kiếm hay không. Nếu dữ liệu trùng thì node đó sẽ được trả về, nếu không thì tiếp tục tìm kiếm. Đến cuối cùng, nếu không có node nào có dữ liệu trùng thì FALSE sẽ được trả về.

public function search(string $data = NULL) {
if ($this->_totalNode) {
$currentNode = $this->_firstNode;
while ($currentNode !== NULL) {
if ($currentNode->data === $data) {
return $currentNode;
}
$currentNode = $currentNode->next;
}
}
return FALSE;
}

Xoá phần tử đầu tiên của LinkedList

Để thực hiện xoá phần tử đầu tiên của LinkedList. Chúng ta chỉ cần trỏ head của LinkedList vào phần tử thứ 2, như vậy thì phần tử thứ 2 sẽ trở thành head của LinkedList.

public function deleteFirst() {
if ($this->_firstNode !== NULL) {
if ($this->_firstNode->next !== NULL) {
$this->_firstNode = $this->_firstNode->next;
} else {
$this->_firstNode = NULL;
}
$this->_totalNode–;
return TRUE;
}
return FALSE;
}

Xoá phần tử cuối cùng của LinkedList

Để thực hiện thao tác xoá phần tử cuối cùng của LinkedList. Chúng ta chỉ cần gán giá trị null cho tham chiếu ở phần tử gần vị trí cuối cùng. Như vậy phần tử ở vị trí cuối cùng sẽ không còn được tham chiếu đến nữa. Và phần tử ở gần vị trí cuối cùng sẽ trở thành tail của LinkedList.

public function deleteLast() {
if ($this->_firstNode !== NULL) {
$currentNode = $this->_firstNode;
if ($currentNode->next === NULL) {
$this->_firstNode = NULL;
} else {
$previousNode = NULL;

while ($currentNode->next !== NULL) {
$previousNode = $currentNode;
$currentNode = $currentNode->next;
}

$previousNode->next = NULL;
$this->_totalNode–;
return TRUE;
}
}
return FALSE;
}

Xoá một phần tử tại vị trí bất kỳ

Để thực hiện thao tác xoá một phần tử tại một vị trí bất kỳ, chúng ta thay đổi tham chiếu ở phần tử trước nó.

Chẳng hạn, để xoá phần tử tại vị trí k, chúng ta sẽ cho tham chiếu ở phần tử k-1 trỏ đến phần tử k + 1, như vậy phần tử k sẽ được bỏ qua và không còn nằm trong LinkedList nữa. Không có bất cứ thay đổi nào xảy ra với các phần tử còn lại.

Như vậy, chúng ta có thể thấy rằng thao tác xoá phần tử trong LinkedList rất dễ dàng và hiệu quả hơn so với thao tác này trong ArrayList vì không phải thực hiện thao tác dịch các phần tử.

Singly Linked List

• Singly Linked List (Danh sách liên kết đơn): Một phần tử chỉ chứa một liên kết đến phần tử tiếp sau nó. 
• Circular Singly LinkedList (Danh sách liên kết đơn vòng): phần tử cuối cùng lại tham chiếu đến phần tử đầu tiên, tạo thành một vòng khép kín

Danh sách liên kết đơn vòng

Doubly Linked List

Doubly Linked List (Danh sách liên kết đôi) có các đặc điểm:

• Một node chứa hai liên kết trỏ đến phần tử đứng trước và sau nó
• Phần tử trước của phần tử đầu tiên là null
• Phần tử sau của phần tử sau là null

Đối với loại LinkedList này, chúng ta có thể duyệt các phần tử theo các chiều khác nhau.

Circular Doubly Linked List

Có một phiên bản khác của danh sách liên kết đôi đó là danh sách liên kết đôi vòng. Có nghĩa phần tử đầu có tham chiếu đến phần tử cuối và phần tử cuối có tham chiếu đến phần tử đầu, như vậy tạo thành một vòng khép kín.

Lựa chọn ArrayList hay LinkedList?

Như vậy, trong cấu trúc dữ liệu danh sách, chúng ta có 2 cách triển khai khác nhau đó là dựa trên mảng và dựa trên liên kết tiếp nối. Đại diện cho 2 cái triển khai này đó là lớp ArrayList và LinkedList.

Vì cách triển khai khác nhau nên hiệu năng của 2 loại này cũng khác nhau trong từng trường hợp. Do đó, chúng ta cần biết lựa chọn cấu trúc dữ liệu phù hợp để đảm bảo được hiệu năng của ứng dụng.

Điểm khác biệt đầu tiên giữa ArrayList và LinkedList đó là ArrayList cho phép truy xuất ngẫu nhiên rất nhanh, trong khi LinkedList thì truy xuất ngẫu nhiên rất chậm. Do đó, ArrayList thích hợp cho các bài toán mà chúng ta cần truy xuất nhiều đến các phần tử.

Điểm khác biệt thức hai đó là lớp ArrayList có hiệu năng thấp hơn trong việc thêm hoặc xoá các phần tử so với LinkedList. Do đó, LinkedList thích hợp hơn cho các bài toán mà chúng ta cần phải thêm và xoá các phần tử thường xuyên.