HomeLập trìnhPythonDanh sách được...

Danh sách được liên kết trong Python – Được giải thích bằng các ví dụ


Các ngôn ngữ lập trình khác nhau cung cấp các cách khác nhau để lưu trữ và truy cập dữ liệu.

Một số cấu trúc dữ liệu bạn có thể sử dụng là các tập hợp chẳng hạn như mảng, danh sách, bản đồ, tập hợp, v.v.

Tất cả những thứ này đều thực hiện công việc tuyệt vời là lưu trữ và truy cập dữ liệu, nhưng đôi khi bạn có thể cần thứ gì đó khác biệt. Một cấu trúc dữ liệu khác thường được sử dụng được gọi là Danh sách liên kết.

Danh sách liên kết là gì?

Danh sách được liên kết là một cấu trúc dữ liệu lưu trữ dữ liệu dưới dạng chuỗi. Cấu trúc của danh sách được liên kết sao cho mỗi phần dữ liệu có kết nối với phần tiếp theo (và đôi khi cả dữ liệu trước đó). Mỗi phần tử trong danh sách liên kết được gọi là một nút.

Bạn có thể coi nó như một chuỗi thực tế, trong đó mỗi vòng hoặc nút được kết nối với nhau.
Một cái gì đó như thế này

chuỗi chữ A

Giống như mọi cấu trúc dữ liệu khác, danh sách được liên kết có ưu và nhược điểm:

Ưu điểm của danh sách liên kết:

  1. Do hệ thống danh sách được liên kết giống như chuỗi, bạn có thể thêm và xóa các phần tử một cách nhanh chóng. Điều này cũng không yêu cầu tổ chức lại cấu trúc dữ liệu không giống như mảng hoặc danh sách. Cấu trúc dữ liệu tuyến tính thường dễ triển khai hơn bằng cách sử dụng danh sách được liên kết.
  2. Danh sách được liên kết cũng không yêu cầu kích thước cố định hoặc kích thước ban đầu do cấu trúc dạng chuỗi của chúng.

Nhược điểm của danh sách liên kết:

  1. Cần nhiều bộ nhớ hơn khi so sánh với một mảng. Điều này là do bạn cần một con trỏ (chiếm bộ nhớ của chính nó) để trỏ bạn đến phần tử tiếp theo.
  2. Hoạt động tìm kiếm trên một danh sách được liên kết là rất chậm. Không giống như một mảng, bạn không có tùy chọn truy cập ngẫu nhiên.

Khi nào bạn nên sử dụng danh sách liên kết?

Bạn nên sử dụng danh sách liên kết trên một mảng khi:

  1. Bạn không biết có bao nhiêu mục sẽ có trong danh sách (đó là một trong những lợi thế – dễ dàng thêm mục).
  2. Bạn không cần truy cập ngẫu nhiên vào bất kỳ phần tử nào (không giống như mảng, bạn không thể truy cập phần tử tại một chỉ mục cụ thể trong danh sách được liên kết).
  3. Bạn muốn có thể chèn các mục vào giữa danh sách.
  4. Bạn cần chèn/xóa thời gian liên tục khỏi danh sách (không giống như một mảng, trước tiên bạn không phải thay đổi mọi mục khác trong danh sách).
Đọc thêm  Thuộc tính Python – Ví dụ về thuộc tính lớp và trường hợp

Đây là một vài điều bạn nên xem xét trước khi thử triển khai danh sách được liên kết.

Bây giờ với tất cả các lý thuyết đã hết, đã đến lúc thực hiện một lý thuyết. Chúng ta sẽ làm điều này bằng Python, nhưng hầu hết những gì chúng ta tìm hiểu ở đây đều áp dụng cho bất kỳ ngôn ngữ nào bạn đang sử dụng. Điều quan trọng nhất là phải hiểu nó hoạt động như thế nào.

Cách sử dụng danh sách liên kết trong Python

Đây là một thủ thuật khi tạo Danh sách liên kết. Đó là thứ đã giúp tôi hiểu nó tốt hơn nhiều.

Bạn chỉ cần nhận ra rằng mọi mục mà bạn sẽ thêm vào danh sách chỉ là một nút (tương tự như một vòng trong chuỗi). Điều gì làm nên sự khác biệt của cái đầu (là nút đầu tiên trong danh sách) là bạn đã đặt cho nó tiêu đề cái đầuvà sau đó bạn bắt đầu thêm các nút khác vào đó.

Hãy nhớ rằng Danh sách được liên kết tương tự như cách một chuỗi được ghép nối với nhau.
Joe đang ở đây với vài chiếc nhẫn, và anh ấy sẽ giúp chúng ta.

Joe-and-the-chain

Tôi sẽ sử dụng điều này để minh họa khi chúng ta bắt đầu…vì vậy bạn có thể suy nghĩ theo những dòng này (đây không phải là một lớp nghệ thuật – tôi nhắc lại, đây không phải là một lớp nghệ thuật :)).

Vì vậy, trước tiên hãy tạo các nút:

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

Đó là nó. Chúng tôi thêm value bởi vì đối với bất kỳ thứ gì được thêm vào danh sách được liên kết, ít nhất nó phải có một số giá trị (ví dụ: ngoại trừ trong một số trường hợp hiếm gặp, bạn không thêm một chuỗi trống vào một mảng, phải không?).

Các next có nghĩa là có thể chúng ta muốn xâu chuỗi các nút khác – ý tôi là, đó là mục đích chính của danh sách được liên kết.

Tiếp theo chúng ta sẽ định nghĩa một số chức năng cơ bản:

class LinkedList:
	def __init__(self,head=None):
		self.head = head    
		def append(self, new_node):
            current = self.head
            if current:
                while current.next:
                    current = current.next
                current.next = new_node
            else:
                self.head = new_node

Các append() phương pháp cho phép bạn thêm một nút mới vào danh sách. Hãy khám phá cách thức hoạt động của nó.

nối thêm

Nếu tôi có hai giá trị – giả sử 1 và 2 – và tôi muốn thêm chúng vào danh sách, điều đầu tiên là xác định chúng dưới dạng các nút riêng lẻ (nghĩa là dưới dạng các vòng của chuỗi). tôi có thể làm điều đó như thế này:

e1 = Node(1)
e2 = Node(2)

Bây giờ tôi có thể định nghĩa một danh sách được liên kết vì tôi đã có sẵn các nút của mình. Một danh sách được liên kết (giống như các chuỗi chúng ta thấy – luôn có phần đầu, phải không?), vì vậy tôi có thể xác định danh sách được liên kết của mình với một giá trị phần đầu mà về cơ bản chỉ là một nút (vòng) khác:

ll = LinkedList(e1)

Bây giờ từ đoạn mã trên, e1 là phần đầu của danh sách được liên kết, đây chỉ là một cách nói hoa mỹ về điểm bắt đầu của danh sách được liên kết của tôi. Tôi có thể thêm nhiều mục hơn vào nó và vì mỗi chuỗi phải được kết nối (nghĩa là bên trong nhau), trước tiên tôi phải thiết lập trường hợp cơ sở để kiểm tra xem danh sách có phần đầu hay không.

Đọc thêm  Cách xóa một ký tự cụ thể khỏi chuỗi trong Python

Điều tạo nên một danh sách liên kết là nó có một điểm bắt đầu. Nếu không, chúng ta chỉ cần đặt phần tử mới vào phần đầu. Nhưng nếu nó đã có phần đầu, tôi phải xem qua toàn bộ danh sách và tiếp tục kiểm tra xem có nút nào có phần đầu không. next trống rỗng (nghĩa là None).

Một lần nữa, một danh sách được liên kết giống như một chuỗi, phải không? Vì vậy, mọi nút nên trỏ đến nút khác với next con trỏ. Khi một nút có nút tiếp theo đó là none, nó đơn giản có nghĩa là nó ở cuối danh sách. Vì vậy, tôi có thể dễ dàng thêm nút mới vào vị trí đó.

Hãy tạo một phương thức để xóa bỏ một nút. Nhưng trước khi làm, chúng ta hãy suy nghĩ về nó trong một giây. Hãy tưởng tượng bạn có một sợi dây xích và bạn phát hiện ra một chiếc nhẫn yếu. Bạn làm nghề gì?

Trước tiên, bạn tìm chiếc nhẫn yếu, sau đó bạn tháo nó ra và kết nối chiếc nhẫn trước và sau nó lại với nhau. Nhưng nếu vòng yếu là vòng đầu tiên, điều đó thật dễ dàng – bạn chỉ cần gỡ bỏ nó và không thực sự phải tham gia bất cứ thứ gì. Vòng thứ hai tự động trở thành đầu của chuỗi. Hãy thử hình dung điều đó.

Chúng tôi muốn làm điều tương tự ở đây. Vì vậy, trước tiên chúng tôi tìm vòng yếu – trong trường hợp này sẽ là giá trị mà chúng tôi đang tìm kiếm – và sau đó chúng tôi sẽ lấy cái trước và cái sau và nối chúng lại với nhau:

class LinkedList:    
	def __init(...)    
	def append(...)    
	  def delete(self, value):
        """Delete the first node with a given value."""
        current = self.head
        if current.value == value:
            self.head = current.next
        else:
            while current:
                if current.value == value:
                    break
                prev = current
                current = current.next
            if current == None:
                return
            prev.next = current.next
            current = None

Vì vậy, những gì chúng tôi đang làm ở đây chỉ đơn giản là đi qua từng nút để xem liệu đó có phải là giá trị mà chúng tôi muốn xóa hay không. Nhưng khi di chuyển qua danh sách, chúng ta phải theo dõi giá trị trước đó (chúng ta vẫn phải nối danh sách lại với nhau). Chúng tôi làm điều này với prev = current như bạn có thể thấy ở trên hoặc dưới :).

xóa-1

Vì vậy, khi nút đã được tìm thấy, prev chứa nút trước nó, có thể dễ dàng chuyển đổi (nghĩa là giá trị tiếp theo) để trỏ đến một nút khác – trong trường hợp này là các nút khác được kết nối với nút mà chúng tôi muốn xóa. Tôi hy vọng điều này có ý nghĩa :).

Đọc thêm  Tôi đã chuyển từ C++ sang Python như thế nào: một sự thay đổi về khái niệm

chúng ta hãy làm việc trên chèn một nút vào một vị trí cụ thể. Chúng tôi sẽ sử dụng phép loại suy chuỗi của chúng tôi để hiểu điều này tốt hơn.

Khi bạn cầm một sợi xích và thực sự muốn tăng chiều dài của sợi xích, bạn có ba lựa chọn. Bạn có thể:

  1. Thêm một liên kết (phần tử) vào đầu chuỗi (điều này khá đơn giản phải không?)
  2. Thêm nó vào cuối chuỗi (tương tự như 1)
  3. Hoặc bạn có thể thêm nó vào bất kỳ điểm nào ở giữa (phức tạp hơn một chút)

chèn3

Một điều bạn nên ghi nhớ là bất cứ nơi nào bạn quyết định thêm nó vào, bạn phải nối các nút khác lại với nó. Điều đó chỉ khả thi nếu bạn theo dõi các nút khác bằng một vòng lặp.

Hãy xem điều đó trong hành động:

	class LinkedList:   
	def __init(...)    
	def append(...) 
    def delete(...)
    def insert(self, new_element, position):
        """Insert a new node at the given position.
        Assume the first position is "1".
        Inserting at position 3 means between
        the 2nd and 3rd elements."""
        count=1
        current = self.head
        if position == 1:
            new_element.next = self.head
            self.head = new_element
        while current:
            if count+1 == position:
                new_element.next =current.next
                current.next = new_element
                return
            else:
                count+=1
                current = current.next
            # break

        pass

Chúng tôi được cung cấp một vị trí để chèn nút trong mã ở trên. Nếu vị trí là một, có nghĩa là nó sẽ là gốc. Vì chúng tôi không chắc chắn lắm, chúng tôi có thể khởi tạo một vòng lặp và bộ đếm để theo dõi vòng lặp.

Nếu vị trí chúng ta chèn là một (nghĩa là gốc), chỉ cần lưu gốc hiện tại vào một biến giả, tạo một gốc mới, sau đó thêm gốc trước đó (nghĩa là toàn bộ chuỗi) vào gốc mới này .

Nếu vị trí không phải là một, hãy tiếp tục đi qua chuỗi cho đến khi bạn tìm thấy vị trí đó.

Cuối cùng đối với bài viết này, chúng ta hãy làm việc để hiển thị các giá trị của danh sách được liên kết của chúng ta ở bất kỳ định dạng nào bạn muốn – ví dụ: in nó ra hoặc thêm nó vào bộ sưu tập danh sách. Tôi sẽ chỉ in các giá trị ra.

Điều này khá đơn giản, tương tự như chuỗi vật lý: bạn chỉ cần nhìn qua mọi nơi có một nút và lấy giá trị, sau đó chuyển sang nút tiếp theo:

in
class LinkedList:   
	def __init(...)    
	def append(...) 
    def insert(...)
	def delete(...)    
	def print(self):
        current = self.head
        while current:
            print(current.value)
            current = current.next
    

Vì vậy, đó là tất cả trên danh sách được liên kết cho bây giờ! Chúng ta sẽ giải một số câu hỏi về danh sách liên kết sau này.

kết thúc

Trong bài viết này, tôi đã giải thích:

  • Cách hoạt động của danh sách liên kết
  • Ưu nhược điểm của danh sách liên kết
  • Cách triển khai danh sách liên kết với Python

Bạn có thể tìm thấy mã cho bài viết này ở đây. Cảm ơn bạn đã đọc.



Zik.vn – Biên dịch & Biên soạn Lại

spot_img

Create a website from scratch

Just drag and drop elements in a page to get started with Newspaper Theme.

Buy Now ⟶

Bài viết liên quang

DMCA.com Protection Status