Danh sách được liên kết chèn vào chỉ mục Python

Danh sách liên kết là một trong những cấu trúc dữ liệu được sử dụng phổ biến nhất trong bất kỳ ngôn ngữ lập trình nào. Trong bài này chúng ta sẽ nghiên cứu chi tiết về danh sách liên kết. Chúng ta sẽ xem các loại danh sách được liên kết khác nhau là gì, cách duyệt qua danh sách được liên kết, cách chèn và xóa phần tử khỏi danh sách được liên kết, các kỹ thuật khác nhau để sắp xếp danh sách được liên kết, cách đảo ngược danh sách được liên kết, v.v.

Sau khi đọc bài viết này, bạn sẽ có thể bẻ khóa tất cả các câu hỏi phỏng vấn danh sách liên kết

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

Trước khi chúng ta nghiên cứu danh sách được liên kết là gì, trước tiên chúng ta hãy xem lại cách Mảng lưu trữ dữ liệu. Trong mảng, dữ liệu được lưu trữ tại các vị trí bộ nhớ liền kề. Chẳng hạn, nếu mục đầu tiên trong mảng được lưu trữ ở chỉ mục 10 của bộ nhớ và có kích thước 15 byte, thì mục thứ hai sẽ được lưu trữ ở chỉ mục 10+15+1 = chỉ mục thứ 26. Do đó, thật dễ dàng để duyệt qua một mảng

Để tìm mục thứ ba trong một mảng, bạn chỉ cần sử dụng chỉ mục bắt đầu của mục đầu tiên, cộng với kích thước của mục đầu tiên, cộng với kích thước của mục thứ hai, cộng với 1

Cách danh sách được liên kết lưu trữ dữ liệu

Mặt khác, Danh sách được liên kết thì khác. Danh sách được liên kết, không lưu trữ dữ liệu tại các vị trí bộ nhớ liền kề. Đối với mỗi mục trong vị trí bộ nhớ, danh sách được liên kết lưu trữ giá trị của mục đó và tham chiếu hoặc con trỏ tới mục tiếp theo. Một cặp mục danh sách được liên kết và tham chiếu đến mục tiếp theo tạo thành một nút

Chẳng hạn, nếu một nút bao gồm 34. 10, có nghĩa là giá trị của nút là 30, trong khi mục tiếp theo được lưu trữ tại vị trí bộ nhớ "10". Để duyệt qua một danh sách được liên kết, bạn chỉ cần biết vị trí bộ nhớ hoặc tham chiếu của nút đầu tiên, các nút còn lại có thể được duyệt tuần tự bằng cách sử dụng tham chiếu đến phần tử tiếp theo trong mỗi nút

Tham chiếu đến nút đầu tiên còn được gọi là nút bắt đầu

Danh sách được liên kết vs Mảng

• Danh sách liên kết là một cấu trúc dữ liệu động, có nghĩa là bộ nhớ dành riêng cho danh sách liên kết có thể tăng hoặc giảm khi chạy. Không có bộ nhớ nào được phân bổ trước cho cấu trúc dữ liệu danh sách được liên kết. Bất cứ khi nào một mục mới được yêu cầu thêm vào liên kết, bộ nhớ cho nút mới sẽ được tạo trong thời gian chạy. Mặt khác, trong trường hợp của mảng, bộ nhớ phải được phân bổ trước cho một số mục cụ thể. Trong trường hợp không có đủ mục để điền vào tất cả chỉ mục mảng, không gian bộ nhớ sẽ bị lãng phí
• Vì các mảng yêu cầu các vị trí bộ nhớ liền kề nên rất khó xóa hoặc chèn một phần tử vào một mảng vì các vị trí bộ nhớ của một số lượng lớn các phần tử phải được cập nhật. Mặt khác, các mục danh sách được liên kết không được lưu trữ trong một vị trí bộ nhớ liền kề, do đó bạn có thể dễ dàng cập nhật danh sách được liên kết
• Do tính linh hoạt của nó, danh sách được liên kết phù hợp hơn để triển khai các cấu trúc dữ liệu như ngăn xếp, hàng đợi và danh sách

Tuy nhiên, cũng có một số nhược điểm đối với danh sách liên kết.

• Vì mỗi mục trong danh sách được liên kết phải lưu trữ tham chiếu đến mục tiếp theo nên cần có thêm bộ nhớ
• Không giống như Mảng, nơi bạn có thể truy cập trực tiếp vào một mục, bạn không thể truy cập trực tiếp vào mục danh sách được liên kết vì thông tin duy nhất bạn có là tham chiếu đến mục đầu tiên. Theo thuật ngữ Big O, thời gian truy cập trong trường hợp xấu nhất là O[n]

Trong loạt bài viết này, chúng ta sẽ nghiên cứu các loại danh sách liên kết sau đây cùng với các chức năng khác nhau của chúng

• Danh sách liên kết đơn
• Danh sách liên kết đôi
• Danh sách liên kết vòng
• Danh sách được liên kết với tiêu đề
• Danh sách liên kết được sắp xếp

Trong phần đầu tiên của bài viết này, chúng tôi sẽ tập trung vào danh sách liên kết đơn và các hoạt động khác nhau của nó

Danh sách liên kết đơn

Danh sách liên kết đơn là dạng đơn giản nhất trong tất cả các biến thể của danh sách liên kết. Mỗi nút trong một danh sách được liên kết duy nhất chứa một mục và tham chiếu đến mục tiếp theo và đó là mục đó

Trong phần này, chúng ta sẽ xem cách tạo một nút cho danh sách liên kết đơn cùng với các chức năng cho các kiểu chèn, duyệt và xóa khác nhau

Tạo lớp nút

Điều đầu tiên bạn cần làm là tạo một lớp cho các nút. Các đối tượng của lớp này sẽ là các nút thực tế mà chúng ta sẽ chèn vào danh sách được liên kết của mình. Chúng tôi biết rằng một nút cho một danh sách được liên kết đơn chứa mục và tham chiếu đến nút tiếp theo. Do đó, lớp nút của chúng ta sẽ chứa hai biến thành viên

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

1 và

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

2. Giá trị của

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

1 sẽ được đặt bởi giá trị được truyền qua hàm tạo, trong khi tham chiếu ban đầu sẽ được đặt thành null

Thực thi đoạn script sau

class Node:
    def __init__[self, data]:
        self.item = data
        self.ref = None

Tạo lớp danh sách liên kết đơn

Tiếp theo, chúng ta cần tạo một lớp cho Danh sách liên kết. Lớp này sẽ chứa các phương thức để chèn, xóa, duyệt và sắp xếp danh sách. Ban đầu, lớp sẽ chỉ chứa một thành viên

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

4 sẽ trỏ đến nút bắt đầu hoặc nút đầu tiên của danh sách. Giá trị của

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

4 sẽ được đặt thành null khi sử dụng hàm tạo vì danh sách được liên kết sẽ trống tại thời điểm tạo. Đoạn script sau tạo một lớp cho danh sách liên kết

class LinkedList:
    def __init__[self]:
        self.start_node = None

Bây giờ chúng tôi đã tạo một lớp cho danh sách đơn của chúng tôi. Bước tiếp theo là thêm chức năng chèn để chèn các mục vào danh sách được liên kết. Nhưng trước đó, chúng ta sẽ thêm chức năng duyệt danh sách liên kết. Chức năng này sẽ giúp chúng tôi đọc dữ liệu trong danh sách của chúng tôi

Duyệt qua các mục trong danh sách được liên kết

Mã Python cho chức năng duyệt như sau. Thêm chức năng bên dưới vào lớp

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

6 mà chúng tôi đã tạo trong phần trước

________số 8_______

Hãy xem những gì đang xảy ra trong chức năng trên. Chức năng có hai phần chính. Đầu tiên, nó kiểm tra xem danh sách liên kết có rỗng hay không. Đoạn mã sau kiểm tra xem

  if self.start_node is None:
        print["List has no element"]
        return

Nếu danh sách được liên kết trống, điều đó có nghĩa là không có mục nào để lặp lại. Trong những trường hợp như vậy, hàm

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

7 chỉ in ra câu lệnh rằng danh sách không có mục nào

Mặt khác, nếu danh sách có một mục, đoạn mã sau sẽ thực thi

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

Như chúng tôi đã nói trước đó, biến

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

8 sẽ chứa một tham chiếu đến các nút đầu tiên. Do đó, chúng tôi khởi tạo một biến

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

9 với biến

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

8. Tiếp theo, chúng tôi thực hiện một vòng lặp thực thi cho đến khi

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

9 trở thành không. Bên trong vòng lặp, chúng tôi in mục được lưu trữ tại nút hiện tại và sau đó đặt giá trị của biến

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

9 thành

    def insert_at_start[self, data]:
        new_node = Node[data]
        new_node.ref = self.start_node
        self.start_node= new_node

3, chứa tham chiếu đến nút tiếp theo. Tham chiếu của nút cuối cùng là

    def insert_at_start[self, data]:
        new_node = Node[data]
        new_node.ref = self.start_node
        self.start_node= new_node

4 vì không có nút nào sau đó. Do đó, khi

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

9 trở thành

    def insert_at_start[self, data]:
        new_node = Node[data]
        new_node.ref = self.start_node
        self.start_node= new_node

4, vòng lặp kết thúc

Bây giờ, chúng tôi có chức năng duyệt qua danh sách được liên kết, hãy xem cách chúng tôi có thể thêm các mục vào danh sách được liên kết đơn lẻ

Chèn mục

Tùy thuộc vào vị trí mà bạn muốn chèn mục, có nhiều cách khác nhau để chèn mục vào danh sách liên kết đơn

Chèn các mục ở đầu

Cách đơn giản nhất để chèn một mục vào danh sách liên kết đơn là thêm một mục vào đầu danh sách. Hàm sau chèn mục vào đầu danh sách. Thêm hàm này vào lớp

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

6 mà chúng ta đã tạo trước đó

    def insert_at_start[self, data]:
        new_node = Node[data]
        new_node.ref = self.start_node
        self.start_node= new_node

Trong đoạn mã trên, chúng tôi tạo một phương thức

    def insert_at_start[self, data]:
        new_node = Node[data]
        new_node.ref = self.start_node
        self.start_node= new_node

8, phương thức này chấp nhận một tham số, về cơ bản là giá trị của mục mà chúng tôi muốn chèn. Bên trong phương thức, chúng ta chỉ cần tạo một đối tượng của lớp

    def insert_at_start[self, data]:
        new_node = Node[data]
        new_node.ref = self.start_node
        self.start_node= new_node

9 và đặt tham chiếu của nó tới lớp

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

4 vì trước đó

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

4 đã lưu trữ nút đầu tiên, nút này sau khi chèn nút mới vào đầu sẽ trở thành nút thứ hai

Do đó, chúng tôi thêm tham chiếu của

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

4 vào biến

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

2 của nút mới. Bây giờ vì

  def insert_at_end[self, data]:
        new_node = Node[data]
        if self.start_node is None:
            self.start_node = new_node
            return
        n = self.start_node
        while n.ref is not None:
            n= n.ref
        n.ref = new_node;

4 là nút đầu tiên, chúng tôi đặt giá trị của biến

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

4 thành

  def insert_at_end[self, data]:
        new_node = Node[data]
        if self.start_node is None:
            self.start_node = new_node
            return
        n = self.start_node
        while n.ref is not None:
            n= n.ref
        n.ref = new_node;

4

Chèn các mục ở cuối

Hàm sau dùng để thêm một mục vào cuối danh sách liên kết

  def insert_at_end[self, data]:
        new_node = Node[data]
        if self.start_node is None:
            self.start_node = new_node
            return
        n = self.start_node
        while n.ref is not None:
            n= n.ref
        n.ref = new_node;

Trong đoạn mã trên, chúng tôi tạo một hàm

  def insert_at_end[self, data]:
        new_node = Node[data]
        if self.start_node is None:
            self.start_node = new_node
            return
        n = self.start_node
        while n.ref is not None:
            n= n.ref
        n.ref = new_node;

7, hàm này sẽ chèn phần tử vào cuối danh sách được liên kết. Giá trị của mục mà chúng tôi muốn chèn được truyền dưới dạng đối số cho hàm. Chức năng bao gồm hai phần. Đầu tiên chúng ta kiểm tra xem danh sách liên kết có trống hay không, nếu danh sách liên kết trống, tất cả những gì chúng ta phải làm là đặt giá trị của biến

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

4 thành đối tượng

  def insert_at_end[self, data]:
        new_node = Node[data]
        if self.start_node is None:
            self.start_node = new_node
            return
        n = self.start_node
        while n.ref is not None:
            n= n.ref
        n.ref = new_node;

4

Mặt khác, nếu danh sách đã chứa một số nút. Chúng tôi khởi tạo một biến

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

9 với nút bắt đầu. Sau đó, chúng tôi lặp qua tất cả các nút trong danh sách bằng cách sử dụng vòng lặp while như chúng tôi đã làm trong trường hợp hàm

    def insert_after_item[self, x, data]:

        n = self.start_node
        print[n.ref]
        while n is not None:
            if n.item == x:
                break
            n = n.ref
        if n is None:
            print["item not in the list"]
        else:
            new_node = Node[data]
            new_node.ref = n.ref
            n.ref = new_node

1. Vòng lặp kết thúc khi chúng ta đến nút cuối cùng. Sau đó, chúng tôi đặt tham chiếu của nút cuối cùng thành

  def insert_at_end[self, data]:
        new_node = Node[data]
        if self.start_node is None:
            self.start_node = new_node
            return
        n = self.start_node
        while n.ref is not None:
            n= n.ref
        n.ref = new_node;

4 mới được tạo

Thêm hàm

  def insert_at_end[self, data]:
        new_node = Node[data]
        if self.start_node is None:
            self.start_node = new_node
            return
        n = self.start_node
        while n.ref is not None:
            n= n.ref
        n.ref = new_node;

7 vào lớp

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

6

Chèn Mục này sau Mục khác

Chúng tôi có thể cần thêm mục này sau mục khác trong một danh sách được liên kết duy nhất. Để làm như vậy, chúng ta có thể sử dụng hàm

    def insert_after_item[self, x, data]:

        n = self.start_node
        print[n.ref]
        while n is not None:
            if n.item == x:
                break
            n = n.ref
        if n is None:
            print["item not in the list"]
        else:
            new_node = Node[data]
            new_node.ref = n.ref
            n.ref = new_node

5 như được định nghĩa bên dưới

    def insert_after_item[self, x, data]:

        n = self.start_node
        print[n.ref]
        while n is not None:
            if n.item == x:
                break
            n = n.ref
        if n is None:
            print["item not in the list"]
        else:
            new_node = Node[data]
            new_node.ref = n.ref
            n.ref = new_node

Hàm

    def insert_after_item[self, x, data]:

        n = self.start_node
        print[n.ref]
        while n is not None:
            if n.item == x:
                break
            n = n.ref
        if n is None:
            print["item not in the list"]
        else:
            new_node = Node[data]
            new_node.ref = n.ref
            n.ref = new_node

5 chấp nhận hai tham số.

    def insert_after_item[self, x, data]:

        n = self.start_node
        print[n.ref]
        while n is not None:
            if n.item == x:
                break
            n = n.ref
        if n is None:
            print["item not in the list"]
        else:
            new_node = Node[data]
            new_node.ref = n.ref
            n.ref = new_node

7 và

    def insert_after_item[self, x, data]:

        n = self.start_node
        print[n.ref]
        while n is not None:
            if n.item == x:
                break
            n = n.ref
        if n is None:
            print["item not in the list"]
        else:
            new_node = Node[data]
            new_node.ref = n.ref
            n.ref = new_node

8. Tham số đầu tiên là mục mà sau đó bạn muốn chèn nút mới trong khi tham số thứ hai chứa giá trị cho nút mới

Chúng tôi bắt đầu bằng cách tạo một biến mới

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

9 và gán biến

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

4 cho nó. Tiếp theo, chúng tôi duyệt qua danh sách được liên kết bằng cách sử dụng vòng lặp while. Vòng lặp while thực hiện cho đến khi

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

9 trở thành

    def insert_at_start[self, data]:
        new_node = Node[data]
        new_node.ref = self.start_node
        self.start_node= new_node

4. Trong mỗi lần lặp, chúng tôi kiểm tra xem giá trị được lưu trữ trong nút hiện tại có bằng giá trị được truyền bởi tham số

    def insert_after_item[self, x, data]:

        n = self.start_node
        print[n.ref]
        while n is not None:
            if n.item == x:
                break
            n = n.ref
        if n is None:
            print["item not in the list"]
        else:
            new_node = Node[data]
            new_node.ref = n.ref
            n.ref = new_node

7 hay không. Nếu phép so sánh trả về true, chúng ta ngắt vòng lặp

Tiếp theo, nếu hàng được tìm thấy, biến

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

9 sẽ không phải là

    def insert_at_start[self, data]:
        new_node = Node[data]
        new_node.ref = self.start_node
        self.start_node= new_node

4. Tham chiếu của

  def insert_at_end[self, data]:
        new_node = Node[data]
        if self.start_node is None:
            self.start_node = new_node
            return
        n = self.start_node
        while n.ref is not None:
            n= n.ref
        n.ref = new_node;

4 được đặt thành tham chiếu được lưu trữ bởi

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

9 và tham chiếu của

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

9 được đặt thành

  def insert_at_end[self, data]:
        new_node = Node[data]
        if self.start_node is None:
            self.start_node = new_node
            return
        n = self.start_node
        while n.ref is not None:
            n= n.ref
        n.ref = new_node;

4. Thêm hàm

    def insert_after_item[self, x, data]:

        n = self.start_node
        print[n.ref]
        while n is not None:
            if n.item == x:
                break
            n = n.ref
        if n is None:
            print["item not in the list"]
        else:
            new_node = Node[data]
            new_node.ref = n.ref
            n.ref = new_node

5 vào lớp

     if self.start_node is None:
        print["List has no element"]
        return

1

Chèn Mục trước Mục khác

    def insert_before_item[self, x, data]:
        if self.start_node is None:
            print["List has no element"]
            return

        if x == self.start_node.item:
            new_node = Node[data]
            new_node.ref = self.start_node
            self.start_node = new_node
            return

        n = self.start_node
        print[n.ref]
        while n.ref is not None:
            if n.ref.item == x:
                break
            n = n.ref
        if n.ref is None:
            print["item not in the list"]
        else:
            new_node = Node[data]
            new_node.ref = n.ref
            n.ref = new_node

Trong đoạn mã trên, chúng tôi định nghĩa hàm

     if self.start_node is None:
        print["List has no element"]
        return

2. Chức năng có ba phần. Hãy xem xét từng phần một cách chi tiết

     if self.start_node is None:
        print["List has no element"]
        return

Trong đoạn script trên, chúng tôi kiểm tra xem danh sách có trống không. Nếu nó thực sự trống, chúng ta chỉ cần in ra rằng danh sách không có phần tử nào và trả về từ hàm

Tiếp theo, chúng tôi kiểm tra xem phần tử có nằm ở chỉ mục đầu tiên không. Nhìn vào đoạn script sau

class LinkedList:
    def __init__[self]:
        self.start_node = None

0

Nếu phần tử mà sau đó chúng ta muốn chèn một nút mới nằm ở chỉ mục đầu tiên. Chúng tôi chỉ cần đặt tham chiếu của nút mới được chèn thành

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

4 và sau đó đặt giá trị của

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

4 thành

  def insert_at_end[self, data]:
        new_node = Node[data]
        if self.start_node is None:
            self.start_node = new_node
            return
        n = self.start_node
        while n.ref is not None:
            n= n.ref
        n.ref = new_node;

4

Cuối cùng, nếu danh sách không phải là

    def insert_at_start[self, data]:
        new_node = Node[data]
        new_node.ref = self.start_node
        self.start_node= new_node

4 và không tìm thấy phần tử ở chỉ mục đầu tiên, chúng ta tạo một biến mới

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

9 và gán biến

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

4 cho nó. Tiếp theo, chúng tôi duyệt qua danh sách được liên kết bằng cách sử dụng vòng lặp while. Vòng lặp while thực thi cho đến khi

    def insert_at_start[self, data]:
        new_node = Node[data]
        new_node.ref = self.start_node
        self.start_node= new_node

3 trở thành

    def insert_at_start[self, data]:
        new_node = Node[data]
        new_node.ref = self.start_node
        self.start_node= new_node

4. Trong mỗi lần lặp lại, chúng tôi kiểm tra xem giá trị được lưu trữ trong tham chiếu của nút hiện tại có bằng với giá trị được truyền bởi tham số

    def insert_after_item[self, x, data]:

        n = self.start_node
        print[n.ref]
        while n is not None:
            if n.item == x:
                break
            n = n.ref
        if n is None:
            print["item not in the list"]
        else:
            new_node = Node[data]
            new_node.ref = n.ref
            n.ref = new_node

7 hay không. Nếu phép so sánh trả về true, chúng ta ngắt vòng lặp

Tiếp theo, nếu mục được tìm thấy, biến

    def insert_at_start[self, data]:
        new_node = Node[data]
        new_node.ref = self.start_node
        self.start_node= new_node

3 sẽ không phải là

    def insert_at_start[self, data]:
        new_node = Node[data]
        new_node.ref = self.start_node
        self.start_node= new_node

4. Tham chiếu của

  def insert_at_end[self, data]:
        new_node = Node[data]
        if self.start_node is None:
            self.start_node = new_node
            return
        n = self.start_node
        while n.ref is not None:
            n= n.ref
        n.ref = new_node;

4 được đặt thành tham chiếu của

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

9 và tham chiếu của

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

9 được đặt thành

  def insert_at_end[self, data]:
        new_node = Node[data]
        if self.start_node is None:
            self.start_node = new_node
            return
        n = self.start_node
        while n.ref is not None:
            n= n.ref
        n.ref = new_node;

4. Nhìn vào đoạn script sau

class LinkedList:
    def __init__[self]:
        self.start_node = None

1

Thêm hàm

     if self.start_node is None:
        print["List has no element"]
        return

2 vào lớp

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

6

Chèn mục vào chỉ mục cụ thể

Đôi khi, chúng ta cần chèn mục vào một chỉ mục cụ thể, chúng ta có thể làm như vậy với sự trợ giúp của tập lệnh sau

class LinkedList:
    def __init__[self]:
        self.start_node = None

2

Trong tập lệnh, trước tiên chúng tôi kiểm tra xem chỉ mục mà chúng tôi muốn lưu trữ mục có phải là 1 hay không, sau đó chỉ cần gán

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

4 cho tham chiếu của

  def insert_at_end[self, data]:
        new_node = Node[data]
        if self.start_node is None:
            self.start_node = new_node
            return
        n = self.start_node
        while n.ref is not None:
            n= n.ref
        n.ref = new_node;

4 rồi đặt giá trị của

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

4 thành

  def insert_at_end[self, data]:
        new_node = Node[data]
        if self.start_node is None:
            self.start_node = new_node
            return
        n = self.start_node
        while n.ref is not None:
            n= n.ref
        n.ref = new_node;

4

Tiếp theo, thực hiện vòng lặp while, vòng lặp này thực hiện cho đến khi bộ đếm

class LinkedList:
    def __init__[self]:
        self.start_node = None

14 trở nên lớn hơn hoặc bằng

class LinkedList:
    def __init__[self]:
        self.start_node = None

15. Chẳng hạn, nếu bạn muốn thêm một nút mới vào chỉ mục thứ ba. Trong lần lặp đầu tiên của vòng lặp while,

class LinkedList:
    def __init__[self]:
        self.start_node = None

14 sẽ trở thành 2 và nút được lặp hiện tại sẽ là '2'. Vòng lặp sẽ không thực hiện lại vì

class LinkedList:
    def __init__[self]:
        self.start_node = None

14 bây giờ là 2 bằng với chỉ số-1 [3-1=2]. Do đó, vòng lặp sẽ bị phá vỡ. Tiếp theo, chúng tôi thêm một nút mới sau nút hiện tại được lặp lại [là nút 2], do đó nút mới được thêm vào chỉ mục

Điều quan trọng cần đề cập là nếu chỉ mục hoặc vị trí được truyền dưới dạng đối số lớn hơn kích thước của danh sách được liên kết, một thông báo sẽ được hiển thị cho người dùng rằng chỉ mục nằm ngoài phạm vi hoặc ngoài giới hạn

Kiểm tra chức năng chèn

Bây giờ chúng tôi đã xác định tất cả các chức năng chèn của mình, hãy kiểm tra chúng

Đầu tiên tạo một đối tượng thuộc lớp danh sách liên kết như sau

class LinkedList:
    def __init__[self]:
        self.start_node = None

3

Tiếp theo, trước tiên hãy gọi hàm

  def insert_at_end[self, data]:
        new_node = Node[data]
        if self.start_node is None:
            self.start_node = new_node
            return
        n = self.start_node
        while n.ref is not None:
            n= n.ref
        n.ref = new_node;

7 để thêm ba phần tử vào danh sách được liên kết. Thực thi đoạn script sau

class LinkedList:
    def __init__[self]:
        self.start_node = None

4

Để xem, nếu các mục đã thực sự được chèn vào, hãy duyệt qua danh sách được liên kết bằng chức năng duyệt qua

class LinkedList:
    def __init__[self]:
        self.start_node = None

5

Bạn sẽ thấy đầu ra sau

class LinkedList:
    def __init__[self]:
        self.start_node = None

6

Tiếp theo, hãy thêm một phần tử vào đầu

Hãy xem hướng dẫn thực hành, thực tế của chúng tôi để học Git, với các phương pháp hay nhất, tiêu chuẩn được ngành chấp nhận và bao gồm bảng gian lận. Dừng các lệnh Git trên Google và thực sự tìm hiểu nó

class LinkedList:
    def __init__[self]:
        self.start_node = None

7

Bây giờ, nếu bạn duyệt qua danh sách, bạn sẽ thấy đầu ra sau

class LinkedList:
    def __init__[self]:
        self.start_node = None

8

Hãy thêm một mục mới 17 sau mục 10

class LinkedList:
    def __init__[self]:
        self.start_node = None

9

Duyệt qua danh sách trả về đầu ra sau ngay bây giờ

def traverse_list[self]:
    if self.start_node is None:
        print["List has no element"]
        return
    else:
        n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

0

Bạn có thể thấy 17 được chèn sau 10

Bây giờ, hãy chèn một mục khác 25 trước mục 17 bằng cách sử dụng hàm

     if self.start_node is None:
        print["List has no element"]
        return

2 như hình bên dưới

def traverse_list[self]:
    if self.start_node is None:
        print["List has no element"]
        return
    else:
        n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

1

Bây giờ danh sách sẽ chứa các yếu tố sau

def traverse_list[self]:
    if self.start_node is None:
        print["List has no element"]
        return
    else:
        n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

2

Cuối cùng, hãy thêm một phần tử ở vị trí thứ ba, hiện đang bị chiếm bởi 10. Bạn sẽ thấy rằng 10 sẽ di chuyển về phía trước một vị trí và mục mới sẽ được chèn vào vị trí của nó. Hàm

class LinkedList:
    def __init__[self]:
        self.start_node = None

20 có thể được sử dụng cho mục đích này. Đoạn script sau chèn mục

class LinkedList:
    def __init__[self]:
        self.start_node = None

21 vào chỉ mục chỉ mục thứ ba của danh sách

def traverse_list[self]:
    if self.start_node is None:
        print["List has no element"]
        return
    else:
        n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

3

Bây giờ nếu bạn duyệt qua danh sách, bạn sẽ thấy đầu ra sau

def traverse_list[self]:
    if self.start_node is None:
        print["List has no element"]
        return
    else:
        n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

4

Và cùng với đó, chúng tôi đã kiểm tra tất cả chức năng chèn của mình. Chúng tôi hiện có 7 yếu tố trong danh sách của chúng tôi. Hãy viết hàm trả về số phần tử trong danh sách liên kết

Đếm yếu tố

Hàm sau đếm tổng số phần tử

def traverse_list[self]:
    if self.start_node is None:
        print["List has no element"]
        return
    else:
        n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

5

Trong đoạn mã trên, chúng tôi tạo hàm

class LinkedList:
    def __init__[self]:
        self.start_node = None

22 chỉ đơn giản là đếm số lượng phần tử trong danh sách được liên kết. Hàm chỉ đơn giản là duyệt qua tất cả các nút trong mảng và tăng bộ đếm bằng cách sử dụng vòng lặp while. Ở cuối vòng lặp, bộ đếm chứa tổng số phần tử trong vòng lặp

Thêm hàm trên vào lớp

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

6, biên dịch lớp

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

6 và sau đó chèn một số phần tử vào lớp

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

6 như chúng ta đã làm trong phần trước. Chúng tôi đã có 7 mục trong danh sách được liên kết của mình, vào cuối phần trước

Hãy sử dụng hàm

class LinkedList:
    def __init__[self]:
        self.start_node = None

22 để lấy tổng số mục trong danh sách

def traverse_list[self]:
    if self.start_node is None:
        print["List has no element"]
        return
    else:
        n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

6

Bạn sẽ thấy số lượng mục trong danh sách được liên kết của mình ở đầu ra

Ngoài ra, một cách khác để lấy 'số lượng' của danh sách là theo dõi số mục được thêm vào và xóa khỏi danh sách trong một biến đếm đơn giản thuộc lớp

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

6. Điều này hoạt động tốt và nhanh hơn phương thức

class LinkedList:
    def __init__[self]:
        self.start_node = None

28 ở trên, nếu không thể thao tác cấu trúc dữ liệu danh sách cơ bản từ bên ngoài lớp

tìm kiếm các yếu tố

Tìm kiếm một phần tử khá giống với việc đếm hoặc duyệt qua một danh sách được liên kết, tất cả những gì bạn phải làm là so sánh giá trị được tìm kiếm với giá trị của nút trong mỗi lần lặp. Nếu giá trị được tìm thấy, hãy in giá trị được tìm thấy và ngắt vòng lặp. Nếu không tìm thấy phần tử sau khi duyệt qua tất cả các nút, chỉ cần in phần tử đó không tìm thấy

Kịch bản cho

class LinkedList:
    def __init__[self]:
        self.start_node = None

29 như sau

def traverse_list[self]:
    if self.start_node is None:
        print["List has no element"]
        return
    else:
        n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

7

Thêm chức năng trên vào lớp

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

6. Hãy tìm kiếm một phần tử trong danh sách đã tạo trước đó. Thực thi đoạn script sau

def traverse_list[self]:
    if self.start_node is None:
        print["List has no element"]
        return
    else:
        n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

8

Vì chúng ta đã chèn 5 vào danh sách liên kết nên hàm trên sẽ trả về giá trị true. Đầu ra sẽ trông như thế này

def traverse_list[self]:
    if self.start_node is None:
        print["List has no element"]
        return
    else:
        n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

9

Tạo một danh sách liên kết

Mặc dù chúng ta có thể thêm từng mục một bằng cách sử dụng bất kỳ chức năng chèn nào. Hãy tạo một hàm yêu cầu người dùng nhập số lượng phần tử trong nút rồi đến phần tử riêng lẻ và nhập phần tử đó vào danh sách liên kết

  if self.start_node is None:
        print["List has no element"]
        return

0

Trong đoạn mã trên, hàm

class LinkedList:
    def __init__[self]:
        self.start_node = None

31 trước tiên hỏi người dùng về số lượng mục trong danh sách. Tiếp theo, sử dụng vòng lặp for, người dùng được nhắc nhập giá trị cho từng nút, giá trị này sau đó được chèn vào danh sách được liên kết bằng hàm

  def insert_at_end[self, data]:
        new_node = Node[data]
        if self.start_node is None:
            self.start_node = new_node
            return
        n = self.start_node
        while n.ref is not None:
            n= n.ref
        n.ref = new_node;

7

Ảnh chụp màn hình sau đây hiển thị chức năng

class LinkedList:
    def __init__[self]:
        self.start_node = None

31 đang hoạt động

Xóa phần tử

Trong phần này, chúng ta sẽ xem các cách khác nhau để xóa một phần tử khỏi danh sách liên kết đơn

Xóa từ đầu

Việc xóa một phần tử hoặc mục từ đầu danh sách được liên kết rất đơn giản. Chúng ta phải đặt tham chiếu của

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

4 cho nút thứ hai, điều mà chúng ta có thể thực hiện bằng cách chỉ cần gán giá trị của tham chiếu của nút bắt đầu [đang trỏ đến nút thứ hai] cho nút bắt đầu như hình bên dưới

  if self.start_node is None:
        print["List has no element"]
        return

1

Trong đoạn mã trên, trước tiên chúng tôi kiểm tra xem danh sách có trống hay không. Nếu danh sách trống ta hiển thị thông báo danh sách không có phần tử cần xóa. Mặt khác, chúng tôi gán giá trị của

class LinkedList:
    def __init__[self]:
        self.start_node = None

35 cho

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

4.

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

4 bây giờ sẽ trỏ tới phần tử thứ hai. Thêm hàm

class LinkedList:
    def __init__[self]:
        self.start_node = None

38 vào lớp

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

6

Xóa ở cuối

Để xóa một phần tử khỏi cuối danh sách, chúng ta chỉ cần lặp qua danh sách được liên kết cho đến phần tử cuối cùng thứ hai, sau đó chúng ta cần đặt tham chiếu của phần tử cuối cùng thứ hai thành none, điều này sẽ chuyển đổi phần tử cuối cùng thứ hai thành

Kịch bản cho chức năng

class LinkedList:
    def __init__[self]:
        self.start_node = None

40 như sau

  if self.start_node is None:
        print["List has no element"]
        return

2

Thêm đoạn mã trên vào lớp

class LinkedList:
    def __init__[self]:
        self.start_node = None

41

Xóa theo giá trị mặt hàng

Để xóa phần tử theo giá trị, trước tiên chúng ta phải tìm nút chứa phần tử có giá trị được chỉ định và sau đó xóa nút. Tìm mục có giá trị được chỉ định khá giống với tìm kiếm mục. Sau khi tìm thấy mục cần xóa, tham chiếu của nút trước mục đó được đặt thành nút tồn tại sau mục bị xóa. Nhìn vào đoạn script sau

Trong đoạn script trên, trước tiên chúng tôi kiểm tra xem danh sách có trống không. Tiếp theo ta kiểm tra xem phần tử cần xóa có nằm ở đầu danh sách liên kết không. Nếu phần tử được tìm thấy ngay từ đầu, chúng tôi sẽ xóa nó bằng cách đặt nút đầu tiên thành tham chiếu của nút đầu tiên [về cơ bản là nút thứ hai]

Cuối cùng, nếu không tìm thấy phần tử ở chỉ mục đầu tiên, chúng ta lặp qua danh sách liên kết và kiểm tra xem giá trị của nút được lặp có bằng giá trị cần xóa không. Nếu so sánh trả về true, chúng tôi đặt tham chiếu của nút trước cho nút tồn tại sau nút đang bị xóa

Kiểm tra chức năng xóa

Hãy kiểm tra các chức năng xóa mà chúng tôi vừa tạo. Nhưng trước đó, hãy thêm một số dữ liệu giả vào danh sách được liên kết của chúng tôi bằng cách sử dụng tập lệnh sau

  if self.start_node is None:
        print["List has no element"]
        return

3

Đoạn script trên chèn 5 phần tử vào danh sách liên kết. Nếu bạn duyệt qua danh sách, bạn sẽ thấy các mục sau

  if self.start_node is None:
        print["List has no element"]
        return

4

Trước tiên hãy xóa một mục từ đầu

  if self.start_node is None:
        print["List has no element"]
        return

5

Bây giờ nếu bạn duyệt qua danh sách, bạn sẽ thấy đầu ra sau

  if self.start_node is None:
        print["List has no element"]
        return

6

Bây giờ hãy xóa một phần tử từ cuối

  if self.start_node is None:
        print["List has no element"]
        return

7

Danh sách hiện chứa các mục sau

  if self.start_node is None:
        print["List has no element"]
        return

8

Cuối cùng, hãy xóa một phần tử theo giá trị, giả sử 30

  if self.start_node is None:
        print["List has no element"]
        return

9

Bây giờ nếu bạn duyệt qua danh sách, bạn sẽ không thấy mục 30

Đảo ngược danh sách liên kết

Để đảo ngược danh sách liên kết, bạn cần có ba biến,

class LinkedList:
    def __init__[self]:
        self.start_node = None

42,

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

9 và

class LinkedList:
    def __init__[self]:
        self.start_node = None

44.

class LinkedList:
    def __init__[self]:
        self.start_node = None

42 sẽ theo dõi nút trước đó,

class LinkedList:
    def __init__[self]:
        self.start_node = None

44 sẽ theo dõi nút tiếp theo,

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

9 sẽ tương ứng với nút hiện tại

Chúng tôi bắt đầu vòng lặp while bằng cách gán nút bắt đầu cho biến

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

9 và biến

class LinkedList:
    def __init__[self]:
        self.start_node = None

42 được khởi tạo thành none. Vòng lặp thực hiện cho đến khi

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

9 trở thành không. Trong vòng lặp while, bạn cần thực hiện các chức năng sau

• Gán giá trị tham chiếu của nút hiện tại cho

  class LinkedList:
      def __init__[self]:
          self.start_node = None
  

  44
• Đặt giá trị tham chiếu của nút hiện tại

      n = self.start_node
          while n is not None:
              print[n.item , " "]
              n = n.ref
  

  9 thành

  class LinkedList:
      def __init__[self]:
          self.start_node = None
  

  42
• Đặt biến

  class LinkedList:
      def __init__[self]:
          self.start_node = None
  

  42 thành nút hiện tại

      n = self.start_node
          while n is not None:
              print[n.item , " "]
              n = n.ref
  

  9
• Đặt nút hiện tại

      n = self.start_node
          while n is not None:
              print[n.item , " "]
              n = n.ref
  

  9 thành giá trị của nút

  class LinkedList:
      def __init__[self]:
          self.start_node = None
  

  44

Khi kết thúc vòng lặp, biến

class LinkedList:
    def __init__[self]:
        self.start_node = None

42 sẽ trỏ đến nút cuối cùng, chúng ta cần biến nó thành nút đầu tiên nên chúng ta đặt giá trị biến

class LinkedList:
    def __init__[self]:
        self.start_node = None

59 thành

class LinkedList:
    def __init__[self]:
        self.start_node = None

42. Vòng lặp while sẽ làm cho mỗi nút trỏ tới nút trước của nó, dẫn đến danh sách liên kết đảo ngược. Kịch bản như sau

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

0

Thêm chức năng trên vào lớp

    n = self.start_node
        while n is not None:
            print[n.item , " "]
            n = n.ref

6. Tạo một danh sách các số ngẫu nhiên được liên kết và sau đó xem liệu bạn có thể đảo ngược nó bằng cách sử dụng hàm

class LinkedList:
    def __init__[self]:
        self.start_node = None

62 hay không

Phần kết luận

Trong bài này, chúng ta bắt đầu thảo luận về danh sách liên kết đơn. Chúng ta đã thấy các chức năng khác nhau có thể được thực hiện trên danh sách được liên kết, chẳng hạn như duyệt qua danh sách được liên kết, chèn các mục vào danh sách được liên kết, tìm kiếm và đếm các mục trong danh sách được liên kết, xóa các mục khỏi danh sách được liên kết và đảo ngược một danh sách được liên kết

Đây là Phần 1 của loạt bài viết về danh sách liên kết. Trong phần tiếp theo [sắp ra mắt], chúng ta sẽ xem cách sắp xếp danh sách liên kết đơn, cách hợp nhất các danh sách liên kết đã sắp xếp và cách loại bỏ chu trình khỏi danh sách liên kết đơn

Làm cách nào để chèn một nút tại một vị trí cụ thể trong danh sách được liên kết Python?

Chúng ta có thể sử dụng chỉ mục trong danh sách được liên kết không?

Bạn có thể thêm các nút mới vào bất kỳ đâu trong danh sách được liên kết không?

Làm cách nào để chèn một nút tại một vị trí cụ thể trong danh sách được liên kết trong C?