Một nút trong danh sách liên kết đơn phải có hai thuộc tính. val
và 2. val
là giá trị của nút hiện tại và next
là con trỏ/tham chiếu đến nút tiếp theo
Nếu muốn sử dụng danh sách liên kết kép thì cần thêm 1 thuộc tính prev
để chỉ nút trước đó trong danh sách liên kết. Giả sử tất cả các nút trong danh sách được liên kết đều được lập chỉ mục 0
Triển khai lớp MyLinkedList
MyLinkedList
của chúng tôiMyLinkedList[]
Khởi tạo đối tượngMyLinkedList
val
0 Lấy giá trị của nútval
1 trong danh sách liên kết. Nếu chỉ mục không hợp lệ, hãy trả lạival
2val
3 Thêm một nút có giá trịval
trước phần tử đầu tiên của danh sách liên kết. Sau khi chèn, nút mới sẽ là nút đầu tiên của danh sách liên kếtval
5 Nối một nút có giá trịval
làm phần tử cuối cùng của danh sách liên kếtval
7 Thêm một nút có giá trịval
trước nútval
1 trong danh sách liên kết. Nếunext
0 bằng độ dài của danh sách được liên kết, nút sẽ được thêm vào cuối danh sách được liên kết. Nếunext
0 lớn hơn chiều dài, nút sẽ không được chènnext
2 Xóa nútval
1 trong danh sách liên kết, nếu chỉ mục hợp lệ
ví dụ 1
Input
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
Output
[null, null, null, null, 2, null, 3]Explanation
MyLinkedList myLinkedList = new MyLinkedList[];
myLinkedList.addAtHead[1];
myLinkedList.addAtTail[3];
myLinkedList.addAtIndex[1, 2]; // linked list becomes 1->2->3
myLinkedList.get[1]; // return 2
myLinkedList.deleteAtIndex[1]; // now the linked list is 1->3
myLinkedList.get[1]; // return 3
Hạn chế
next
4- Vui lòng không sử dụng thư viện LinkedList tích hợp
- Tối đa
next
5 cuộc gọi sẽ được thực hiện tớinext
6,next
7,next
8,next
9 vàval
0
Suy nghĩ của tôi
Cá nhân tôi thích những nhiệm vụ như thế này. Nó có thể được giải quyết bằng một số cách khác nhau mà nếu chúng tôi mô tả chúng, bạn sẽ cảm thấy nhàm chán và mệt mỏi khi đọc từng ấy thông tin. Nhiệm vụ này có thể giúp bạn xây dựng hoặc cải thiện kỹ năng chia nhiệm vụ thành các phần nhỏ hơn. Một lần nữa, đó là kỹ năng cực kỳ quan trọng nếu bạn muốn trở thành một kỹ sư phần mềm giỏi. Nếu bạn đã có kinh nghiệm về thuật toán và cấu trúc dữ liệu, bạn có thể làm một số thứ như thế này
Giải pháp đơn giản nhất cho nhiệm vụHoàn toàn ổn khi giải quyết vấn đề theo cách này nhưng nó chỉ hoạt động khi bạn đã biết cách LinkedList hoạt động và bạn có thể triển khai nó từ đầu. Trong khi cách tiếp cận trên có thể giúp bạn tiết kiệm thời gian. Tôi khuyên bạn nên tìm hiểu sâu hơn và triển khai phiên bản LinkedList của riêng mình. Tôi khá chắc rằng nhiều bạn biết nó hoạt động như thế nào nhưng khi tôi yêu cầu bạn thực hiện thì một số bạn có thể gặp khó khăn
Tôi nghĩ rằng sau khi bạn đọc hoặc học một cái gì đó, bạn nên thực hiện những gì bạn vừa học. Nó sẽ giúp bạn hiểu cấu trúc dữ liệu này hoạt động như thế nào và nó có thể được sử dụng ở đâu. Kiến thức bạn có sẽ được ghi nhớ tốt hơn
lý luận
Như tôi đã nói, nhiệm vụ này là một ví dụ hoàn hảo về việc chúng ta có thể chia một nhiệm vụ lớn thành những nhiệm vụ nhỏ hơn. Vì vậy, hãy cố gắng hiểu làm thế nào để làm điều đó
Có vẻ như chúng ta cần triển khai ít nhất 5 phương pháp khác nhau. Đó là một điểm khởi đầu tuyệt vời. Trong khi có bức tranh toàn cảnh hơn trong đầu, chúng ta có thể tập trung vào bài toán con cụ thể mà mọi phương pháp đều phải giải quyết. Hãy giải quyết từng vấn đề nhỏ hơn
Theo phương thức mô tả, val
1có thể nhận chỉ mục của phần tử và trả về phần tử tại chỉ mục này nếu chúng ta có nó trong danh sách của mình. Nghe có vẻ khá đơn giản. Chúng tôi có danh sách với các phần tử, hãy lặp lại nó và theo dõi chỉ mục và chỉ mục hiện tại mà chúng tôi đã cung cấp. Nếu chúng bằng nhau, chúng tôi đã tìm thấy phần tử và có thể quay lại. Trong tất cả các trường hợp khác, chúng tôi trả về -1. Chú ý đến dòng 11. Chúng tôi sử dụng đầu vì nó lưu liên kết đến phần đầu của danh sách. Hãy ghi nhớ điều đó, chúng ta sẽ quay lại với nó
Ví dụ. chúng tôi có danh sách 1 -> 2 -> 3 -> 4 ->5
1 có chỉ số 0, 2 có chỉ số 1, v.v. Nếu chúng tôi đưa ra chỉ số 3, chúng tôi phải trả lại 4
val
0Phương pháp tiếp theo trong danh sách của chúng tôi là val
3, nó phải chèn giá trị vào phía trước danh sách của chúng tôi. cái này hơi khó. Chúng tôi có phần đầu lưu trữ liên kết đến phần đầu, vì vậy chúng tôi muốn đẩy phần tử tiếp theo và chèn giá trị được cung cấp ngay sau phần đầu. Điều đầu tiên chúng tôi làm là tạo Liên kết mới sẽ lưu trữ giá trị được cung cấp [sơ đồ bên dưới]. Đồng thời, chúng ta cần cập nhật mối quan hệ giữa các liên kết hiện có và liên kết mới. Thay vì sử dụng các từ, hãy xem một số hình ảnh, tôi hy vọng tôi sẽ giúp bạn hiểu khái niệm này
Trạng thái ban đầu của MyLinkedList
Chúng tôi đã tạo Liên kết mới với giá trị 5
Trạng thái của MyLinkedList sau khi chúng tôi cập nhật tất cả các liên kết
Chúng tôi cũng có một kích thước thay đổi ở đây để lưu trữ số lượng phần tử trong danh sách của chúng tôi
val
3Phương pháp tiếp theo là val
5, nó thực hiện gần giống như phương pháp trước, điểm khác biệt duy nhất là chúng tôi chèn giá trị của mình vào trước phần đuôi của danh sách
val
5Trạng thái ban đầu của MyLinkedList
Chúng tôi đã tạo một Liên kết mới với giá trị 7
Trạng thái của MyLinkedList sau khi chúng tôi cập nhật tất cả các liên kết
Phương thức tiếp theo là val
7 nó phải chèn một giá trị trong LinkedList tại một chỉ mục cụ thể được cung cấp dưới dạng tham số. Nút đầu tiên sau nút đầu có chỉ số 0, nút tiếp theo có chỉ số 1, v.v.
Giá trị và chỉ số của các nút trong MyLinkedList
Mục tiêu của chúng tôi là lặp lại chỉ mục đích và chèn giá trị vào chỉ mục đó. Hãy chèn giá trị 5 vào chỉ mục 1
Chúng tôi đã tạo một Liên kết mới với giá trị 5
Trạng thái của MyLinkedList sau khi chúng tôi cập nhật tất cả các liên kết
Phương pháp cuối cùng của chúng tôi để thực hiện là next
2. Nó thực hiện gần giống như chèn vào chỉ mục, ngoại trừ một điều, lần này chúng tôi xóa Liên kết. Bài này dài quá nên mình cung cấp ít ảnh và code cho dễ hiểu. Hãy xóa nút tại chỉ số 3