Node-luokka ja listan rakentaminen
Määritelkää Node-dataclass, rakentakaa listoja yhdistämällä solmuja käsin ja kirjoittakaa insert-, delete- ja print-apufunktiot osoitinmuutosten havainnollistamiseksi.
Node-luokka ja listan rakentaminen on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 1/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Valmistautuminen ohjelmointihaastatteluihin-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Mikä on linkitetty lista
Linkitetty lista on solmujen muodostama jono, jossa jokainen solmu tallentaa arvon ja osoittimen seuraavaan solmuun. Toisin kuin taulukoissa, solmut sijaitsevat hajallaan muistissa, joten indeksipohjaista O(1)-käyttöä ei ole. Vastineeksi saatte O(1)-aikaisen lisäämisen ja poistamisen mistä tahansa tunnetusta kohdasta ilman alkioiden siirtämistä.
Pythonissa kutakin solmua edustaa pieni luokka, jossa ovat val ja next. Solmujen ketjuttaminen muodostaa listan; viimeisen solmun next on None, joka ilmaisee listan lopun.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Build: 1 -> 2 -> 3 -> None
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
# Traverse and print
curr = head
while curr:
print(curr.val, end=' -> ')
curr = curr.next
print('None')Listojen rakentaminen taulukoista
Haastatteluissa saatte usein listan ja tehtäväksenne rakentaa sitä vastaavan linkitetyn listan tai päinvastoin. Apufunktiot build ja to_list kannattaa opetella ulkoa: build ketjuttaa solmut taulukon alkioista, ja to_list käy listan läpi ja kerää arvot helppoa tarkistamista varten.
Linkitetyn listan rakentaminen n alkiosta vie O(n)-aikaa ja O(n) tilaa. Dummy head -solmun käyttäminen yksinkertaistaa reunatapauksia, joissa ensimmäinen solmu saattaa vaihtua.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def build(arr):
dummy = ListNode(0)
curr = dummy
for val in arr:
curr.next = ListNode(val)
curr = curr.next
return dummy.next
def to_list(head):
result = []
while head:
result.append(head.val)
head = head.next
return result
head = build([1, 2, 3, 4, 5])
print(to_list(head)) # [1, 2, 3, 4, 5]Lisääminen alku- ja loppupäähän
Uuden solmun lisääminen alkupäähän on O(1): luokaa solmu, osoittakaa sen next vanhaan alkupäähän ja palauttakaa uusi solmu alkupääksi. Lisääminen loppupäähän edellyttää kulkemista viimeiseen solmuun (O(n)), minkä jälkeen uusi solmu yhdistetään listaan.
Dummy head -solmun käyttäminen poistaa tyhjän listan erityistapauksen kummassakin lisäyksessä, koska dummy.next on aina todellinen alkupää.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def insert_head(head, val):
return ListNode(val, head) # O(1)
def insert_tail(head, val):
new_node = ListNode(val)
if not head:
return new_node
curr = head
while curr.next:
curr = curr.next
curr.next = new_node
return head
head = None
for v in [1, 2, 3]:
head = insert_tail(head, v)
head = insert_head(head, 0)
curr = head
while curr:
print(curr.val, end=' -> ')
curr = curr.next
print('None') # 0 -> 1 -> 2 -> 3 -> NoneSolmun poistaminen arvon perusteella
Poistaaksenne ensimmäisen tietyn arvon sisältävän solmun ylläpitäkää prev-osoitinta yhden askeleen curr-osoittimen jäljessä. Kun curr.val == target, asettakaa prev.next = curr.next, jolloin solmu ohitetaan. Dummy head on tässä erityisen hyödyllinen, koska se poistaa todellisen alkupään solmun poistamisen erityistapauksen: prev voi aina aloittaa dummysta.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def delete_val(head, target):
dummy = ListNode(0)
dummy.next = head
prev, curr = dummy, head
while curr:
if curr.val == target:
prev.next = curr.next
break
prev, curr = curr, curr.next
return dummy.next
def to_list(h):
r = []
while h:
r.append(h.val)
h = h.next
return r
head = None
for v in [1, 2, 3, 2, 4]:
dummy2 = ListNode(v)
dummy2.next = head
head = dummy2 # build in reverse for speed
head = delete_val(head, 2)
print(to_list(head))Osoittimien muutosten havainnollistaminen
Yleinen virhe on kadottaa solmun viite osoittimia päivitettäessä. Tallenna aina next ennen sen korvaamista: saved = curr.next, ja määritä osoitin sitten uudelleen. Piirtäkää lista nuolilla yhdistettyinä laatikoina ja simuloikaa jokainen osoittimen päivitys paperilla ennen koodaamista. Tämä visuaalinen lähestymistapa estää tahattomat null-osoitinvirheet haastatteluissa.
Muistakaa: Pythonissa curr.next-osoittimen uudelleenmäärittäminen ei vaikuta itse curr-osoittimeen, mutta jos curr.next-viite katoaa ennen sen tallentamista, ette voi enää kulkea listassa eteenpäin.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Demonstrate safe pointer update
def swap_first_two(head):
if not head or not head.next:
return head
first = head
second = head.next
# Save third before losing the reference
third = second.next
# Rewire
second.next = first
first.next = third
return second
from functools import reduce
nodes = [ListNode(i) for i in range(1, 5)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = swap_first_two(nodes[0])
curr = head
while curr:
print(curr.val, end=' ')
curr = curr.next
# 2 1 3 4Yksisuuntaiset ja kaksisuuntaiset linkitetyt listat
Yksisuuntaiseen linkitettyyn listaan tallennetaan vain next-osoitin, joten läpikäynti on yksisuuntaista. Kaksisuuntaiseen linkitettyyn listaan tallennetaan sekä prev- että next-osoitin, mikä mahdollistaa O(1)-aikaisen taaksepäin kulkemisen ja O(1)-aikaisen poistamisen, kun käytössä on suora viittaus solmuun eikä prev-osoitinta tarvitse jäljittää silmukassa.
Pythonin collections.deque on toteutettu kaksisuuntaisena linkitettynä listana, minkä vuoksi se tukee O(1)-aikaisia appendleft- ja popleft-operaatioita. Haastatteluissa toteutatte yksisuuntaisia linkitettyjä listoja; kaksisuuntaiset linkitetyt listat tulevat vastaan LRU-välimuistin suunnittelussa.
class DLNode:
def __init__(self, val=0):
self.val = val
self.prev = None
self.next = None
# Build doubly linked: 1 <-> 2 <-> 3
a, b, c = DLNode(1), DLNode(2), DLNode(3)
a.next = b; b.prev = a
b.next = c; c.prev = b
# Traverse forward
curr = a
while curr:
print(curr.val, end=' <-> ')
curr = curr.next
print('None')
# Traverse backward from c
curr = c
while curr:
print(curr.val, end=' <-> ')
curr = curr.prev
print('None')Pituus, loppupää ja tulostuksen apufunktiot
Kolme apufunktiota, jotka kannattaa pitää valmiina jokaisessa linkitettyjen listojen haastattelussa: length(head) laskee solmut O(n)-ajassa, tail(head) palauttaa viimeisen solmun O(n)-ajassa ja print_list(head) muotoilee listan virheenkorjausta varten. Kun nämä ovat valmiina, voitte keskittyä ydinalgoritmiin sen sijaan, että toteuttaisitte apulogiikan uudelleen.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def length(head):
count = 0
while head:
count += 1
head = head.next
return count
def tail(head):
while head and head.next:
head = head.next
return head
def print_list(head):
parts = []
while head:
parts.append(str(head.val))
head = head.next
print(' -> '.join(parts) + ' -> None')
# Build and test
nodes = [ListNode(i) for i in [10, 20, 30, 40]]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = nodes[0]
print('Length:', length(head))
print('Tail:', tail(head).val)
print_list(head)Kahden osoittimen alustus linkitetyissä listoissa
Kahden osoittimen tekniikka on linkitetyissä listoissa yhtä tärkeä kuin taulukoissa, mutta osoittimet viittaavat indeksien sijaan linkitetyn listan solmuihin. Yleisiä asetelmia ovat hidas ja nopea osoitin (nopea osoitin etenee kaksi kertaa nopeammin) keskipisteiden löytämiseen ja syklien tunnistamiseen sekä edeltäjän ja nykyisen solmun pari poistamista ja kääntämistä varten.
Alustakaa molemmat osoittimet aina selkeästi ja käsitelkää listan päättymisen tarkistus huolellisesti — fast and fast.next estää null-osoitinvirheet, kun fast on lähellä listan loppua.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Find middle node using slow-fast pointers
def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow # for even length, returns second of two middle nodes
nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
print(find_middle(nodes[0]).val) # 3 (middle of 1->2->3->4->5)Dummy head -malli
Dummy head -malli (sentinellisolmu) on yksi hyödyllisimmistä linkitettyjen listojen ongelmien tekniikoista. Kun lisäätte alkuun arvon 0 sisältävän dummy head -solmun, tyhjää listaa tai todellisen alkupään muuttumista ei tarvitse koskaan käsitellä erityistapauksena. Tulos on aina dummy.next. Tätä mallia käytetään järjestettyjen listojen yhdistämisessä, lopusta n:nnen solmun poistamisessa, listan osioinnissa ja monissa muissa tehtävissä.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Remove all nodes with val == target (may include head)
def remove_all(head, target):
dummy = ListNode(0)
dummy.next = head
curr = dummy
while curr.next:
if curr.next.val == target:
curr.next = curr.next.next # skip the node
else:
curr = curr.next
return dummy.next
def to_list(h):
r = []
while h:
r.append(h.val)
h = h.next
return r
nodes = [ListNode(v) for v in [1, 2, 6, 3, 4, 5, 6]]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = remove_all(nodes[0], 6)
print(to_list(head)) # [1, 2, 3, 4, 5]Aika- ja tilavaativuus
Useimmilla linkitetyn listan operaatioilla on seuraavat vaativuudet. Käyttö indeksillä: O(n) — alkupäästä on kuljettava listan läpi. Lisääminen tai poistaminen tunnetusta solmusta: O(1) — osoittimet vain yhdistetään uudelleen. Lisääminen tai poistaminen kohdassa k: O(k) — ensin on kuljettava listan läpi. Haku: O(n) — pahimmillaan koko lista. Tila on O(1) kaikissa in-place-operaatioissa (lukuun ottamatta ylimääräisiä tietorakenteita).
Verratkaa tätä taulukoihin: taulukot tarjoavat O(1)-aikaisen käytön, mutta lisääminen ja poistaminen vievät O(n)-aikaa alkioiden siirtämisen vuoksi. Linkitetyt listat ovat parempia, kun lisääminen ja poistaminen mielivaltaisista kohdista on yleistä.
Haastatteluvinkkejä linkitetyille listoille
Ennen kuin kirjoitatte linkitetyn listan koodia, piirtäkää lista visuaalisesti laatikoina ja nuolina. Käykää reunatapaukset ääneen läpi: tyhjä lista, yksi solmu sekä parillinen ja pariton pituus. Käyttäkää dummy head -solmua rajaehtojen yksinkertaistamiseen. Tarkistakaa heti alussa if not head. Koodauksen jälkeen jäljittäkää ratkaisun toiminta kolmen solmun listalla, jotta löydätte osoitinvirheet ennen haastattelijaa.
Useimmat linkitettyjen listojen virheet johtuvat yhdestä kolmesta syystä: next-osoittimen unohtamisesta ennen sen korvaamista, päättymisehdon off-by-one-virheestä tai alkupään muuttumisen reunatapauksen käsittelemättä jättämisestä — dummy-solmu poistaa näistä kolmannen kokonaan.
Pikatarkistus
Testatkaa tämän oppitunnin Data Structures & Algorithms — Coding Interview Prep -aiheiden ymmärtämistä.
Oppitunnin yhteenveto
Tässä oppitunnissa opitte: linkitetty lista muodostuu Node-olioista, joilla on val- ja next-kentät, dummy head -malli poistaa alkupään muuttumiseen liittyvät reunatapaukset ja hitaan ja nopean osoittimen asetelma muodostaa keskipisteen etsimisen ja syklien tunnistamisen perustan. Seuraavaksi käsittelemme linkitetyn listan kääntämistä — yhtä yleisimmistä osoitinongelmista.
Opi Valmistautuminen ohjelmointihaastatteluihin tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 90
- Oppitunnit
- 360
Usein kysytyt kysymykset
Onko oppitunti ”Node-luokka ja listan rakentaminen” ilmainen?
Kyllä – oppitunnin ”Node-luokka ja listan rakentaminen” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Valmistautuminen ohjelmointihaastatteluihin-kurssin, päivitä CoddyKit PROhon. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Node-luokka ja listan rakentaminen”?
Määritelkää Node-dataclass, rakentakaa listoja yhdistämällä solmuja käsin ja kirjoittakaa insert-, delete- ja print-apufunktiot osoitinmuutosten havainnollistamiseksi. Harjoittelet Valmistautuminen ohjelmointihaastatteluihin-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni Valmistautuminen ohjelmointihaastatteluihin-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin Valmistautuminen ohjelmointihaastatteluihin-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 1/4.
Kuinka kauan ”Node-luokka ja listan rakentaminen”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä Valmistautuminen ohjelmointihaastatteluihin-oppitunnilla?
Kyllä. Jokainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- Node-luokka ja listan rakentaminen
- Linkitetyn listan kääntäminen
- Syklien tunnistaminen Floydin algoritmilla
- Yhdistäminen, jakaminen ja n:nnen alkion etsiminen lopusta