Vấn đề mã hóa hàng ngày: Xóa chỉ mục thứ k khỏi danh sách được liên kết trong một lượt

Xóa chỉ mục thứ k khỏi danh sách được liên kết trong một lượt

Chào mừng trở lại, với một vấn đề khác cần giải quyết! Hôm nay, chúng ta đang giải quyết các danh sách được liên kết và loại bỏ các phần tử của chúng. Chúng ta sẽ thảo luận một chút về danh sách được liên kết là gì, chúng ta sẽ tạo một danh sách và xem cách loại bỏ các phần tử khỏi danh sách đó.

Trước khi bắt đầu, các tuyên bố từ chối trách nhiệm thông thường:

• Những vấn đề này được cung cấp bởi bản tin tuyệt vời Vấn đề mã hóa hàng ngày mà bạn có thể đăng ký đây . Kiểm tra nó ra, và cố gắng giải quyết những thách thức của bạn quá!

• Tôi không phải là một lập trình viên chuyên nghiệp: Chỉ là một người thích chia sẻ ảnh của mình! Nếu bạn tình cờ có một giải pháp tốt hơn hoặc nhanh hơn cho một thuật toán, vui lòng gửi nó trong phần bình luận! Tôi muốn tìm hiểu thêm về điều này!

  
  

Đủ ado; hãy chuyển sang vấn đề!

Vấn đề này ban đầu được hỏi bởi Amazon

Cho một danh sách được liên kết và một số nguyên k , xóa nút thứ k khỏi cuối danh sách và trả về phần đầu của danh sách.

k được đảm bảo nhỏ hơn độ dài của danh sách.

Làm điều này trong một lần.

Được rồi, hãy giải thích một chút điều gì đang xảy ra ở đây: chúng ta được cung cấp một danh sách được liên kết và một phần tử chỉ mục k cần xóa khỏi danh sách. Sau đó, chúng ta nên trả lại phần đầu của danh sách được liên kết.

Cuối cùng, chúng ta phải thực hiện tất cả những điều này chỉ trong một lượt, nghĩa là chúng ta không thể lặp lại danh sách nhiều lần.

Chúng tôi cũng được đảm bảo rằng chỉ mục k được chứa trong danh sách, vì vậy chúng tôi không phải kiểm tra xem nó có vượt quá độ dài thực của danh sách hay không.

Hôm nay chúng ta sẽ sử dụng Go để xây dựng thuật toán vì cú pháp của nó rất tuyệt vời cho loại công việc này, đồng thời, nó vẫn khá đơn giản để hiểu.

Hãy bắt đầu lại từ đầu: xây dựng một danh sách liên kết đơn giản.

Danh sách liên kết

Khái niệm đằng sau danh sách được liên kết khá đơn giản: đó là một danh sách gồm các đối tượng (thường được gọi là các nút ) và mỗi nút phải có ít nhất hai thuộc tính: một giá trị (thứ thực sự chứa trong nút đó) và một liên kết đến nút tiếp theo.

Thông thường, một con trỏ được sử dụng như một liên kết để chuyển từ nút này sang nút khác.

Ngoài ra, nút đầu tiên của danh sách thường được gọi là đầu danh sách, đây cũng là nút mà chúng tôi được yêu cầu trả về trong bài toán.

Đây là một ví dụ đồ họa:

Nút đầu tiên bên trái là đầu danh sách, chứa giá trị v₀ và con trỏ bộ nhớ P(n₁) chuyển hướng danh sách đến nút n₁ tiếp theo. Nút sau n₁ sẽ chứa giá trị của nó và một con trỏ P(n₂) tới nút tiếp theo, v.v.

Tất nhiên, nút cuối cùng sẽ không có gì để trỏ tới, vì vậy giá trị của con trỏ của nó sẽ là null .

Hãy xem mã để tạo một cái!

Mã này khá đơn giản: chúng tôi tạo hai cấu trúc, một cho nút bên trong và một cho danh sách được liên kết.

• Nút, như chúng ta vừa thấy, sẽ có hai thuộc tính, cụ thể là thuộc tính Giá Value và thuộc tính Next , chứa loại *Node làm con trỏ tới nút tiếp theo.

• Danh sách liên kết, một cấu trúc để “khởi tạo” danh sách liên kết, danh sách này sẽ chỉ có một thuộc tính là Head danh sách.

  
  

Sau đó, chúng ta chỉ cần khởi tạo danh sách trong hàm chính và đặt cho phần đầu của nó một nút có giá trị ngẫu nhiên là 10.

Chìa khóa đằng sau việc hiểu danh sách được liên kết là giờ đây nút Head , vì thuộc loại Node , vốn dĩ sẽ có thuộc tính Next , thuộc tính này sẽ chứa nút tiếp theo. Nút cuối cùng này sau đó sẽ có thuộc tính Next của nó để chuyển sang nút tiếp theo, v.v.

Mọi thứ sẽ rõ ràng hơn khi chúng tôi thêm một số nút vào danh sách, vì vậy hãy làm điều đó! Chúng tôi có hai lựa chọn: hoặc chúng tôi thực hiện thủ công, một công việc thực sự tẻ nhạt hoặc chúng tôi viết một phương thức cho lớp danh sách được liên kết để thêm một số nút khác. Hãy cùng kiểm tra nào!

Thêm nút: Danh sách có thể thay đổi trong ngụy trang

Ngay cả khi bạn có ít kinh nghiệm lập trình, trong hầu hết mọi ngôn ngữ lập trình, một trong những khái niệm đầu tiên bạn nên nghe là sự khác biệt giữa danh sách có thể thay đổi và danh sách không thể thay đổi .

Như tên gợi ý, danh sách có thể thay đổi là danh sách mà bạn có thể thao tác và thêm phần tử vào . Thay vào đó, các bất biến có kích thước cố định và không thể thêm các phần tử mới. Nhưng tại sao lại như vậy?

Immutable list nằm liền kề trong bộ nhớ , nghĩa là các phần tử của chúng được lưu trong bộ nhớ một cách tuần tự : đối với danh sách có 3 phần tử, nếu phần tử đầu tiên được lưu ở 0x00 thì phần tử thứ hai sẽ ở 0x01 và phần tử cuối cùng ở 0x02.

Đó là lý do tại sao việc lặp qua một mảng cố định, một danh sách bất biến hoặc một bộ trong Python rất nhanh bởi vì CPU chỉ đơn giản gọi lại từng chỉ mục bộ nhớ.

Mặt khác, các danh sách có thể thay đổi chỉ liền kề trong bộ nhớ khi được khởi tạo lần đầu tiên: tại thời điểm đó, nếu các phần tử được thêm vào, chúng sẽ không còn tuần tự nữa. Vì vậy, làm thế nào chúng ta có thể lặp qua chúng?

Chà, bởi vì phần tử cuối cùng của lần khởi tạo đầu tiên sẽ có một con trỏ mà phần tử được thêm vào sau nó , con trỏ này sẽ mang đến cho chúng ta phần tử to được nối thêm, v.v. Vì vậy, có, danh sách có thể thay đổi thực sự thường là danh sách được liên kết trong ngụy trang!

Bây giờ, hãy xem mã:

Chúng tôi đã thêm phương thức AddNode vào các phương thức của danh sách được liên kết của chúng tôi. Quá trình thêm một nút diễn ra như sau:

• Đầu tiên, chúng tôi lưu trữ giá trị Head trong một biến có tên là current

• Tiếp theo, chúng tôi lặp lại danh sách được liên kết cập nhật biến current với nút tiếp theo mỗi lần, cho đến khi nút tiếp theo là null. Khi nút mà chúng tôi hiện đang ở trên có một con trỏ null, chúng tôi biết rằng chúng tôi đang ở nút cuối cùng của danh sách.

• Cuối cùng, chúng tôi cập nhật nút cuối cùng này bằng một nút mới và một giá trị mới (con trỏ Next của nút mới này sẽ được đặt thành null nếu chúng tôi để trống)

  
  

Về mặt đồ họa, quá trình này giống như sau:

Chúng ta có thể kiểm tra chức năng chính xác của phương thức này trong chức năng chính, in ra các giá trị của các nút trong danh sách được liên kết.

Loại bỏ nút

Bây giờ là phần cuối cùng và giải pháp cho vấn đề của chúng ta: xóa một nút có chỉ mục chính xác. Trước hết, việc xóa một nút khỏi danh sách được liên kết có nghĩa là gì? Nếu chúng ta nghĩ về nó, một nút trong danh sách được liên kết chỉ tồn tại nếu nó được kết nối với nút trước đó , phải không?

Ví dụ: nếu chúng tôi cung cấp cho n-1ᵗʰ giá trị Next là null, chúng tôi có thể ngắt kết nối giá trị nᵗʰ khỏi danh sách.

Nếu phần tử chúng ta muốn xóa không phải là phần tử cuối cùng thì sao? Chà, chúng ta có thể hủy liên kết phần tử bằng cách kết nối phần trước với phần tiếp theo của nó !

Vậy để loại bỏ phần tử kᵗʰ ta phải tìm phần tử k-1ᵗʰ và liên kết nó với nút k+1ᵗʰ. Chúng tôi sẽ cần lưu trữ nút trước đó (k-1ᵗʰ) .

Rõ ràng, chúng ta không thể lập chỉ mục trực tiếp danh sách : hãy thử một cái gì đó như linkedlist[n] sẽ chỉ gây ra lỗi. Mặc dù vậy, với điều này, chúng ta có thể coi phần đầu của danh sách là chỉ mục 0 và nút tiếp theo của nó là chỉ mục 1, v.v. và chúng ta cũng có thể lặp qua các nút, như chúng ta đã làm trước đây.

Những gì chúng ta có thể làm sau đó là triển khai một bộ đếm để theo dõi nút mà chúng ta đang truy cập!

Hãy mã nó sau đó.

Hãy xem xét hàm RemoveNode chấp nhận thuộc index mục. Sau đó, chúng tôi khởi tạo ba biến:

• previousNode , sẽ giữ nút trước đó

• current , nút này sẽ giữ nút mà chúng ta đang bật trong vòng lặp

• counter , ban đầu bằng 0, sẽ giữ vị trí của chúng ta trong danh sách

  
  

Hãy tạm bỏ qua khối if đầu tiên và thay vào đó hãy tập trung vào vòng lặp for. Chúng tôi bắt đầu lặp cho đến khi biến bộ counter của chúng tôi nhỏ hơn index của chúng tôi : mỗi vòng lặp sau đó sẽ cập nhật nút trước đó với nút hiện tại và chuyển sang cập nhật nút hiện tại và bộ đếm.

Khi vòng lặp bị ngắt, điều đó có nghĩa là chúng ta đang ở ngay nút trước chỉ mục mong muốn của mình: chúng ta chỉ cần cập nhật con trỏ của nút trước đó, prev.Next , với nút tiếp theo trong danh sách từ nút này mà chúng ta đang ở. sẽ là current.Next . Cuối cùng, chúng tôi trả lại phần đầu của danh sách được liên kết.

Bây giờ điều gì sẽ xảy ra nếu chỉ mục cần loại bỏ là phần đầu có chỉ số bằng 0? Vòng lặp sẽ không bao giờ bắt đầu vì nó sẽ bắt đầu với counter = 0 và index = 0 và điều kiện sẽ sai ngay lập tức. Chúng ta có thể quản lý trường hợp đầu tiên này với khối if ở trên cùng.

Về cơ bản, nếu chỉ mục là 0, chúng ta có thể cập nhật trực tiếp phần đầu của danh sách được liên kết với nút bên cạnh nó và trả lại nó. Tôi muốn bạn chú ý, đặc biệt là dòng 31: Go, như trong nhiều ngôn ngữ khác, chuyển các thuộc tính cho các hàm theo giá trị , nghĩa là hàm giữ lại một bản sao của đối tượng đã truyền, không phải đối tượng thực mà bạn đang chuyển .

Khái niệm này được thấy rõ trong ví dụ này:

 package main import "fmt" func printMemoryAddress(value int) { fmt.Println(&value) } func main() { a := 10 fmt.Println(&a) printMemoryAddress(a) } // 0xc00010a000 // 0xc00010a008 // Program exited.

Chúng tôi tạo một hàm để in địa chỉ bộ nhớ của giá trị được truyền dưới dạng thuộc tính. Sau đó, trong hàm chính, chúng ta tạo một biến a và in ra địa chỉ bộ nhớ của nó. Sau đó, chúng tôi chuyển cùng một biến cho hàm và in địa chỉ bộ nhớ của nó.

Như bạn có thể thấy, nếu bạn thử, kết quả sẽ khác: đó là vì các thuộc tính được truyền cho hàm dưới dạng giá trị, nghĩa là một bản sao của a được tạo chỉ với mục đích truyền nó cho hàm.

Quay lại danh sách liên kết của chúng ta, chúng ta phải sử dụng con trỏ để lấy đầu thực cho cùng một vấn đề ở trên. Vì vậy, để đến được ll.Node “thực”, chúng ta phải nhớ lại con trỏ của nó, *ll.Node và di chuyển nó xa hơn với *ll.Node = *ll.Node.Next .

Trong chức năng chính, chúng tôi thêm các cuộc gọi vào phương thức, ví dụ: gọi ll.RemoveNode(0) và ll.RemoveNode(2) và chúng tôi có thể kiểm tra kết quả xem nút 0 và nút 2 sẽ bị thiếu.

Phần kết luận

Chúng tôi đã làm cho nó đến cùng!

Nếu bạn đọc cho đến thời điểm này, toàn bộ lòng biết ơn của tôi dành cho bạn. Nếu bạn sẵn sàng để lại một hoặc hai lượt thích và chia sẻ bài viết, nó sẽ giúp tôi có một ngày vui vẻ và giúp tôi tiếp tục viết những bài báo này!

Hẹn gặp lại bạn trong bài viết tiếp theo, và như mọi khi, cảm ơn vì đã đọc.

Nicola