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[]0