Python - Danh sách được Liên kết

Danh sách liên kết là một chuỗi các phần tử dữ liệu, được kết nối với nhau thông qua các liên kết. Mỗi phần tử dữ liệu chứa một kết nối đến một phần tử dữ liệu khác dưới dạng một con trỏ. Python không có danh sách liên kết trong thư viện tiêu chuẩn của nó. Chúng tôi triển khai khái niệm danh sách liên kết bằng cách sử dụng khái niệm các nút như đã thảo luận trong chương trước. Chúng ta đã thấy cách chúng ta tạo một lớp nút và cách duyệt các phần tử của một nút. Trong chương này, chúng ta sẽ nghiên cứu các loại danh sách liên kết được gọi là danh sách liên kết đơn. Trong kiểu cấu trúc dữ liệu này, chỉ có một liên kết giữa hai phần tử dữ liệu bất kỳ. Chúng tôi tạo một danh sách như vậy và tạo các phương pháp bổ sung để chèn, cập nhật và xóa các phần tử khỏi danh sách.

Tạo danh sách được liên kết

Danh sách liên kết được tạo bằng cách sử dụng lớp nút mà chúng ta đã nghiên cứu trong chương trước. Chúng ta tạo một đối tượng Node và tạo một lớp khác để sử dụng đối tượng ode này. Chúng tôi truyền các giá trị thích hợp qua đối tượng nút để trỏ đến các phần tử dữ liệu tiếp theo. Chương trình dưới đây tạo danh sách liên kết với ba phần tử dữ liệu. Trong phần tiếp theo, chúng ta sẽ xem cách duyệt qua danh sách liên kết.

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None

class SLinkedList:
    def __init__(self):
        self.headval = None

list1 = SLinkedList()
list1.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")
# Link first Node to second node
list1.headval.nextval = e2

# Link second Node to third node
e2.nextval = e3

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

Danh sách liên kết đơn có thể được duyệt chỉ theo hướng forwrad bắt đầu từ phần tử dữ liệu đầu tiên. Chúng tôi chỉ cần in giá trị của phần tử dữ liệu tiếp theo bằng cách gán con trỏ của nút tiếp theo với phần tử dữ liệu hiện tại.

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None

class SLinkedList:
    def __init__(self):
        self.headval = None

    def listprint(self):
        printval = self.headval
        while printval is not None:
            print (printval.dataval)
            printval = printval.nextval

list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")

# Link first Node to second node
list.headval.nextval = e2

# Link second Node to third node
e2.nextval = e3

list.listprint()

Khi đoạn mã trên được thực thi, nó tạo ra kết quả sau:

Mon
Tue
Wed

Chèn vào một danh sách được liên kết

Chèn phần tử trong danh sách liên kết bao gồm việc gán lại các con trỏ từ các nút hiện có cho nút mới được chèn. Tùy thuộc vào việc phần tử dữ liệu mới đang được chèn ở đầu hay ở giữa hoặc ở cuối danh sách được liên kết, chúng ta có các tình huống dưới đây.

Chèn vào đầu danh sách được liên kết

Điều này liên quan đến việc trỏ con trỏ tiếp theo của nút dữ liệu mới đến phần đầu hiện tại của danh sách được liên kết. Vì vậy, phần đầu hiện tại của danh sách được liên kết trở thành phần tử dữ liệu thứ hai và nút mới trở thành phần đầu của danh sách được liên kết.

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None

class SLinkedList:
    def __init__(self):
        self.headval = None

# Print the linked list
    def listprint(self):
        printval = self.headval
        while printval is not None:
            print (printval.dataval)
            printval = printval.nextval
    def AtBegining(self,newdata):
        NewNode = Node(newdata)

# Update the new nodes next val to existing node
        NewNode.nextval = self.headval
        self.headval = NewNode

list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")

list.headval.nextval = e2
e2.nextval = e3

list.AtBegining("Sun")

list.listprint()

Khi đoạn mã trên được thực thi, nó tạo ra kết quả sau:

Sun
Mon
Tue
Wed

Chèn vào cuối danh sách được liên kết

Điều này liên quan đến việc trỏ con trỏ tiếp theo của nút cuối cùng hiện tại của danh sách được liên kết đến nút dữ liệu mới. Vì vậy, nút cuối cùng hiện tại của danh sách liên kết trở thành nút dữ liệu cuối cùng thứ hai và nút mới trở thành nút cuối cùng của danh sách liên kết.

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None

class SLinkedList:
    def __init__(self):
        self.headval = None

# Function to add newnode
    def AtEnd(self, newdata):
        NewNode = Node(newdata)
        if self.headval is None:
            self.headval = NewNode
            return
        laste = self.headval
        while(laste.nextval):
            laste = laste.nextval
        laste.nextval=NewNode

# Print the linked list
    def listprint(self):
        printval = self.headval
        while printval is not None:
            print (printval.dataval)
            printval = printval.nextval


list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")

list.headval.nextval = e2
e2.nextval = e3

list.AtEnd("Thu")

list.listprint()

Khi đoạn mã trên được thực thi, nó tạo ra kết quả sau:

Mon
Tue
Wed
Thu

Chèn vào giữa hai nút dữ liệu

Điều này liên quan đến việc mã hóa con trỏ của một nút cụ thể để trỏ đến nút mới. Điều đó có thể thực hiện được bằng cách chuyển vào cả nút mới và nút hiện có, sau đó nút mới sẽ được chèn vào. Vì vậy, chúng tôi xác định một lớp bổ sung sẽ thay đổi con trỏ tiếp theo của nút mới thành con trỏ tiếp theo của nút giữa. Sau đó, gán nút mới cho con trỏ tiếp theo của nút giữa.

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None

class SLinkedList:
    def __init__(self):
        self.headval = None

# Function to add node
    def Inbetween(self,middle_node,newdata):
        if middle_node is None:
            print("The mentioned node is absent")
            return

        NewNode = Node(newdata)
        NewNode.nextval = middle_node.nextval
        middle_node.nextval = NewNode

# Print the linked list
    def listprint(self):
        printval = self.headval
        while printval is not None:
            print (printval.dataval)
            printval = printval.nextval


list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Thu")

list.headval.nextval = e2
e2.nextval = e3

list.Inbetween(list.headval.nextval,"Fri")

list.listprint()

Khi đoạn mã trên được thực thi, nó tạo ra kết quả sau:

Mon
Tue
Fri
Thu

Loại bỏ một biểu mẫu Mục một Danh sách đã thích

Chúng ta có thể xóa một nút hiện có bằng cách sử dụng khóa cho nút đó. Trong chương trình dưới đây, chúng tôi xác định vị trí nút trước đó của nút sẽ bị xóa. Sau đó trỏ con trỏ tiếp theo của nút này tới nút tiếp theo của nút cần xóa.

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

class SLinkedList:
    def __init__(self):
        self.head = None

    def Atbegining(self, data_in):
        NewNode = Node(data_in)
        NewNode.next = self.head
        self.head = NewNode
		
# Function to remove node
    def RemoveNode(self, Removekey):

        HeadVal = self.head

        if (HeadVal is not None):
            if (HeadVal.data == Removekey):
                self.head = HeadVal.next
                HeadVal = None
                return

        while (HeadVal is not None):
            if HeadVal.data == Removekey:
                break
            prev = HeadVal
            HeadVal = HeadVal.next

        if (HeadVal == None):
            return

        prev.next = HeadVal.next

        HeadVal = None

    def LListprint(self):
        printval = self.head
        while (printval):
            print(printval.data),
            printval = printval.next


llist = SLinkedList()
llist.Atbegining("Mon")
llist.Atbegining("Tue")
llist.Atbegining("Wed")
llist.Atbegining("Thu")
llist.RemoveNode("Tue")
llist.LListprint()

Khi đoạn mã trên được thực thi, nó tạo ra kết quả sau:

Thu
Wed
Mon