Danh sách liên kết

Trở về Mục lục cuốn sách

Tham chiếu nhúng

Ta đã từng thấy những ví dụ về các thuộc tính để chỉ đến những đối tượng; ta gọi chúng là các tham chiếu nhúng (xem thêm module copy trong Chương: Lớp và đối tượng). Một cấu trúc dữ liệu thông dụng, danh sách liên kết, đã tận dụng đặc điểm này.

Danh sách liên kết được hợp thành từ các nút, trong đó mỗi nút có chứa tham chiếu đến nút kế tiếp trong danh sách. Ngoài ra, mỗi nút cũng có một đơn vị dữ liệu trong một khoang (cargo).

Danh sách liên kết được gọi là cấu trúc dữ liệu đệ quy vì lời định nghĩa của nó mang tính đệ quy.

Một danh sách liên kết hoặc là:

  • một danh sách rỗng, biểu diễn bởi None, hay
  • một nút có chứa một đối tượng khoang và một tham chiếu đến một danh sách liên kết.

Cấu trúc dữ liệu đệ quy rất phù hợp với các phương pháp đệ quy.

Lớp Node

Như thường lệ, khi viết một lớp mới, ta sẽ bắt đầu bằng các phương thức khởi tạo và __str__ để có thể kiểm tra được cơ chế tạo lập và hiển thị kiểu dữ liệu mới này:

class Node: 
  def __init__(self, cargo=None, next=None): 
    self.cargo = cargo 
    self.next  = next 

  def __str__(self): 
    return str(self.cargo) 

Như thường lệ, các tham số cho phương thức khởi tạo đều là tùy chọn. Theo mặc định, cả khoang và mối liên kết, next, đều được đặt là None.

Chuỗi biểu thị cho một nút chính là chuỗi biểu thị cho khoang. Vì bất kì giá trị nào cũng có thể truyền được tới hàm str, nên ta có thể lưu được một giá trị bất kì vào danh sách.

Để kiểm tra kết quả tạo lập được đến giờ, ta có thể tạo một Node rồi in nó ra:

>>> node = Node("test") 
>>> print node 
test 

Để thú vị hơn, phải có một danh sách nhiều nút:

>>> node1 = Node(1) 
>>> node2 = Node(2) 
>>> node3 = Node(3) 

Đoạn mã lệnh này tạo nên ba nút, nhưng ta chưa có một danh sách vì ba nút này chưa được nối với nhau. Biểu đồ trạng thái lúc này trông như sau:

Để kết nối các nút, ta phải làm cho nút thứ nhất chỉ đến nút thứ hai rồi nút thứ hai chỉ đến nút thứ ba:

>>> node1.next = node2 
>>> node2.next = node3 

Tham chiếu của nút thứ ba là None, điều này cho thấy nó đứng ở cuối danh sách. Bây giờ biểu đồ trạng thái có dạng:

Đến giờ bạn đã biết cách tạo ra nút rồi nối chúng lại thành danh sách. Có lẽ điều chưa rõ ràng là tại sao lại làm vậy.

Danh sách như những bộ sưu tập

Danh sách rất hữu ích vì chúng cho ta cách lắp ghép nhiều đối tượng vào trong cùng một thực thể, đôi khi được gọi là bộ sưu tập. Ở ví dụ này, nút thứ nhất trong danh sách đóng vai trò tham chiếu đối với toàn thể danh sách.

Để truyền danh sách làm đối số, ta chỉ cần truyền một tham chiếu đến nút thứ nhất. Chẳng hạn, hàm printList nhận đối số là một nút. Xuất phát từ đầu danh sách, hàm này sẽ in ra từng nút một cho tới khi đạt đến cuối danh sách:

def printList(node):
  while node: 
  print node, 
  node = node.next 
  print

Để kích hoạt hàm này, ta truyền một tham chiếu đến nút nhứ nhất:

>>> printList(node1)
 1 2 3

Bên trong printList ta có một tham chiếu đến nút thứ nhất của danh sách, nhưng không có biến nào tham chiếu đến các nút khác. Ta phải dùng giá trị next từ mỗi nút để đi sang nút tiếp theo.

Để duyệt một danh sách liên kết, ta thường dùng một biến vòng lặp như node để chỉ đến từng nút kế tiếp.

Biểu đồ sau cho thấy các nút trong danh sách và những giá trị mà node đó nhận:

Bài tập: Theo quy ước, danh sách thường được in trong cặp ngoặc vuông với dấu phẩy dùng để ngăn cách giữa các phần tử, như [1, 2, 3]. Hãy sửa lại printList để nó in được kết quả như định dạng này.

Danh sách và đệ quy

Việc biểu diễn nhiều phép toán bằng phương pháp đệ quy là rất tự nhiên. Chẳng hạn, sau đây là một thuận toán đệ quy để in danh sách theo thứ tự ngược lại:

  1. Chia danh sách làm hai phần: nút đầu (gọi là đầu) và phần còn lại (gọi là đuôi).
  2. In phần đuôi theo thứ tự ngược lại.
  3. In phần đầu.

Dĩ nhiên, để thực hiện Bước 2, lời gọi đệ quy, coi như ta đã phải có một cách in ngược danh sách. Nhưng nếu ta giả thiết rằng lời gọi đệ quy hoạt động được     theo niềm tin     thì ta có thể tự thuyết phục bản thân rằng thuật toán này sẽ có hiệu lực.

Tất cả những thứ ta cần chỉ là một trường hợp cơ sở và một cách để chứng minh rằng với một danh sách bất kì, ta cũng có thể trở về trường hợp cơ sở này. Cho trước định nghĩa đệ quy về danh sách, trường hợp cơ sở là danh sách rỗng, biểu diễn bởi None:

def printBackward(list):
  if list == None: return
  head = list
  tail = list.next
  printBackward(tail)
  print head,

Dòng đầu tiên xử lý trường hợp cơ sở bằng việc không làm gì cả. Hai dòng kế tiếp chia danh sách thành hai phần head và tail. Hai dòng sau cùng in danh sách ra. Dấu phẩy ở cuối dòng dưới cùng giữ cho Python khỏi xuống dòng sau khi in từng nút.

Ta kích hoạt hàm này như ta đã kích hoạt printList:

>>> printBackward(node1)
 3 2 1

Kết quả là một danh sách ngược.

Bạn có thể tự hỏi tại sao printList và printBackward là các hàm chứ không phải các phương thức trong lớp Node. Lí do là ta muốn dùng None để biểu diễn mọi danh sách rỗng và sẽ không hợp lệ nếu ta kích hoạt một phương thức đối với None. Điểm hạn chế này khiến cho việc viết mã lệnh thao tác với danh sách theo phong cách hướng đối tượng thuần túy là rất lủng củng.

Liệu ta có thể chứng minh rằng printBackward sẽ luôn kết thúc không? Nói cách khác, liệu nó có luôn đạt đến trường hợp cơ sở? Thật ra câu trả lời là không. Có một số danh sách làm cho hàm này đổ vỡ trong khi thực thi.

Danh sách vô hạn

Chẳng có cách gì buộc một nút không được tham chiếu trở lại một nút trước đó trong danh sách, và kể cả bản thân nó. Chẳng hạn, hình dưới đây cho thấy một danh sách gồm hai nút, trong một nút tham chiếu bản thân:

Nếu ta kích hoạt printList đối với danh sách này, nó sẽ lặp mãi. Nếu ta kích hoạt printBackward, nó sẽ đệ quy mãi. Dạng hành vi này khiến cho ta khó làm việc với danh sách vô hạn.

Dù sao, đôi khi danh sách vô hạn cũng có ích. Chẳng hạn, ta muốn biểu diễn một số dưới dạng danh sách các chữ số và dùng một danh sách vô hạn để biểu diễn cho phần thập phân được lặp lại mãi.

Bất chấp như vậy, rắc rối là ở chỗ ta không thể chứng minh được rằng printList và printBackward sẽ kết thúc. Cách tốt nhất mà ta có thể làm là theo lời phát biểu giả định, “Nếu danh sách không chứa vòng khép kín, thì những hàm này sẽ kết thúc.” Mệnh đề kiểu này được gọi là một điều kiện tiền đề. Nó đặt ra một ràng buộc đối với một trong các đối số và mô tả hành vi của hàm trong trường hợp ràng buộc này được thỏa mãn. Không lâu nữa bạn sẽ thấy thêm các ví dụ về điều này.

Định lý cơ bản về tính mơ hồ

Một đoạn mã trong printBackward có thể khiến bạn :

head = list
tail = list.next

Sau lệnh gán thứ nhất, head và list có cùng kiểu và cùng giá trị. Như vậy tại sao ta còn tạo ra một biến mới?

Lí do là hai biến này đóng các vai trò khác nhau. Ta hình dung head như là một tham chiếu đến một nút đơn lẻ, và list như một tham chiếu đến nút đầu tiên trong một danh sách. Những “vai trò” này không phải là bộ phận của chương trình, mà chỉ trong ý thức của người lập trình.

Nói chung, khi nhìn vào chương trình ta không thể biết được mỗi biến đóng vai trò gì. Sự mập mờ này có thể giúp ích, so nó cũng làm cho chương trình khó đọc hơn. Ta thường dùng những tên biến như node và list để cho thấy cách ta định dùng biến và đôi khi tạo ra những biến phụ trợ để làm rõ vấn đề hơn.

Ta cũng đã có thể viết printBackward mà không có cả head lẫn tail; cách này gọn hơn nhưng có lẽ kém rõ ràng:

def printBackward(list) :
  if list == None : return
  printBackward(list.next)
  print list,

Nhìn vào hai lời gọi hàm này, ta phải nhớ rằng printBackward coi đối số của nó như một bộ sưu tập còn print coi đối số của nó như một đối tượng đơn lẻ.

Định lý cơ bản về tính mơ hồ mô tả được sự mập mờ nội tại trong một tham chiếu đến một nút:

Một biến tham chiếu đến một nút thì có thể coi nút đó như một đối tượng đơn lẻ hoặc như một nút đầu tiên trong danh sách các nút.

Sửa đổi danh sách

Có hai cách để sửa đổi một danh sách liên kết. Dĩ nhiên, ta có thể sửa cargo của một trong các nút, nhưng các phép thao tác đáng quan tâm hơn bao gồm thêm, bớt, và đổi chỗ các nút.

Xét một ví dụ, ta cần viết một hàm để xóa bỏ nút thứ hai trong danh sách rồi trả lại một tham chiếu đến nút vừa bị xóa:

def removeSecond(list):
  if list == None: return
  first = list
  second = list.next
  # làm cho nút thứ nhất tham chiếu đến nút thứ ba
  first.next = second.next
  # tách nút thứ hai ra khỏi phần còn lại của danh sách 
  second.next = None
  return second

Một lần nữa, ta lại dùng các biến tạm để làm cho mã lệnh dễ đọc hơn. Sau đây là cách dùng hàm này:

>>> printList(node1)
 1 2 3
 >>> removed = removeSecond(node1)
 >>> printList(removed)
 2
 >>> printList(node1)
 1 3

Sơ đồ trạng thái dưới đây cho thấy hiệu ứng của thao tác trên:

Điều gì sẽ xảy ra nếu ta kích hoạt hàm này rồi truyền cho nó một danh sách chỉ gồm một phần tử (danh sách đơn độc)? Điều gì sẽ xảy ra nếu bạn truyền đối số là một danh sách rỗng? Liệu có một điều kiện tiền đề cho hàm này không? Nếu có, hãy sửa lại hàm để xử lí trường hợp vi phạm điều kiện tiền đề một cách hợp lí.

Phương thức bọc và phương thức trợ giúp

Thường có ích khi chia một thao tác trên danh sách ra làm hai phần. Chẳng hạn, để in một danh sách theo dạng mẫu [3 2 1] ta có thể dùng hàm printBackward để in ra 3 2 1 nhưng vẫn cần một hàm riêng để in cặp ngoặc vuông. Ta hãy gọi nó là printBackwardNicely:

def printBackwardNicely(list) :
  print "[",
  printBackward(list)
  print "]",

Lại một ý tưởng hay, đó là kiểm tra các hàm theo kiểu này để xem liệu chúng có hoạt động được với trường hợp đặc biệt như danh sách rỗng hoặc danh sách đơn độc không.

Khi dùng hàm này ở chỗ khác trong chương trình, ta kích hoạt trực tiếp printBackwardNicely, và nó lại kích hoạt printBackward thay ta. Theo cách này, printBackwardNicely đóng vai trò là một phương thức bọc, và nó sử dụng printBackward như một phương thức trợ giúp.

Lớp LinkedList

Còn một số vấn đề nhỏ trong cách ta đã thiết lập danh sách. Theo tinh thần đảo ngược nhân-quả, trước tiên chúng tôi sẽ đề xuất một cách làm khác rồi mới giải thích xem phương pháp dùng để giải quyết vấn đề nào.

Đầu tiên, ta sẽ tạo ra một lớp có tên LinkedList. Các thuộc tính của nó gồm một số nguyên chứa chiều dài của danh sách và một tham chiếu đến nút thứ nhất. Các đối tượng LinkedList đóng vai trò các chuôi để xử lí danh sách những đối tượng Node:

class LinkedList :
  def __init__(self) :
    self.length = 0
    self.head   = None

Một điểm hay của lớp LinkedList là nó cung cấp một nơi tự nhiên để đặt các hàm bọc như printBackwardNicely, từ đó ta có thể lập một phương thức của lớp LinkedList:

class LinkedList:
  ...
  def printBackward(self):
    print "[",
    if self.head != None:
    self.head.printBackward()
    print "]",
class Node:
  ...
  def printBackward(self):
    if self.next != None:
      tail = self.next
      tail.printBackward()
      print self.cargo,

Với mục đích gây nhầm lẫn, ta đổi tên printBackwardNicely. Bây giờ đã có hai phương thức printBackward: một nằm trong lớp Node (phương thức trợ giúp); và một trong lớp LinkedList (phương thức bao bọc). Khi phương thức bọc  kích hoạt self.head.printBackward, nó đã kích hoạt phương thức trợ giúp, vì self.head là một đối tượng Node.

Một ưu điểm nữa của lớp LinkedList là nó giúp thực hiện dễ dàng việc thêm bớt phần tử đầu tiên của danh sách. Chẳng hạn, addFirst là một phương thức của LinkedLists; nó nhận đối số là một thông tin trong cargo và đặt thông tin này lên đầu danh sách:

class LinkedList:
  ...
  def addFirst(self, cargo):
    node = Node(cargo)
    node.next = self.head
    self.head = node
    self.length = self.length + 1

Như thường lệ, bạn nên kiểm tra mã lệnh như thế này để xem liệu nó có xử lí được trường hợp đặc biệt không. Ví dụ, điều gì sẽ xảy ra nếu ban đầu danh sách trống rỗng?

Bất biến

Có danh sách được “tổ chức tốt”, cũng có danh sách thì không. Chẳng hạn, nếu danh sách có chứa một vòng lặp, nó sẽ làm nhiều phương thức trong đó bị đổ vỡ, do vậy có thể ta sẽ muốn yêu cầu rằng danh sách không được chứa vòng lặp. Một yêu cầu khác là giá trị length trong LinkedListobject phải bằng với số nút thực có trong danh sách.

Những yêu cầu như thế này được gọi là bất biến bởi vì tốt nhất là chúng phải đúng với mọi đối tượng trong mọi lúc. Việc chỉ định bất biến cho đối tượng là một kĩ năng lập trình có ích vì nó góp phần thuận tiện trong việc chứng minh tính đúng đắn của mã lệnh, kiểm tra tính thống nhất của cấu trúc dữ liệu, và phát hiện lỗi.

Một điều mà đôi khi gây nhầm lẫn về bất biến, đó là có những lúc bất biến bị vi phạm. Ví dụ, ở giữa phương thức addFirst, sau khi ta đã thêm nút vào nhưng trước khi ta tăng length, lúc này bất biến bị vi phạm. Trường hợp vi phạm như vậy thì chấp nhận được; thực ra nói chung thì không thể thay đổi một đối tượng nào mà không vi  phạm bất biến ít nhất là trong chốc lát. Thông thường, ta yêu cầu rằng phương pháp nào vi phạm một bất biến thì phải phục hồi bất biến đó.

Nếu có bất kì một đoạn dài mã lệnh vi phạm bất biến, thì phải ghi chú rõ ràng để không thực hiện phép tính nào có gắn với bất biến.

Thuật ngữ

tham chiếu nhúng
Một tham chiếu được lưu trữ trong thuộc tính của một đối tượng.
danh sách liên kết
Một cấu trúc dữ liệu nhằm tạo dựng một bộ sưu tập từ một dãy các nút được kết nối với nhau.
nút
Một phần tử của danh sách, thường được tạo dựng như một đối tượng có chứa tham chiếu đến đối tượng khác có cùng kiểu.
cargo
Một đơn vị thông tin chứa trong một nút.
đường kết nối
Một tham chiếu nhúng được dùng để nối từ đối tượng này sang đối tượng khác.
điều kiện tiền đề
Một mệnh đề phải được thỏa mãn để phương thức hoạt động đúng đắn.
định lí cơ bản về tính mơ hồ
Một tham chiếu đến một nút danh sách có thể được  reference to a list node can be treated as a single object or as the first in a list of nodes.
danh sách đơn độc
Danh sách kết nối chỉ có một nút.
phương thức bọc
Một phương thức đóng vai trò trung gian giữa phương thức gọi và phương thức trợ giúp, thường làm cho việc kích hoạt phương thức dễ dàng hơn và ít gây lỗi.
phương thức trợ giúp
Một phương thức không do phương thức gọi kích hoạt trực tiếp mà được phương thức khác sử dụng để thực hiện một phần việc tính toán.
bất biến
Một khẳng định cần duy trì tính đúng đắn với đối tượng trong mọi lúc (có lẽ chỉ trừ lúc đối tượng bị chỉnh sửa).

2 phản hồi

Filed under Think Python

2 responses to “Danh sách liên kết

  1. Pingback: Cách nghĩ như nhà khoa học máy tính | Blog của Chiến

  2. Pingback: Ngăn xếp | Blog của Chiến

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s