Cụ thể là có xung đột khi tạo danh sách, nếu ListNode là một danh sách thì việc tạo danh sách sẽ được thực hiện bằng cách gọi ListNode nhưng sau đó bạn tạo một nút như thế nào…
Tôi có thể lấy một danh sách và chỉ định toàn bộ nội dung được liên kết không?
ừm. hãy nhớ rằng cấu trúc của bạn khác với cấu trúc của danh sách python. Nếu bạn giữ toàn bộ danh sách thì bạn không có cấu trúc của mình, vì vậy không, đó sẽ không phải là danh sách được liên kết phải không?
Hãy nhớ rằng mục đích của việc tạo kiểu danh sách liên kết là để hiển thị các thao tác. Thông qua họ, bạn sẽ thực hiện chuyển đổi. Và chính nhờ họ mà bạn sẽ sử dụng danh sách. Và sử dụng danh sách có thể liên quan đến việc tạo danh sách
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ả đề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 một cái gì đó khác. 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.
Đại loại như thế này
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 của chúng
Ưu điểm của danh sách liên kết
- Do hệ thống danh sách 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
- 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
- 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
- Thao tác tìm kiếm trên danh sách liên kết 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
- 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]
- 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]
- Bạn muốn có thể chèn các mục vào giữa danh sách
- 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]
Đâ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ả lý thuyết đã hết, đã đến lúc thực hiện mộ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à điều đã 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ểm khác biệt của phần đầu [là nút đầu tiên trong danh sách] là bạn đã đặt cho nó phần đầu tiêu đề và 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.
Tôi sẽ sử dụng điều này để minh họa khi chúng ta đi. để 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
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_nodeclass 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_nodeTiế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
Phương thức
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_nodeNế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,
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Đ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 đầ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ó
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_nodeclass 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_nodeMột lần nữa, danh sách được liên kết giống như một chuỗi, phải không? . Khi một nút có nút tiếp theo là
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_nodeHãy tạo một phương thức để xóa một nút. Nhưng trước khi làm, hãy nghĩ về nó trong giây lát. 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à nối chiếc trước và chiếc sau 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 xóa nó và không thực sự phải tham gia bất kỳ 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 = NoneVì 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 chúng tôi di chuyển qua danh sách, chúng tôi phải theo dõi giá trị trước đó [chúng tôi vẫn phải nối lại danh sách với nhau]. Chúng tôi làm điều này với
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_nodeVì vậy, khi nút đã được tìm thấy,
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_nodeHãy thực hiện việc 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 giữ một sợi xích và bạn 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ể
- 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?]
- Thêm nó vào cuối chuỗi [tương tự như 1]
- 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]
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ó, bạn phải nối các nút khác trở 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__[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_nodeChú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 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 bắt đầu 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 ra hoặc thêm danh sách đó 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
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_nodeVì vậy, đó là tất cả trên danh sách được liên kết cho đến bây giờ. Chúng tôi sẽ làm việc để giải quyết một số câu hỏi về danh sách được 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
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
Đọc thêm bài viết
Nếu bài viết này hữu ích, hãy tweet nó
Học cách viết mã miễn phí. Chương trình giảng dạy mã nguồn mở của freeCodeCamp đã giúp hơn 40.000 người có được việc làm với tư cách là nhà phát triển. Bắt đầu