Hướng dẫn what is linked list in python with example? - danh sách được liên kết trong python với ví dụ là gì?

Một danh sách được liên kết là một chuỗi các yếu 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 với phần tử dữ liệu khác dưới dạng 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 thực hiện khái niệm danh sách được liên kết bằng cách sử dụng khái niệm các nút như được thảo luận trong chương trước.

Chúng tôi đã thấy cách chúng tôi tạo một lớp nút và cách đi qua các yếu tố của một nút. Trong chương này, chúng tôi sẽ nghiên cứu các loại danh sách được liên kết được gọi là danh sách liên kết đơn lẻ. Trong loại cấu trúc dữ liệu này, chỉ có một liên kết giữa bất kỳ hai phần tử dữ liệu nào. Chúng tôi tạo một danh sách như vậy và tạo các phương thức bổ sung để chèn, cập nhật và xóa các yếu tố khỏi danh sách.

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

Một danh sách được liên kết được tạo bằng cách sử dụng lớp nút mà chúng tôi đã nghiên cứu trong chương trước. Chúng tôi tạo một đối tượng nút và tạo một lớp khác để sử dụng đối tượng ODE này. Chúng tôi chuyển các giá trị thích hợp thông 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 ra danh sách được liên kết với ba yếu tố dữ liệu. Trong phần tiếp theo, chúng ta sẽ thấy cách đi qua 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

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

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

Danh sách liên kết đơn lẻ có thể được đi qua chỉ theo hướng bắt đầu hình thức 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 cho phần tử dữ liệu hiện tại.

Thí dụ

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()

Đầu ra

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

Mon
Tue
Wed

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

Phần tử chèn vào danh sách được liên kết liên quan đến việc chỉ định lại các con trỏ từ các nút hiện có đến nút mới được chèn. Tùy thuộc vào việc phần tử dữ liệu mới được chèn vào đầu hay ở giữa hay ở cuối danh sách được liên kết, chúng tôi có các kịch bản dưới đây.

Chèn vào đầu

Đ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 vào đầu hiện tại của danh sách được liên kết. Vì vậy, đầ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 người đứng đầu của danh sách được liên kết.

Thí dụ

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()

Đầu ra

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

Sun
Mon
Tue
Wed

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

Phần tử chèn vào danh sách được liên kết liên quan đến việc chỉ định lại các con trỏ từ các nút hiện có đến nút mới được chèn. Tùy thuộc vào việc phần tử dữ liệu mới được chèn vào đầu hay ở giữa hay ở cuối danh sách được liên kết, chúng tôi có các kịch bản dưới đây.

Thí dụ

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()

Đầu ra

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

Mon
Tue
Wed
Thu

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

Phần tử chèn vào danh sách được liên kết liên quan đến việc chỉ định lại các con trỏ từ các nút hiện có đến nút mới được chèn. Tùy thuộc vào việc phần tử dữ liệu mới được chèn vào đầu hay ở giữa hay ở cuối danh sách được liên kết, chúng tôi có các kịch bản dưới đây.

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()

Đầu ra

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

Mon
Tue
Fri
Thu

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

Phần tử chèn vào danh sách được liên kết liên quan đến việc chỉ định lại các con trỏ từ các nút hiện có đến nút mới được chèn. Tùy thuộc vào việc phần tử dữ liệu mới được chèn vào đầu hay ở giữa hay ở cuối danh sách được liên kết, chúng tôi có các kịch bản dưới đây.

Thí dụ

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()

Đầu ra

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

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()

Danh sách được liên kết với ví dụ là gì?

Các loại danh sách được liên kết trong Python là gì?

Danh sách được liên kết là gì?