Delete Operation - Singly Linked List

Agar linked listda mavjud bo'lgan cur nodeni o'chirmoqchi bo'lsak, buni ikki bosqichqa qilishimiz mumkin.

1. cur nodedan oldingi prev node va keyingi next nodelarni topamiz.

prev and next nodes

1. prev nodeni cur nodedan keyingi nodega bog'laymiz.

link prev to next

Birinchi qadamda, prev va next nodelarni topishimiz kerak. next ni curning havolasidan foydalanib topish oson. Lekin biz prev ni topish uchun headdan boshlab o'tib chiqishimiz kerak, uzunligi N ga teng bo'lgan linked listda o'rtacha O(N) vaqt oladi. Shu sababli nodeni o'chirish vaqt murakkabligi O(N) bo'ladi.

Misol

an example

Keling yuqoridagi singly linked listdan node-6 ni o'chirishga harakat qilib ko'ramiz.

1. head node dan boshlab oldingi prev node node-23 ni topganimizcha linked listni o'tib chiqamiz.

2. prev nodeni next nodega bog'laymiz.

link prev to next

node-6 endi bizning singly linked listimizda emas.

Birinchi Nodeni o'chirish

Agar birinchi nodeni o'chirmoqchi bo'lsak bu biroz boshqacha bo'ladi.

Avval ta'kidlaganimizdek, linked listni ifodalash uchun bosh node sifatida head nodedan foydalanamiz, Bosh nodeimiz pastda misoldagi qora node-23.

black head node

Agar birinchi nodeni o'chirmoqchi bo'lsak, shunchaki keyingi nodeni head nodega biriktiramiz. Ya'ni o'chirishdan keyin node-6 head node bo'ladi.

delete head node

Linked list head nodedan boshlanad, shuning uchun endi node-23 yo'q.

Note

Oxirgi tugunni o'chirish haqida nima deyish mumkin? Shunga oʻxshash strategiyadan foydalanishimiz mumkinmi?

© Leetcode link