Đã đăng vào thg 4 18, 2019 1:57 SA 2 phút đọc
1. Linked List là cái gì?Linked List là tập hợp các nodes được liên kết với nhau. Node sau chứa link đến node trước -> Một linked list chứa tập hợp các node. ->Một node chứa data và liên kết đến node tiếp theo. Ví dụ ở đây data là 12. Có thể thay thế bằng các object hoặc bất kì dữ liệu nào khác thậm chí là một linked list khác (hại não =)) )
2. Đặc điểm chính:Ưu điểm:- Tiết kiếm bộ nhớ và cấp phát động: Không như array cần 1 lượng chỉ định ô nhớ trên bộ nhớ ngay khi khỏi tạo. Linked list chỉ sử dụng bộ nhớ để lưu trữ khi dữ liệu thực sự được lưu vào linked list.
- Nó còn có thể lưu các phần tử ở bất cứ đâu được phép trên bộ nhớ mà không cần các ô nhớ liền kề nhau như array
- Quick insertion (Thêm rất nhanh với complexity chỉ là O(1))
- Quick deletion (Xóa nhanh)
Nhược điểm- Slow search (Tìm kiểm chậm do phải duyệt qua nhiều node để đến được node cần tìm)
3. Thực hiện tạo linked list trên pythonĐầu tiên ta tạo 1 class nodes trên python:class Node:
def __init__(self,data):
self.data = data #Đây là dữ liệu mà ta sẽ lưu trữ trong mỗi node
self.next = None #Đây là con trỏ trỏ đến node tiếp theo trong linked list
Thử set dữ liệu cho các node bằng tay:node1 = Node("Java")
node2 = Node("Python")
node3 = Node("C++")
node1.next = node2
node2.next = node3
# Ta sẽ được linked list dạng như: Java -> Python -> C++
Hàm push để thêm dữ
liệu cho linked listdef push(head, valuetoInsert):
currentNode = head
while currentNode is not None:
if currentNode.nextNode is None:
currentNode.nextNode = linkedListNode(valuetoInsert)
return head
currentNode = currentNode.nextNode
Thử tạo hàm duyệt các phần tử của linked list:class Node:
...
def traverse(self):
node = self # Xác định node đầu tiên hay còn gọi là head node
while node != None:
print node.data # in ra dữ liệu
node = node.next # tiếp tực đến node tiếp theo
Ngoài ra ta còn có Double Linked List (Danh sách liên kết đôi)class DoublyNode:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
-> Điểm khác nhau của double linked list và linked list chính là mỗi node của DLL vừa có chứa con trỏ đến node tiếp theo vừa chứa con trỏ đến node trước nó. 4. Độ phức tạp thuật toán của linked listVới n là số phần tử của linked: - Thêm một phần tử vào sau danh sách: O(n) do phải duyệt hết các ptử để lấy
node ở đuôi - Thêm một phần tử ở đầu danh sách: O(1) - Duyệt qua tất cả các phần tử O(n) - Xóa 1 phần tử: Trường hợp xấu nhất là O(n) và tốt nhất là O(1) ## Tài liệu tham khảo: https://medium.com/@kojinoshiba/data-structures-in-python-series-1-linked-lists-d9f848537b4d All rights reserved Tổng quanHai bài trước chúng ta đã tìm hiểu về Array và Hash Table. Và chúng ta thấy cả hai loại cấu trúc dữ liệu đều có những nhược điểm của mình.
Với Array : Chúng ta thường gặp phải vấn đề là chèn hoặc xoá một phần tử chậm và mỗi khi thêm phần tử đến giới hạn, ta lại phải sao chép toàn bộ data sang một vùng nhớ có kích thước lớn gấp đôi.
Với Hash Table : Hàm băm khá là tuyệt, nó sẽ lo cho chúng ta việc lưu bộ nhớ, nhưng tiếc là mảng
băm không có thứ tự và bộ nhớ sẽ được lưu rải rác.
Để giải quyết những vấn đề trên chúng ta có thể sử dụng một loại CTDL mới là Linked List.
Nói vậy không có nghĩa Linked List là tốt nhất và ta sẽ luôn sử dụng Linked List, chúng ta luôn có những sự đánh đổi khi dùng một loại CTDL. Linked List là gì?Như tên gọi của nó, đó là một loại danh sách có liên kết. Có hai loại Linked List đó là Singly Linked List và Doubly Linked
List. Trong bài này chúng ta sẽ tìm hiểu về Singly Linked List trước. Singly Linked List
Như hình vẽ ta có thể thấy mỗi một khối xanh-xanh lá là một Node, mỗi Node chứa một giá trị (value) và một con trỏ (pointer) trỏ đến Node tiếp theo.
Node đầu được gọi là Head, nốt cuối gọi là Tail.
Khi một phần tử mà con trỏ trỏ đến Node tiếp theo là Null, ta biết đó là phần tử cuối cùng và là Tail.
Bạn có thể thấy Linked List là một CTDL khá đơn giản, nó là một phần tử liên kết với phần tử tiếp theo với phần tử tiếp theo và giữ cho đến khi phần tử cuối cùng trỏ đến Null.
Con trỏ (Pointer)Chắc hẳn các bạn cũng đã từng nhiều lần nghe
đến khái niệm con trỏ và cũng nhiều bạn vẫn còn mơ hồ về khái niệm này.
Hiểu đơ giản thì con trỏ là một tham chiếu đến một vị trí khác, một bộ nhớ khác hoặc một đối tượng khác, ở đây là một Node khác.
Chúng ta cùng xem qua một ví dụ: final obj1 = {'value': 1};
final obj2 = obj1;
obj1['value'] = 2;
print(obj2);
Và kết quả nhận được: dart implement.dart
{value: 2}
Kết quả xảy ra như vậy là ở đây tôi đã tạo ra một con trỏ ở đây nói rằng đối tượng obj2 sẽ tham chiếu đến obj1 và cả 2 đối tượng sẽ cùng trỏ đến một vị trí bộ
nhớ, con trỏ ở đây đơn giản là một vị trí trong bộ nhớ.
Cách implement và các hàm cơ bảnChúng ta cùng xem qua một cách implement từ đầu một Linked List class Node<E> {
final E value;
Node? next;
Node(this.value, this.next);
}
class MyLinkedList<E> {
Node? head;
Node? tail;
var length = 0;
MyLinkedList(E value) {
head = Node(value, null);
tail = head;
length = 1;
}
Node append(value) {
final newNode = Node(value, null);
tail!.next = newNode;
tail = newNode;
length++;
return head!;
}
Node appendAll(List<E> values) {
values.forEach((element) {
append(element);
});
return head!;
}
Node prepend(value) {
final newNode = Node(value, head);
head = newNode;
length++;
return head!;
}
Node insert(index, value) {
if (index > length) {
throw Exception("Out of index");
} else if (index == 0) {
prepend(value);
} else if (index == length) {
append(value);
} else {
final leadNode = traverseToIndex(index - 1);
final newNode = Node(value, leadNode!.next);
leadNode.next = newNode;
}
length++;
return head!;
}
Node? remove(index) {
if (index >= length) {
throw Exception("Out of index");
} else if (index == 0) {
head = head!.next;
} else {
final leadNode = traverseToIndex(index - 1);
final removeNode = leadNode!.next;
leadNode.next = removeNode!.next;
removeNode.next = null;
}
length--;
return head;
}
Node? traverseToIndex(int index) {
var count = 0;
var temp = head;
while (count != index) {
temp = temp!.next;
count++;
}
return temp;
}
Node? reverse() {
if (length == 1) {
return head;
}
var first = head;
var second = first!.next;
while (second != null) {
var temp = second.next;
second.next = first;
first = second;
second = temp;
}
head!.next = null;
head = first;
return head;
}
}
Qua đoạn code trên ta có thể thấy mỗi phần tử của Linked List là một Node(value, next).
Một Linked List bao gồm có Head (phần tử đầu) Tail (phần tử cuối), length (độ dài) và một chuỗi các Node liên kết với nhau. Tiếp theo chúng ta sẽ tìm hiểu
sâu hơn vào các hàm cơ bản của Linked List. Appendfinal newNode = Node(value, null);
tail!.next = newNode;
tail = newNode;
length++;
Qua đoạn code trên, chúng ta có thể thấy việc thêm một Node mới vào cuối của Linked List là khá đơn giản, chỉ cần update lại con trỏ của phần tử cuối cùng(tail) trỏ vào Node mới và update Node mới là phần tử cuối cùng.
Chúng ta có thể thấy độ phức tạp hàm này là O(1). Prependfinal newNode = Node(value, head);
head = newNode;
length++;
Tương tự, việc thêm vào đầu Linked List cũng khá đơn giản và có độ phức tạp là
O(1), chỉ cần update Node mới trỏ và head và update node mới là head. Get Node? get(int index) {
var count = 0;
var temp = head;
while (count != index) {
temp = temp!.next;
count++;
}
return temp;
}
Việc look up phần tử của Linked List bắt buộc cần di chuyển tuần tự từ Head và đi tới vị trí cần lấy, nên việc tìm kiếm phần tử theo chỉ mục của Linked List sẽ có độ phức tạp là O(n). Insertif (index > length) {
throw Exception("Out of index");
} else if (index == 0) {
prepend(value);
} else if (index == length) {
append(value);
} else {
final leadNode = traverseToIndex(index - 1);
final newNode = Node(value, leadNode!.next);
leadNode.next = newNode;
}
length++;
Việc insert như chúng ta thấy nếu insert vào đầu hoặc cuối thì sẽ tương tự với việc append hoặc prepend.
Nhưng nếu chèn
một phần tử vào giữa thì sẽ phức tạp hơn, chúng ta sẽ cần tìm Node tại vị trí index-1, sau đó cập nhật con trỏ của Node mới vào Node(index) và cập nhật con trỏ next của Node(index-1) vào Node mới tạo.
Vì muốn thêm một phần tử vào vị trí index, ta cần tìm phần từ tại vị trí index-1 nên việc chèn một phần tử vào LinkedList sẽ là O(n). RemoveNode? remove(index) {
if (index >= length) {
throw Exception("Out of index");
} else if (index == 0) {
head = head!.next;
} else {
final leadNode = get(index - 1);
final removeNode = leadNode!.next;
leadNode.next = removeNode!.next;
removeNode.next = null;
}
length--;
return head;
}
Tương tự, việc xoá một phần tử
ở giữa LinkedList thì ta cũng cần tìm phần tử ở vị trí index-1 và cập nhật lại con trỏ của vị trí index-1 sẽ trỏ đến vị trí index+1. nên độ phức tạp cũng là O(n). Tạm kếtChúng ta vừa đi qua một lượt về Singly Linked List, trong bài tiếp theo chúng ta sẽ tìm hiểu về Doubly LinkedList và đánh giá cách sử dụng chúng.
Cảm ơn các bạn. Link Github | 
