search

Danh sách Python có phải là số 1 không?

Ngày đăng: 02/01/2023
Trả lời: 0
Lượt xem: 150

Danh sách được liên kết giống như một người anh em họ ít được biết đến của danh sách. Chúng không phổ biến hay thú vị bằng và thậm chí bạn có thể không nhớ chúng từ lớp thuật toán của mình. Nhưng trong bối cảnh phù hợp, họ thực sự có thể tỏa sáng

Show

Trong bài viết này, bạn sẽ học

  • Danh sách được liên kết là gì và khi nào bạn nên sử dụng chúng
  • Cách sử dụng 
    >>> deque(['a','b','c'])
deque(['a', 'b', 'c'])

>>> deque('abc')
deque(['a', 'b', 'c'])

>>> deque([{'data': 'a'}, {'data': 'b'}])
deque([{'data': 'a'}, {'data': 'b'}])
    9 cho tất cả các nhu cầu về danh sách được liên kết của bạn
  • Cách triển khai danh sách được liên kết của riêng bạn
  • Các loại danh sách được liên kết khác là gì và chúng có thể được sử dụng để làm gì

Nếu bạn đang tìm cách cải thiện kỹ năng mã hóa của mình để phỏng vấn xin việc hoặc nếu bạn muốn tìm hiểu thêm về cấu trúc dữ liệu Python bên cạnh các từ điển và danh sách thông thường, thì bạn đã đến đúng nơi

Bạn có thể làm theo các ví dụ trong hướng dẫn này bằng cách tải xuống mã nguồn có sẵn tại liên kết bên dưới

Lấy mã nguồn. Nhấp vào đây để lấy mã nguồn mà bạn sẽ sử dụng để tìm hiểu về danh sách được liên kết trong hướng dẫn này

Hiểu danh sách liên kết

Danh sách liên kết là một tập hợp các đối tượng được sắp xếp theo thứ tự. Vậy điều gì làm cho chúng khác với danh sách bình thường? . Trong khi các danh sách sử dụng một khối bộ nhớ liền kề để lưu trữ các tham chiếu đến dữ liệu của chúng, thì các danh sách được liên kết lưu trữ các tham chiếu như một phần của các phần tử riêng của chúng.

Loại bỏ các quảng cáo

Khái niệm chính

Trước khi tìm hiểu sâu hơn về danh sách được liên kết là gì và cách bạn có thể sử dụng chúng, trước tiên bạn nên tìm hiểu cách chúng được cấu trúc. Mỗi phần tử của danh sách liên kết được gọi là một nút và mỗi nút có hai trường khác nhau

  1. Dữ liệu chứa giá trị được lưu trữ trong nút
  2. Tiếp theo chứa một tham chiếu đến nút tiếp theo trong danh sách

Đây là một nút điển hình trông như thế nào

Danh sách Python có phải là số 1 không?
Nút

Danh sách liên kết là tập hợp các nút. Nút đầu tiên được gọi là 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
0 và nó được sử dụng làm điểm bắt đầu cho bất kỳ lần lặp nào trong danh sách. Nút cuối cùng phải có tham chiếu 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
1 trỏ đến 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
2 để xác định phần cuối của danh sách. Đây là giao diện của nó

Danh sách Python có phải là số 1 không?
Danh sách liên kết

Bây giờ bạn đã biết cách cấu trúc danh sách được liên kết, bạn đã sẵn sàng xem xét một số trường hợp sử dụng thực tế cho danh sách đó

Ứng dụng thực tế

Danh sách được liên kết phục vụ nhiều mục đích khác nhau trong thế giới thực. Chúng có thể được sử dụng để thực hiện (cảnh báo spoiler. ) hàng đợi hoặc ngăn xếp cũng như đồ thị. Chúng cũng hữu ích cho các tác vụ phức tạp hơn nhiều, chẳng hạn như quản lý vòng đời cho một ứng dụng hệ điều hành

Hàng đợi hoặc ngăn xếp

Hàng đợi và ngăn xếp chỉ khác nhau ở cách truy xuất các phần tử. Đối với hàng đợi, bạn sử dụng phương pháp Nhập trước/Xuất trước (FIFO). Điều đó có nghĩa là phần tử đầu tiên được chèn vào danh sách là phần tử đầu tiên được truy xuất

Danh sách Python có phải là số 1 không?
Xếp hàng

Trong sơ đồ trên, bạn có thể thấy các phần tử phía trước và phía sau của hàng đợi. Khi bạn thêm các phần tử mới vào hàng đợi, chúng sẽ chuyển đến phần cuối. Khi bạn truy xuất các phần tử, chúng sẽ được lấy từ đầu hàng đợi

Đối với ngăn xếp, bạn sử dụng phương pháp Nhập sau/Xuất trước (LIFO), nghĩa là phần tử cuối cùng được chèn vào danh sách là phần tử đầu tiên được truy xuất

Danh sách Python có phải là số 1 không?
Cây rơm

Trong sơ đồ trên, bạn có thể thấy rằng phần tử đầu tiên được chèn vào ngăn xếp (chỉ số 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
3) ở dưới cùng và phần tử cuối cùng được chèn vào ở trên cùng. Vì các ngăn xếp sử dụng phương pháp LIFO, nên phần tử cuối cùng được chèn (ở trên cùng) sẽ là phần tử đầu tiên được truy xuất

Do cách bạn chèn và truy xuất các phần tử từ các cạnh của hàng đợi và ngăn xếp, danh sách được liên kết là một trong những cách thuận tiện nhất để triển khai các cấu trúc dữ liệu này. Bạn sẽ thấy các ví dụ về các triển khai này sau trong bài viết

đồ thị

Đồ thị có thể được sử dụng để hiển thị mối quan hệ giữa các đối tượng hoặc để biểu thị các loại mạng khác nhau. Ví dụ: biểu diễn trực quan của biểu đồ—giả sử biểu đồ tuần hoàn có hướng (DAG)—có thể trông như thế này

Danh sách Python có phải là số 1 không?
Đồ thị tuần hoàn có hướng

Có nhiều cách khác nhau để triển khai các biểu đồ như trên, nhưng một trong những cách phổ biến nhất là sử dụng danh sách kề. Về bản chất, một danh sách kề là một danh sách các danh sách được liên kết trong đó mỗi đỉnh của đồ thị được lưu trữ cùng với một tập hợp các đỉnh được kết nối

VertexLinked Danh sách các đỉnh12 → 3 → Không có24 → Không có3None45 → 6 → Không có56 → Không có6None

Trong bảng trên, mỗi đỉnh của đồ thị của bạn được liệt kê ở cột bên trái. Cột bên phải chứa dãy danh sách liên kết chứa các đỉnh khác được nối với đỉnh tương ứng ở cột bên trái. Danh sách kề này cũng có thể được biểu diễn bằng mã bằng cách sử dụng 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
4

>>> 

>>> graph = {
..     1: [2, 3, None],
..     2: [4, None],
..     3: [None],
..     4: [5, 6, None],
..     5: [6, None],
..     6: [None]
.. }

Các khóa của từ điển này là các đỉnh nguồn và giá trị cho mỗi khóa là một danh sách. Danh sách này thường được triển khai dưới dạng danh sách liên kết

Ghi chú. Trong ví dụ trên, bạn có thể tránh lưu trữ các giá trị 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
2, nhưng chúng tôi đã giữ lại chúng ở đây để làm rõ và nhất quán với các ví dụ sau

Về cả tốc độ và bộ nhớ, việc triển khai biểu đồ bằng danh sách kề rất hiệu quả so với, chẳng hạn như ma trận kề. Đó là lý do tại sao danh sách được liên kết rất hữu ích cho việc triển khai biểu đồ

Loại bỏ các quảng cáo

So sánh hiệu suất. Danh sách so với Danh sách được liên kết

Trong hầu hết các ngôn ngữ lập trình, có sự khác biệt rõ ràng trong cách danh sách liên kết và mảng được lưu trữ trong bộ nhớ. Tuy nhiên, trong Python, danh sách là. Điều đó có nghĩa là việc sử dụng bộ nhớ của cả danh sách và danh sách được liên kết là rất giống nhau

đọc thêm. Việc triển khai các mảng động của Python khá thú vị và chắc chắn đáng để đọc. Hãy chắc chắn rằng bạn đã xem qua và sử dụng kiến ​​thức đó để trở nên nổi bật trong bữa tiệc tiếp theo của công ty bạn

Vì sự khác biệt về mức sử dụng bộ nhớ giữa danh sách và danh sách được liên kết là không đáng kể, nên sẽ tốt hơn nếu bạn tập trung vào sự khác biệt về hiệu suất của chúng khi nói đến độ phức tạp về thời gian

Chèn và xóa phần tử

Trong Python, bạn có thể chèn các phần tử vào danh sách bằng cách sử dụng 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
6 hoặc 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
7. Để xóa các phần tử khỏi danh sách, bạn có thể sử dụng các đối tác của chúng. 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
8 và 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
9

Sự khác biệt chính giữa các phương pháp này là bạn sử dụng 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
6 và 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
8 để chèn hoặc xóa phần tử tại một vị trí cụ thể trong danh sách, nhưng bạn chỉ sử dụng 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
7 và 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
9 để chèn hoặc xóa phần tử ở cuối danh sách

Bây giờ, một điều bạn cần biết về danh sách Python là việc chèn hoặc xóa các phần tử không ở cuối danh sách yêu cầu một số phần tử dịch chuyển trong nền, khiến thao tác trở nên phức tạp hơn về mặt thời gian. Bạn có thể đọc bài viết được đề cập ở trên về cách triển khai danh sách trong Python để hiểu rõ hơn cách triển khai 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
6, 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
8, 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
7 và 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
9 ảnh hưởng đến hiệu suất của chúng

Với tất cả những điều này, mặc dù việc chèn các phần tử vào cuối danh sách bằng cách sử dụng 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
7 hoặc 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
6 sẽ có thời gian không đổi, O(1), khi bạn cố gắng chèn một phần tử gần hơn hoặc vào đầu danh sách, độ phức tạp của thời gian trung bình . Trên)

Mặt khác, các danh sách được liên kết đơn giản hơn nhiều khi chèn và xóa các phần tử ở đầu hoặc cuối danh sách, trong đó độ phức tạp về thời gian của chúng luôn không đổi. Ô(1)

Vì lý do này, danh sách được liên kết có lợi thế về hiệu suất so với danh sách thông thường khi triển khai hàng đợi (FIFO), trong đó các phần tử liên tục được chèn và xóa ở đầu danh sách. Nhưng chúng hoạt động tương tự như một danh sách khi triển khai ngăn xếp (LIFO), trong đó các phần tử được chèn và xóa ở cuối danh sách

Truy xuất các phần tử

Khi nói đến tra cứu phần tử, danh sách hoạt động tốt hơn nhiều so với danh sách được liên kết. Khi bạn biết phần tử nào bạn muốn truy cập, danh sách có thể thực hiện thao tác này trong thời gian O(1). Cố gắng làm điều tương tự với danh sách được liên kết sẽ mất O(n) vì bạn cần duyệt qua toàn bộ danh sách để tìm phần tử

Tuy nhiên, khi tìm kiếm một phần tử cụ thể, cả danh sách và danh sách được liên kết đều hoạt động rất giống nhau, với độ phức tạp về thời gian là O(n). Trong cả hai trường hợp, bạn cần lặp lại toàn bộ danh sách để tìm phần tử mà bạn đang tìm kiếm

Giới thiệu >>> deque(['a','b','c']) deque(['a', 'b', 'c']) >>> deque('abc') deque(['a', 'b', 'c']) >>> deque([{'data': 'a'}, {'data': 'b'}]) deque([{'data': 'a'}, {'data': 'b'}]) 9

Trong Python, có một đối tượng cụ thể trong mô-đun 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
31 mà bạn có thể sử dụng cho các danh sách được liên kết được gọi là (phát âm là “deck”), viết tắt của hàng đợi hai đầu

>>> deque(['a','b','c'])
deque(['a', 'b', 'c'])

>>> deque('abc')
deque(['a', 'b', 'c'])

>>> deque([{'data': 'a'}, {'data': 'b'}])
deque([{'data': 'a'}, {'data': 'b'}])
9 sử dụng triển khai danh sách được liên kết trong đó bạn có thể truy cập, chèn hoặc xóa các phần tử từ đầu hoặc cuối danh sách với hiệu suất O(1) không đổi

Cách sử dụng >>> deque(['a','b','c']) deque(['a', 'b', 'c']) >>> deque('abc') deque(['a', 'b', 'c']) >>> deque([{'data': 'a'}, {'data': 'b'}]) deque([{'data': 'a'}, {'data': 'b'}]) 9

Theo mặc định, có khá nhiều thứ đi kèm với một đối tượng 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
34. Tuy nhiên, trong bài viết này, bạn sẽ chỉ chạm vào một vài trong số chúng, chủ yếu là để thêm hoặc xóa các phần tử

Đầu tiên, bạn cần tạo một danh sách liên kết. Bạn có thể sử dụng đoạn mã sau để làm điều đó với 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
34

>>> 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
8

Đoạn mã trên sẽ tạo một danh sách liên kết rỗng. Nếu bạn muốn điền nó khi tạo, thì bạn có thể cung cấp cho nó một lần lặp làm đầu vào

>>> 

>>> deque(['a','b','c'])
deque(['a', 'b', 'c'])

>>> deque('abc')
deque(['a', 'b', 'c'])

>>> deque([{'data': 'a'}, {'data': 'b'}])
deque([{'data': 'a'}, {'data': 'b'}])

Khi khởi tạo một đối tượng 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
34, bạn có thể chuyển bất kỳ lần lặp nào làm đầu vào, chẳng hạn như một chuỗi (cũng là một lần lặp) hoặc danh sách các đối tượng

Bây giờ bạn đã biết cách tạo một đối tượng 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
34, bạn có thể tương tác với nó bằng cách thêm hoặc bớt các phần tử. Bạn có thể tạo danh sách liên kết 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
38 và thêm phần tử mới 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
39 như thế này

>>> 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

Cả 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
50 và 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
51 đều thêm hoặc xóa các phần tử ở phía bên phải của danh sách được liên kết. Tuy nhiên, bạn cũng có thể sử dụng 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
34 để nhanh chóng thêm hoặc xóa các phần tử ở phía bên trái hoặc 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
0 của danh sách

>>> 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
9

Việc thêm hoặc xóa các phần tử ở cả hai đầu danh sách khá đơn giản bằng cách sử dụng đối tượng 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
34. Bây giờ bạn đã sẵn sàng học cách sử dụng 
>>> deque(['a','b','c'])
deque(['a', 'b', 'c'])

>>> deque('abc')
deque(['a', 'b', 'c'])

>>> deque([{'data': 'a'}, {'data': 'b'}])
deque([{'data': 'a'}, {'data': 'b'}])
9 để triển khai hàng đợi hoặc ngăn xếp

Loại bỏ các quảng cáo

Cách triển khai hàng đợi và ngăn xếp

Như bạn đã học ở trên, sự khác biệt chính giữa hàng đợi và ngăn xếp là cách bạn truy xuất các phần tử từ mỗi. Tiếp theo, bạn sẽ tìm hiểu cách sử dụng 

>>> deque(['a','b','c'])
deque(['a', 'b', 'c'])

>>> deque('abc')
deque(['a', 'b', 'c'])

>>> deque([{'data': 'a'}, {'data': 'b'}])
deque([{'data': 'a'}, {'data': 'b'}])
9 để triển khai cả hai cấu trúc dữ liệu

hàng đợi

Với hàng đợi, bạn muốn thêm giá trị vào danh sách (

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
57) và khi đúng thời điểm, bạn muốn xóa phần tử đã có trong danh sách lâu nhất (
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
58). Ví dụ, hãy tưởng tượng một hàng đợi tại một nhà hàng thời thượng và đã được đặt kín chỗ. Nếu bạn đang cố triển khai một hệ thống sắp xếp chỗ ngồi hợp lý cho khách, thì bạn nên bắt đầu bằng cách tạo một hàng đợi và thêm người khi họ đến.

>>> 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
3

Bây giờ bạn có Mary, John và Susan trong hàng đợi. Hãy nhớ rằng vì hàng đợi là FIFO, nên người đầu tiên vào hàng đợi sẽ là người đầu tiên ra khỏi hàng đợi

Bây giờ hãy tưởng tượng một thời gian trôi qua và một số bảng có sẵn. Ở giai đoạn này, bạn muốn xóa mọi người khỏi hàng đợi theo đúng thứ tự. Đây là cách bạn sẽ làm điều đó

>>> 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
5

Mỗi khi bạn gọi 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
59, bạn sẽ xóa phần tử đầu khỏi danh sách được liên kết, bắt chước một hàng đợi ngoài đời thực

ngăn xếp

Thay vào đó, nếu bạn muốn tạo một ngăn xếp thì sao? . Sự khác biệt duy nhất là ngăn xếp sử dụng phương pháp LIFO, nghĩa là phần tử cuối cùng được chèn vào ngăn xếp sẽ là phần tử đầu tiên bị loại bỏ

Hãy tưởng tượng bạn đang tạo chức năng lịch sử của trình duyệt web, trong đó lưu trữ mọi trang mà người dùng truy cập để họ có thể quay ngược thời gian một cách dễ dàng. Giả sử đây là những hành động mà một người dùng ngẫu nhiên thực hiện trên trình duyệt của họ

  1. Truy cập trang web của Real Python
  2. Điều hướng đến Pandas. Cách đọc và ghi tệp
  3. Nhấp vào liên kết để đọc và ghi tệp CSV bằng Python

Nếu bạn muốn ánh xạ hành vi này thành một ngăn xếp, thì bạn có thể làm điều gì đó như thế này

>>> 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
8

Trong ví dụ này, bạn đã tạo một đối tượng 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
80 trống và mỗi khi người dùng truy cập một trang web mới, bạn đã thêm nó vào biến 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
80 của mình bằng cách sử dụng 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
82. Làm như vậy đảm bảo rằng mỗi phần tử mới đã được thêm vào 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
0 của danh sách được liên kết

Bây giờ, giả sử rằng sau khi người dùng đọc cả hai bài viết, họ muốn quay lại trang chủ Real Python để chọn một bài viết mới để đọc. Biết rằng bạn có một ngăn xếp và muốn xóa các phần tử bằng LIFO, bạn có thể làm như sau

>>> 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
3

của bạn đi. Sử dụng 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
59, bạn đã xóa các phần tử khỏi 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
0 của danh sách được liên kết cho đến khi bạn truy cập trang chủ Real Python

Từ các ví dụ trên, bạn có thể thấy việc có 

>>> deque(['a','b','c'])
deque(['a', 'b', 'c'])

>>> deque('abc')
deque(['a', 'b', 'c'])

>>> deque([{'data': 'a'}, {'data': 'b'}])
deque([{'data': 'a'}, {'data': 'b'}])
9 trong hộp công cụ của mình hữu ích như thế nào, vì vậy hãy đảm bảo sử dụng nó vào lần tiếp theo khi bạn có một thử thách dựa trên hàng đợi hoặc ngăn xếp cần giải quyết

Loại bỏ các quảng cáo

Triển khai danh sách liên kết của riêng bạn

Bây giờ bạn đã biết cách sử dụng 

>>> deque(['a','b','c'])
deque(['a', 'b', 'c'])

>>> deque('abc')
deque(['a', 'b', 'c'])

>>> deque([{'data': 'a'}, {'data': 'b'}])
deque([{'data': 'a'}, {'data': 'b'}])
9 để xử lý các danh sách được liên kết, bạn có thể tự hỏi tại sao bạn lại triển khai danh sách được liên kết của riêng mình trong Python. Có một vài lý do để làm điều đó

  1. Thực hành các kỹ năng thuật toán Python của bạn
  2. Tìm hiểu về lý thuyết cấu trúc dữ liệu
  3. Chuẩn bị cho các cuộc phỏng vấn việc làm

Vui lòng bỏ qua phần tiếp theo này nếu bạn không quan tâm đến bất kỳ điều nào ở trên hoặc nếu bạn đã thành công trong việc triển khai danh sách liên kết của riêng mình trong Python. Mặt khác, đã đến lúc triển khai một số danh sách được liên kết

Cách tạo danh sách liên kết

Trước tiên, hãy tạo một lớp để đại diện cho danh sách được liên kết của bạn

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
8

Thông tin duy nhất bạn cần lưu trữ cho danh sách được liên kết là nơi danh sách bắt đầu (_____10 của danh sách). Tiếp theo, tạo một lớp khác để đại diện cho từng nút của danh sách được liên kết

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
80

Trong định nghĩa lớp trên, bạn có thể thấy hai phần tử chính của mỗi nút đơn. 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
89 và 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
1. Bạn cũng có thể thêm một 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
31 vào cả hai lớp để có một biểu diễn hữu ích hơn về các đối tượng

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
81

Hãy xem một ví dụ về việc sử dụng các lớp trên để tạo nhanh một danh sách liên kết có ba nút

>>> 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
82

Bằng cách xác định các giá trị 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
89 và 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
1 của một nút, bạn có thể tạo một danh sách được liên kết khá nhanh chóng. Các lớp 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
34 và 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
35 này là điểm khởi đầu cho việc triển khai của chúng tôi. Từ giờ trở đi, tất cả chỉ là tăng chức năng của chúng

Đây là một thay đổi nhỏ đối với danh sách được liên kết của 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
36 cho phép bạn nhanh chóng tạo danh sách được liên kết với một số dữ liệu

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
83

Với sửa đổi trên, việc tạo danh sách liên kết để sử dụng trong các ví dụ bên dưới sẽ nhanh hơn rất nhiều

Cách duyệt qua một danh sách được liên kết

Một trong những điều phổ biến nhất bạn sẽ làm với một danh sách được liên kết là duyệt qua nó. Đi ngang có nghĩa là đi qua từng nút đơn lẻ, bắt đầu bằng 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
0 của danh sách được liên kết và kết thúc ở nút có giá trị 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
1 là 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
2

Di chuyển ngang chỉ là một cách thú vị hơn để nói lặp đi lặp lại. Vì vậy, với ý nghĩ đó, hãy tạo một 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
80 để thêm hành vi tương tự vào danh sách được liên kết mà bạn mong đợi từ một danh sách bình thường

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
84

Phương thức trên đi qua danh sách và mang lại mọi nút đơn. Điều quan trọng nhất cần nhớ về 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
80 này là bạn cần luôn xác thực rằng 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
82 hiện tại không phải là 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
2. Khi điều kiện đó là 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
84, điều đó có nghĩa là bạn đã đến cuối danh sách được liên kết của mình

Sau khi kết quả nút hiện tại, bạn muốn chuyển sang nút tiếp theo trong danh sách. Đó là lý do tại sao bạn thêm 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
85. Đây là một ví dụ về việc duyệt qua một danh sách ngẫu nhiên và in từng nút

>>> 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
85

Trong các bài viết khác, bạn có thể thấy việc di chuyển ngang được định nghĩa thành một phương thức cụ thể có tên là 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
86. Tuy nhiên, việc sử dụng các phương thức tích hợp sẵn của Python để đạt được hành vi đã nói làm cho việc triển khai danh sách được liên kết này trở nên Pythonic hơn một chút

Loại bỏ các quảng cáo

Cách chèn một nút mới

Có nhiều cách khác nhau để chèn các nút mới vào danh sách được liên kết, mỗi cách có cách triển khai và mức độ phức tạp riêng. Đó là lý do tại sao bạn sẽ thấy chúng được chia thành các phương thức cụ thể để chèn vào đầu, cuối hoặc giữa các nút của danh sách

Chèn lúc bắt đầu

Chèn một nút mới vào đầu danh sách có lẽ là cách chèn đơn giản nhất vì bạn không cần phải duyệt qua toàn bộ danh sách để thực hiện. Tất cả chỉ là tạo một nút mới và sau đó trỏ 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
0 của danh sách tới nút đó

Hãy xem triển khai sau đây của 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
88 cho lớp 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
34

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
86

Trong ví dụ trên, bạn đang đặt 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
800 làm tham chiếu 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
1 của nút mới để nút mới trỏ tới 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
800 cũ. Sau đó, bạn cần chỉ ra rằng 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
0 mới của danh sách là nút được chèn

Đây là cách nó hoạt động với một danh sách mẫu

>>> 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
87

Như bạn có thể thấy, 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
88 luôn thêm nút vào 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
0 của danh sách, ngay cả khi danh sách trống trước đó

Chèn ở cuối

Chèn một nút mới vào cuối danh sách buộc bạn phải duyệt qua toàn bộ danh sách được liên kết trước và thêm nút mới khi bạn đến cuối. Bạn không thể thêm vào cuối danh sách như với danh sách bình thường vì trong danh sách được liên kết, bạn không biết nút nào ở cuối cùng

Đây là một ví dụ triển khai chức năng để chèn một nút vào cuối danh sách được liên kết

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
88

Đầu tiên, bạn muốn duyệt qua toàn bộ danh sách cho đến khi bạn đến cuối (nghĩa là cho đến khi vòng lặp 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
806 tạo ra một ngoại lệ 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
807). Tiếp theo, bạn muốn đặt 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
808 làm nút cuối cùng trong danh sách. Cuối cùng, bạn muốn thêm nút mới làm giá trị 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
1 của 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
808 đó

Đây là một ví dụ về 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
811 đang hoạt động

>>> 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
89

Trong đoạn mã trên, bạn bắt đầu bằng cách tạo một danh sách có bốn giá trị (________ 2812, ________ 2813, ________ 2814 và ________ 2815). Sau đó, khi bạn thêm các nút mới bằng cách sử dụng 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
811, bạn có thể thấy rằng các nút đó luôn được thêm vào cuối danh sách

Chèn giữa hai nút

Việc chèn vào giữa hai nút sẽ thêm một lớp phức tạp khác vào các thao tác chèn vốn đã phức tạp của danh sách được liên kết vì có hai cách tiếp cận khác nhau mà bạn có thể sử dụng

  1. Chèn sau một nút hiện có
  2. Chèn trước một nút hiện có

Việc chia các phương pháp này thành hai phương pháp có vẻ lạ, nhưng danh sách được liên kết hoạt động khác với danh sách thông thường và bạn cần có cách triển khai khác cho từng trường hợp

Đây là một phương pháp thêm một nút sau một nút hiện có với một giá trị dữ liệu cụ thể

>>> deque(['a','b','c'])
deque(['a', 'b', 'c'])

>>> deque('abc')
deque(['a', 'b', 'c'])

>>> deque([{'data': 'a'}, {'data': 'b'}])
deque([{'data': 'a'}, {'data': 'b'}])
0

Trong đoạn mã trên, bạn đang duyệt qua danh sách được liên kết để tìm nút có dữ liệu cho biết nơi bạn muốn chèn nút mới. Khi bạn tìm thấy nút mà bạn đang tìm kiếm, bạn sẽ chèn nút mới ngay sau nút đó và viết lại tham chiếu 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
1 để duy trì tính nhất quán của danh sách

Các ngoại lệ duy nhất là nếu danh sách trống, khiến không thể chèn nút mới sau nút hiện có hoặc nếu danh sách không chứa giá trị bạn đang tìm kiếm. Dưới đây là một vài ví dụ về cách 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
818 cư xử

>>> 

>>> deque(['a','b','c'])
deque(['a', 'b', 'c'])

>>> deque('abc')
deque(['a', 'b', 'c'])

>>> deque([{'data': 'a'}, {'data': 'b'}])
deque([{'data': 'a'}, {'data': 'b'}])
1

Cố gắng sử dụng 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
818 trên một danh sách trống sẽ dẫn đến một ngoại lệ. Điều tương tự cũng xảy ra khi bạn cố gắng thêm vào sau một nút không tồn tại. Mọi thứ khác hoạt động như mong đợi

Bây giờ, nếu bạn muốn triển khai 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
820, thì nó sẽ giống như thế này

>>> deque(['a','b','c'])
deque(['a', 'b', 'c'])

>>> deque('abc')
deque(['a', 'b', 'c'])

>>> deque([{'data': 'a'}, {'data': 'b'}])
deque([{'data': 'a'}, {'data': 'b'}])
2

Có một số điều cần lưu ý khi thực hiện những điều trên. Trước tiên, như với 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
818, bạn muốn đảm bảo đưa ra một ngoại lệ nếu danh sách được liên kết trống (dòng 2) hoặc nút bạn đang tìm kiếm không có (dòng 16)

Thứ hai, nếu bạn đang cố gắng thêm một nút mới trước phần đầu của danh sách (dòng 5), thì bạn có thể sử dụng lại 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
88 vì nút bạn đang chèn sẽ là 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
0 mới của danh sách

Cuối cùng, đối với bất kỳ trường hợp nào khác (dòng 9), bạn nên theo dõi nút được kiểm tra lần cuối bằng cách sử dụng biến 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
824. Sau đó, khi bạn tìm thấy nút đích, bạn có thể sử dụng biến 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
824 đó để viết lại các giá trị 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
1

Một lần nữa, một ví dụ đáng giá ngàn lời nói

>>> 

>>> deque(['a','b','c'])
deque(['a', 'b', 'c'])

>>> deque('abc')
deque(['a', 'b', 'c'])

>>> deque([{'data': 'a'}, {'data': 'b'}])
deque([{'data': 'a'}, {'data': 'b'}])
3

Với 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
820, giờ đây bạn có tất cả các phương pháp cần thiết để chèn các nút vào bất kỳ đâu bạn muốn trong danh sách của mình

Loại bỏ các quảng cáo

Làm thế nào để loại bỏ một nút

Để xóa một nút khỏi danh sách được liên kết, trước tiên bạn cần duyệt qua danh sách cho đến khi tìm thấy nút bạn muốn xóa. Khi bạn tìm thấy mục tiêu, bạn muốn liên kết các nút trước đó và nút tiếp theo của nó. Liên kết lại này là thứ loại bỏ nút đích khỏi danh sách

Điều đó có nghĩa là bạn cần theo dõi nút trước đó khi duyệt qua danh sách. Hãy xem một triển khai ví dụ

>>> deque(['a','b','c'])
deque(['a', 'b', 'c'])

>>> deque('abc')
deque(['a', 'b', 'c'])

>>> deque([{'data': 'a'}, {'data': 'b'}])
deque([{'data': 'a'}, {'data': 'b'}])
4

Trong đoạn mã trên, trước tiên bạn kiểm tra xem danh sách của bạn có trống không (dòng 2). Nếu đúng như vậy, thì bạn đưa ra một ngoại lệ. Sau đó, bạn kiểm tra xem nút cần xóa có phải là 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
0 hiện tại của danh sách không (dòng 5). Nếu đúng như vậy, thì bạn muốn nút tiếp theo trong danh sách trở thành 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
0 mới

Nếu không có điều nào ở trên xảy ra, thì bạn bắt đầu duyệt qua danh sách để tìm nút cần xóa (dòng 10). Nếu bạn tìm thấy nó, thì bạn cần cập nhật nút trước đó để trỏ đến nút tiếp theo của nó, tự động xóa nút tìm thấy khỏi danh sách. Cuối cùng, nếu bạn duyệt qua toàn bộ danh sách mà không tìm thấy nút cần xóa (dòng 16), thì bạn đã đưa ra một ngoại lệ

Lưu ý rằng trong đoạn mã trên, bạn sử dụng 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
830 để theo dõi nút trước đó. Làm như vậy đảm bảo rằng toàn bộ quá trình sẽ đơn giản hơn nhiều khi bạn tìm đúng nút cần xóa

Đây là một ví dụ sử dụng một danh sách

>>> 

>>> deque(['a','b','c'])
deque(['a', 'b', 'c'])

>>> deque('abc')
deque(['a', 'b', 'c'])

>>> deque([{'data': 'a'}, {'data': 'b'}])
deque([{'data': 'a'}, {'data': 'b'}])
5

Đó là nó. Bây giờ bạn đã biết cách triển khai danh sách được liên kết và tất cả các phương thức chính để duyệt, chèn và xóa nút. Nếu bạn cảm thấy thoải mái với những gì mình đã học và bạn khao khát nhiều hơn nữa, thì hãy thoải mái chọn một trong những thử thách bên dưới

  1. Tạo một phương thức để lấy một phần tử từ một vị trí cụ thể. 
    >>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
    831 hoặc thậm chí là 
    >>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
    832
  2. Tạo phương thức đảo ngược danh sách liên kết. 
    >>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
    833
  3. Tạo một đối tượng 
    >>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
    834 kế thừa danh sách liên kết của bài viết này với các phương thức 
    >>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
    835 và 
    >>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
    836

Ngoài việc là một phương pháp luyện tập tuyệt vời, việc tự mình thực hiện một số thử thách bổ sung là một cách hiệu quả để tiếp thu tất cả kiến ​​thức bạn đã thu được. Nếu bạn muốn bắt đầu bằng cách sử dụng lại tất cả mã nguồn từ bài viết này, thì bạn có thể tải xuống mọi thứ bạn cần tại liên kết bên dưới

Lấy mã nguồn. Nhấp vào đây để lấy mã nguồn mà bạn sẽ sử dụng để tìm hiểu về danh sách được liên kết trong hướng dẫn này

Sử dụng danh sách liên kết nâng cao

Cho đến bây giờ, bạn đã tìm hiểu về một loại danh sách liên kết cụ thể được gọi là danh sách liên kết đơn. Nhưng có nhiều loại danh sách được liên kết hơn có thể được sử dụng cho các mục đích hơi khác nhau

Cách sử dụng danh sách liên kết kép

Danh sách liên kết đôi khác với danh sách liên kết đơn ở chỗ chúng có hai tham chiếu

  1. Trường 
    >>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
    837 tham chiếu đến nút trước đó
  2. Trường 
    >>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
    1 tham chiếu nút tiếp theo

Kết quả cuối cùng trông như thế này

Danh sách Python có phải là số 1 không?
Nút (Danh sách liên kết đôi)

Nếu bạn muốn triển khai những điều trên, thì bạn có thể thực hiện một số thay đổi đối với lớp 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
35 hiện tại của mình để bao gồm trường 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
837

>>> deque(['a','b','c'])
deque(['a', 'b', 'c'])

>>> deque('abc')
deque(['a', 'b', 'c'])

>>> deque([{'data': 'a'}, {'data': 'b'}])
deque([{'data': 'a'}, {'data': 'b'}])
6

Kiểu triển khai này sẽ cho phép bạn duyệt qua danh sách theo cả hai hướng thay vì chỉ duyệt qua bằng cách sử dụng 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
1. Bạn có thể sử dụng 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
1 để đi tiếp và 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
837 để đi lùi

Về mặt cấu trúc, đây là cách một danh sách liên kết đôi trông như thế nào

Danh sách Python có phải là số 1 không?
Danh sách liên kết đôi

Trước đó bạn đã biết rằng 

>>> deque(['a','b','c'])
deque(['a', 'b', 'c'])

>>> deque('abc')
deque(['a', 'b', 'c'])

>>> deque([{'data': 'a'}, {'data': 'b'}])
deque([{'data': 'a'}, {'data': 'b'}])
9 sử dụng danh sách được liên kết như một phần cấu trúc dữ liệu của nó. Đây là loại. Với danh sách liên kết kép, 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
34 có khả năng chèn hoặc xóa các phần tử ở cả hai đầu của hàng đợi với hiệu suất O(1) không đổi

Loại bỏ các quảng cáo

Cách sử dụng danh sách liên kết vòng

Danh sách liên kết vòng là một loại danh sách được liên kết trong đó nút cuối cùng trỏ về 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
0 của danh sách thay vì trỏ đến 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
2. Đây là những gì làm cho chúng hình tròn. Danh sách liên kết vòng có khá nhiều trường hợp sử dụng thú vị

  • Đi vòng quanh lượt của từng người chơi trong trò chơi nhiều người chơi
  • Quản lý vòng đời ứng dụng của một hệ điều hành nhất định
  • Thực hiện một đống Fibonacci

Đây là giao diện của một danh sách liên kết vòng

Danh sách Python có phải là số 1 không?
Danh sách liên kết vòng

Một trong những ưu điểm của danh sách liên kết vòng là bạn có thể duyệt qua toàn bộ danh sách bắt đầu từ bất kỳ nút nào. Vì nút cuối cùng trỏ đến 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
0 của danh sách, bạn cần đảm bảo rằng bạn sẽ dừng duyệt khi đến điểm bắt đầu. Nếu không, bạn sẽ kết thúc trong một vòng lặp vô hạn

Về mặt triển khai, danh sách liên kết vòng rất giống với danh sách liên kết đơn. Sự khác biệt duy nhất là bạn có thể xác định điểm bắt đầu khi duyệt qua danh sách

>>> deque(['a','b','c'])
deque(['a', 'b', 'c'])

>>> deque('abc')
deque(['a', 'b', 'c'])

>>> deque([{'data': 'a'}, {'data': 'b'}])
deque([{'data': 'a'}, {'data': 'b'}])
7

Duyệt qua danh sách bây giờ nhận được một đối số bổ sung, 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
849, được sử dụng để xác định điểm bắt đầu và (vì danh sách là vòng tròn) kết thúc quá trình lặp. Ngoài ra, phần lớn mã giống với những gì chúng tôi đã có trong lớp 
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
34 của mình

Để kết thúc với một ví dụ cuối cùng, hãy xem loại danh sách mới này hoạt động như thế nào khi bạn cung cấp cho nó một số dữ liệu

>>> 

>>> deque(['a','b','c'])
deque(['a', 'b', 'c'])

>>> deque('abc')
deque(['a', 'b', 'c'])

>>> deque([{'data': 'a'}, {'data': 'b'}])
deque([{'data': 'a'}, {'data': 'b'}])
8

Ở đó bạn có nó. Bạn sẽ nhận thấy rằng bạn không còn có 

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
2 khi lướt qua danh sách. Đó là bởi vì không có kết thúc cụ thể cho một danh sách vòng tròn. Bạn cũng có thể thấy rằng việc chọn các nút bắt đầu khác nhau sẽ hiển thị các biểu diễn hơi khác nhau của cùng một danh sách

Phần kết luận

Trong bài viết này, bạn đã học được khá nhiều điều. quan trọng nhất là

  • Danh sách được liên kết là gì và khi nào bạn nên sử dụng chúng
  • Cách sử dụng 
    >>> deque(['a','b','c'])
deque(['a', 'b', 'c'])

>>> deque('abc')
deque(['a', 'b', 'c'])

>>> deque([{'data': 'a'}, {'data': 'b'}])
deque([{'data': 'a'}, {'data': 'b'}])
    9 để triển khai hàng đợi và ngăn xếp
  • Cách triển khai danh sách liên kết và các lớp nút của riêng bạn, cùng với các phương thức liên quan
  • Các loại danh sách được liên kết khác là gì và chúng có thể được sử dụng để làm gì

Nếu bạn muốn tìm hiểu thêm về danh sách được liên kết, hãy xem bài đăng trên Trung bình của Vaidehi Joshi để có giải thích trực quan hay. Nếu bạn quan tâm đến hướng dẫn sâu hơn, thì bài viết trên Wikipedia khá kỹ lưỡng. Cuối cùng, nếu bạn tò mò về lý do đằng sau việc triển khai 

>>> deque(['a','b','c'])
deque(['a', 'b', 'c'])

>>> deque('abc')
deque(['a', 'b', 'c'])

>>> deque([{'data': 'a'}, {'data': 'b'}])
deque([{'data': 'a'}, {'data': 'b'}])
9 hiện tại, thì hãy xem chủ đề của Raymond Hettinger

Bạn có thể tải xuống mã nguồn được sử dụng trong hướng dẫn này bằng cách nhấp vào liên kết sau

Lấy mã nguồn. Nhấp vào đây để lấy mã nguồn mà bạn sẽ sử dụng để tìm hiểu về danh sách được liên kết trong hướng dẫn này

Hãy để lại bất kỳ câu hỏi hoặc ý kiến ​​​​dưới đây. Python hạnh phúc

Đánh dấu là đã hoàn thành

Xem ngay Hướng dẫn này có một khóa học video liên quan do nhóm Real Python tạo. Xem nó cùng với hướng dẫn bằng văn bản để hiểu sâu hơn. Làm việc với danh sách được liên kết trong Python

🐍 Thủ thuật Python 💌

Nhận một Thủ thuật Python ngắn và hấp dẫn được gửi đến hộp thư đến của bạn vài ngày một lần. Không có thư rác bao giờ. Hủy đăng ký bất cứ lúc nào. Được quản lý bởi nhóm Real Python

Danh sách Python có phải là số 1 không?

Gửi cho tôi thủ thuật Python »

Giới thiệu về Pedro Pregueiro

Danh sách Python có phải là số 1 không?
Danh sách Python có phải là số 1 không?

Xin chào. Tên tôi là Pedro và tôi là nhà phát triển Python yêu thích viết mã, bánh mì kẹp thịt và chơi ghi-ta

» Thông tin thêm về Pedro

Mỗi hướng dẫn tại Real Python được tạo bởi một nhóm các nhà phát triển để nó đáp ứng các tiêu chuẩn chất lượng cao của chúng tôi. Các thành viên trong nhóm đã làm việc trong hướng dẫn này là

Danh sách Python có phải là số 1 không?

Aldren

Danh sách Python có phải là số 1 không?

Geir Arne

Danh sách Python có phải là số 1 không?

Jim

Danh sách Python có phải là số 1 không?

Joanna

Danh sách Python có phải là số 1 không?

Gia-cốp

Bậc thầy Kỹ năng Python trong thế giới thực Với quyền truy cập không giới hạn vào Python thực

Tham gia với chúng tôi và có quyền truy cập vào hàng nghìn hướng dẫn, khóa học video thực hành và cộng đồng các Pythonistas chuyên gia

Nâng cao kỹ năng Python của bạn »

Bậc thầy Kỹ năng Python trong thế giới thực
Với quyền truy cập không giới hạn vào Python thực

Tham gia với chúng tôi và có quyền truy cập vào hàng ngàn hướng dẫn, khóa học video thực hành và cộng đồng Pythonistas chuyên gia

Nâng cao kỹ năng Python của bạn »

Bạn nghĩ sao?

Đánh giá bài viết này

Tweet Chia sẻ Chia sẻ Email

Bài học số 1 hoặc điều yêu thích mà bạn đã học được là gì?

Mẹo bình luận. Những nhận xét hữu ích nhất là những nhận xét được viết với mục đích học hỏi hoặc giúp đỡ các sinh viên khác. và nhận câu trả lời cho các câu hỏi phổ biến trong cổng thông tin hỗ trợ của chúng tôi

Danh sách Python là 0 hay 1?

danh sách python được 0 lập chỉ mục . Vì vậy, phần tử đầu tiên là 0, thứ hai là 1, v.v. Vì vậy, nếu có n phần tử trong danh sách, phần tử cuối cùng là n-1.

Danh sách 0 có được lập chỉ mục không?

Danh sách “không được lập chỉ mục” , vì vậy [0] trả về thứ 0 (i. e. mục ngoài cùng bên trái) trong danh sách và [1] trả về mục thứ một (i. e. một mục ở bên phải của mục thứ 0).

Độ dài của danh sách O là 1?

len là O(1) vì trong RAM của bạn, các danh sách được lưu trữ dưới dạng bảng (chuỗi địa chỉ liền kề). Để biết khi nào bàn dừng máy tính cần hai điều. chiều dài và điểm bắt đầu. Chính vì vậy len() là O(1), máy tính lưu giá trị nên chỉ cần tra cứu.

[. ] trong Python?

[. ] là cú pháp lát mảng cho mọi phần tử trong mảng . Câu trả lời này ở đây đi sâu hơn vào việc sử dụng chung. Giải thích ký hiệu lát của Python. del arr # Xóa chính mảng đó del arr[. ] # Xóa tất cả các phần tử trong mảng del arr[2] # Xóa phần tử thứ hai trong mảng del arr[1. ] # vân vân.

programming python

Bài Viết Liên Quan

Bán nhà đường lê văn quới bình tân năm 2024
Bán nhà đường lê văn quới bình tân năm 2024

mẹo hay Xây Đựng Nhà
Hướng dẫn mở iphone khi bị vô hiệu hóa năm 2024
Hướng dẫn mở iphone khi bị vô hiệu hóa năm 2024

mẹo hay Mẹo Hay Hướng dẫn Công Nghệ Iphone
Cách tra cứu hóa đơn mới nhất 2023 năm 2024
Cách tra cứu hóa đơn mới nhất 2023 năm 2024

mẹo hay Mẹo Hay Cách
Bài tập tiếng việt lớp 4 tuần 2 chính tả năm 2024
Bài tập tiếng việt lớp 4 tuần 2 chính tả năm 2024

mẹo hay Khỏe Đẹp Bài tập
Bài văn mẫu kể về cuộc đời mình năm 2024
Bài văn mẫu kể về cuộc đời mình năm 2024

mẹo hay
Bài tập hóa đại cương trịnh ngọc châu pdf năm 2024
Bài tập hóa đại cương trịnh ngọc châu pdf năm 2024

mẹo hay Khỏe Đẹp Bài tập
Bị lỗi khi đánh số bằng clip cad năm 2024
Bị lỗi khi đánh số bằng clip cad năm 2024

mẹo hay
Baif diễn văn của obama tại việt nam năm 2024
Baif diễn văn của obama tại việt nam năm 2024

mẹo hay
Giải bt 3 hóa 12 sgk trang 180 năm 2024
Giải bt 3 hóa 12 sgk trang 180 năm 2024

mẹo hay
Bom hủy diệt lón nhất hiện nay là loai nào năm 2024
Bom hủy diệt lón nhất hiện nay là loai nào năm 2024

mẹo hay
Bài tập trắc nghiệm tiếng anh 8 2023 năm 2024
Bài tập trắc nghiệm tiếng anh 8 2023 năm 2024

mẹo hay Khỏe Đẹp Bài tập Học Tốt Tiếng anh
Api-ms-win-crt-runtime-l1-1-0.dll bị lỗi năm 2024
Api-ms-win-crt-runtime-l1-1-0.dll bị lỗi năm 2024

mẹo hay
Như thế nào là yêu thương con người năm 2024
Như thế nào là yêu thương con người năm 2024

mẹo hay Hỏi Đáp Thế nào
Bài tập quy mô huy động vốn tối ưu năm 2024
Bài tập quy mô huy động vốn tối ưu năm 2024

mẹo hay Khỏe Đẹp Bài tập
Bài tập và ngữ pháp tiếng anh 1 năm 2024
Bài tập và ngữ pháp tiếng anh 1 năm 2024

mẹo hay Khỏe Đẹp Bài tập Học Tốt Tiếng anh
Cong ty cua mirinda soda kem thuoc cong ty nào năm 2024
Cong ty cua mirinda soda kem thuoc cong ty nào năm 2024

mẹo hay
Cty yến trường tùng hoàng văn thụ hồ chí minh năm 2024
Cty yến trường tùng hoàng văn thụ hồ chí minh năm 2024

mẹo hay
Tuổi kỷ hợi 2023 sinh giờ nào tốt năm 2024
Tuổi kỷ hợi 2023 sinh giờ nào tốt năm 2024

mẹo hay
Phim quá khứ tội lỗi mexico tập 110 năm 2024
Phim quá khứ tội lỗi mexico tập 110 năm 2024

mẹo hay Phim
Lỗi không vào được youtube trên smart tivi năm 2024
Lỗi không vào được youtube trên smart tivi năm 2024

mẹo hay

Quảng Cáo

Có thể bạn quan tâm

Bài tập reported speech lớp 10 có đáp án năm 2024
1 ngày trước . bởi InfantileBallet
Cách đồng bộ hóa danh bạ trên blackberry lên gmail năm 2024
1 ngày trước . bởi TurquoiseOrganizer
Top tiền đạo cánh phải hay nhất fifa online 4 năm 2024
1 ngày trước . bởi CoiledTavern
Lực ma sát phụ thuộc vào yếu tố nào năm 2024
1 ngày trước . bởi EquivalentFrenchman
Bàn ủi vomet và kim cương hãng nào được năm 2024
1 ngày trước . bởi NarcissisticAppellation
Ngữ văn lớp 7 trang 68 tập 2 năm 2024
1 ngày trước . bởi BefuddledBy-election
Phạt tiền khi viết hóa đơn không đúng thời điểm năm 2024
1 ngày trước . bởi SealedAcreage
5 dương văn nga thành phố vũng tàu năm 2024
1 ngày trước . bởi RealisticRegularity
Laptop bắt wifi bị lỗi dấu chấm than năm 2024
1 ngày trước . bởi SuspendedCheck-in
C o hiện nay do tổ chức nào cấp năm 2024
1 ngày trước . bởi AscendingIntercession

Toplist được quan tâm

#1
Top 6 bản thân em phải làm gì để phòng chống hiv/aids 2023
7 tháng trước
#2
Top 7 số 20 gồm 2 và 0 đúng hay sai 2023
7 tháng trước
#3
Top 7 địa lý lớp 6 bài 19: lớp đất và các nhân tố hình thành đất một số nhóm đất điển hình trang 178 2023
7 tháng trước
#4
Top 7 h thực hiện chủ trương đường lối chính sách của đảng pháp luật của nhà nước 2023
7 tháng trước
#5
Top 6 on tập tiếng việt lớp 7 học kĩ 2 violet 2023
7 tháng trước
#6
Top 7 trung du và miền núi bắc bộ có thế mạnh nổi bật về luyện kim đen 2023
7 tháng trước
#7
Top 8 mơ thấy có người to tình với mình 2023
7 tháng trước
#8
Top 6 nước yến cao cấp yến sào thiên hoàng 2023
7 tháng trước
#9
Top 7 ví dụ về quyết định hành chính nhà nước 2023
7 tháng trước

Quảng cáo

Xem Nhiều

Bài tập trọng âm ôn thi đại học năm 2024
6 ngày trước . bởi OffTrilogy
Công nghệ điện toán đám mây của bkav là gì năm 2024
2 ngày trước . bởi Well-heeledConversation
Lời bài hát xin lỗi em người anh yêu năm 2024
10 giờ trước . bởi ShudderingAppeasement
Lỗi it is not supported in mobile environment năm 2024
1 tuần trước . bởi SlidingPublisher
Lỗi không tải file lên hệ thống ecosys năm 2024
1 tuần trước . bởi SalariedPublicist
Hãng xe ô tô chevrolet của nước nào năm 2024
4 ngày trước . bởi PopulousThriller
Các trường hợp hàng hóa bị giao chậm năm 2024
1 tuần trước . bởi EstablishedRecognition
Bài soạn anh văn unit 11 getting started lớp 7 năm 2024
1 tuần trước . bởi SanitaryPrototype
Ngã tư trung lương nguyễn văn linh bình chánh năm 2024
1 tuần trước . bởi HawkishDeference
Dđề án sáp nhập xã tỉnh thanh hóa năm 2024
1 tuần trước . bởi PerfectBallet

Quảng cáo

Chúng tôi

Điều khoản

Trợ giúp

Mạng xã hội

DMCA.com Protection Status
Bản quyền © 2021 Hỏi Đáp Inc.