Hỏi đáp

Chia sẻ kiến thức, cùng nhau phát triển

Đặt câu hỏi

Hỏi rõ hơn về cơ chế hoạt động của code sau

3 năm trước 551 lượt xem 5 bình luận

python-3.x

Mình có một đoạn code sau:

Python


class LinkedListNode:
    def __init__(self, data):
        self.data = data
        self.next = None
class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
    def insert(self, data):
        node = LinkedListNode(data)
        if not self.head:
            self.head = node
        else:
            self.tail.next = node
        self.tail = node

l1 = LinkedList()
total_inp = inp(input())
for i in range(total_inp):
    inp = int(input())
    l1.insert(inp)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

đây là một bài mình lấy trên HackerRank mà chưa hiểu rõ cơ chế lắm. Sau một lúc mày mò, mình biết cách để lấy dữ liệu như sau
với input là 3 4 2 3 (khoảng trống tương ứng với một lần nhập dữ liệu trước khoảng trống rồi enter)
để lấy dữ liệu theo thứ tự được đưa vào, mình đã lam như sau:

Python


print(l1.head.data)
print(l1.head.next.data)
print(l1.head.next.next.data)
1
2
3

Có thể thấy cách này không khả thi lắm với dữ liệu truyền vào tới hàng trăm, nghìn số.

Vậy cho mình hỏi kĩ về cơ chế của đoạn code trên và cách để lấy giá trị nhanh nhất ạ. Xin chân thành cảm ơn

Bình luận

Để bình luận, bạn cần đăng nhập bằng tài khoản Howkteam.

Đăng nhập

K9 SuperAdmin, KquizAdmin, KquizAuthor đã bình luận 3 năm trước

cấu trúc này không phải để làm chuyện muốn lấy phần tử nào thì lấy.

Trả lời Báo cáo

Nông Thanh Toàn Editor, Author, KquizAuthor đã bình luận 3 năm trước

Mình cảm thấy đây là một câu hỏi rất thú vị, dưới đây là quan điểm của mình:

Thứ nhất, nó gần giống như một loại cấu trúc dữ liệu, đó là linked list, tức là, một danh sách mà từ phần tử này có thể tiến đến phần tử ngay cạnh nó (trong đoạn code trên, từ một phần tử l1 có thể tiến đến phần tử đứng kế tiếp nó trong l1).

Cụ thể, l1 chỉ là một Linkedlist và gồm 2 thuộc tính: head và tail.

Ở lần gọi insert đầu tiên, thì giá trị của l1.head được khởi tạo.

Ở các lần tiếp theo, thì chương trình thực hiện như sau: Nó nhảy vào l1.tail. Lúc này, l1.tail là một LinkedListNode, và do đó, nó nhảy vào next của l1.tail và gán cho l1.tail.next giá trị của một LinkedListNode khác (và lại xuất hiện next, thứ sẽ được dùng trong các lần gọi tiếp theo). Cụ thể, bạn có thể xem hình mình vẽ bên dưới: mỗi lần insert, sẽ chạy qua nhánh bên phải và thêm vào nhánh đó (đó là lí do tại sao bạn lại có thể gọi như vậy).

Và, mình cũng đã thử code hàm để lấy ra toàn bộ các phần tử của l1 theo thứ tự được đưa vào. Cụ thể, mình tạo thêm một thuộc tính length cho class LinkedList để lưu trữ số lượng giá trị mà nó nắm giữ (ban đầu = 0, và tăng thêm 1 mỗi lần gọi insert). sau đó, cũng trong class LinkedList, mình thêm vào một hàm show như sau:

def show(self):
        curr = 0
        valCurr = self.head
        while curr < self.length:
            print(valCurr.data)
            curr += 1
            valCurr = valCurr.next

Tuy nhiên, để có thể lấy một giá trị duy nhất tại một vị trí duy nhất, thì lại tốn nhiều thời gian hơn do phải duyệt qua toàn bộ l1 (hàm show có thể được thay đổi một chút để tạo ra chức năng này).

Gửi bạn ! Cảm ơn vì một câu hỏi lí thú.

Trả lời Báo cáo

Hỏi đáp

Chia sẻ kiến thức, cùng nhau phát triển

Hỏi rõ hơn về cơ chế hoạt động của code sau

Bình luận

Câu hỏi mới nhất

AD BLOCKER DETECTED