[Ag seinm ceoil] DOUG LLOYD: Ceart go. Mar sin, má chríochnaigh tú díreach go físeán ar liostaí ina n-aonar-nasctha leithscéal D'fhág mé tú amach ar beagán de cliffhanger. Ach tá mé sásta go bhfuil tú anseo a chríochnú an scéal liostaí doubly-nasctha. Mar sin, má tá tú chun cuimhne ó go físeán, labhair muid faoi ​​conas ina n-aonar-nasctha liostaí a dhéanamh freastal ar ár gcumas chun déileáil le faisnéis i gcás líon na n-eilimintí nó líon na míreanna i Is féidir liosta ag fás nó Laghdaigh. Is féidir linn déileáil anois le rud éigin mar sin, i gcás ina ní raibh muid ábalta déileáil leis le arrays. Ach an bhfuil siad ag fulaingt ó cheann teorannú chriticiúil a Tá go bhfuil ina n-aonar-nasctha liosta, is féidir linn bogadh ach riamh i dtreo amháin tríd an liosta. Agus an scéal ach fíor nuair is féidir a bheith ina fhadhb Bhí nuair a bhí muid ag iarraidh a eilimint amháin a scriosadh. Agus ní raibh muid ag plé a fiú conas é a dhéanamh i liosta ina n-aonar-nasctha i pseudocode. Tá sé cinnte doable, ach Is féidir é a bheith ina beagán de hassle. Mar sin, má fhaigheann tú féin i gcás ina bhfuil tú ag iarraidh a scriosadh eilimintí aonair ón liosta nó tá sé ag dul a bheith ag teastáil go mbainfidh tú a bheith ag scriosadh eilimintí aonair ó an liosta, b'fhéidir gur mhaith leat a mheas ag baint úsáide as doubly-nasctha liosta in ionad liosta ina n-aonar-nasctha. Mar gheall ar chumas liostaí doubly-nasctha agat chun bogadh idir aghaidh agus ar gcúl tríd an liosta in áit ach ar aghaidh tríd an list-- ach trí ghné amháin breise chun ár sainmhíniú ar struchtúr le haghaidh an liosta nód doubly-nasctha. Arís, más rud é nach bhfuil tú ag dul go dtí bheith scriosadh eilimintí aonair as an list-- toisc go bhfuil muid a chur leis réimse breise a ár struchtúr sainmhíniú, na nóid iad féin do liostaí doubly-nasctha ag dul a bheith níos mó. Tá siad ag dul a ghlacadh suas bytes níos mó de chuimhne. Agus mar sin más rud é nach bhfuil an rud tú ag dul go mór a dhéanamh, go dtiocfadh leat cinneadh a dhéanamh tá sé Ní fiú an trádáil as a bheith acu a chaitheamh ar an breise bytes de chuimhne ag teastáil le haghaidh liosta doubly-nasctha mura bhfuil tú ag dul a bheith scriosadh eilimintí aonair. Ach tá siad fionnuar freisin le haghaidh rudaí eile freisin. Mar sin, mar a dúirt mé, ní mór dúinn ach a chur leis aon réimse amháin chun ár struchtúr definition-- an gcoincheap sin de pointeoir Roimhe. Mar sin, le liosta ina n-aonar-nasctha, táimid ag tá an luach agus an pointeoir Next, mar sin tá an liosta doubly-nasctha ach ar bhealach chun dul siar chomh maith. Anois sa ina n-aonar-nasctha liosta físeán, labhair muid faoi ​​na cúig de na rudaí is mó gá duit a bheith in ann a dhéanamh a bheith ag obair le liostaí nasctha. Agus don chuid is mó de na, ar an bhfíric go bhfuil sé liosta doubly-nasctha nach bhfuil i ndáiríre léim mór. Is féidir linn a chuardach go fóill trí ag díreach ag bogadh ar aghaidh ó thús go deireadh. Is féidir linn a chruthú fós nód as aer tanaí, go leor i bhfad ar an mbealach céanna. Is féidir linn a liostaí a scriosadh go leor i bhfad ar an mbealach céanna freisin. Na rudaí ach go Tá subtly difriúil, i ndáiríre, tá a chur isteach nóid nua isteach ar an liosta, agus beidh muid ag labhairt ar deireadh faoi scriosadh eilimint amháin ón liosta chomh maith. Arís, go leor i bhfad na trí cinn eile, tá muid nach bhfuil ag dul chun labhairt mar gheall orthu ceart anois toisc go bhfuil siad díreach tweaks an-bheag ar na smaointe a pléadh san fhíseán liosta ina n-aonar-nasctha. Mar sin, a ligean ar chur isteach nód nua i liosta doubly-nasctha. Labhair linn faoi déanamh seo ar feadh liostaí ina n-aonar-nasctha chomh maith, ach níl cúpla breise gabhálacha le liostaí doubly-nasctha. Tá muid [? rith?] i ceann an liosta anseo agus roinnt luach treallach, agus ba mhaith linn a fháil ar an ceann nua an liosta amach na feidhme seo. Sin an fáth a tuairisceáin sé ina réalta dllnode. Mar sin, cad iad na céimeanna? Tá siad, arís, an-chosúil chun liostaí ina n-aonar-nasctha le bhreis amháin breise. Ba mhaith linn spás a leithdháileann haghaidh nua nód agus seiceáil a dhéanamh cinnte go bhfuil sé bailí. Is mian linn a líonadh go nód suas le cibé faisnéis a chuirimid ag iarraidh a chur ann. An rud deireanach is gá dúinn a do-- an Rud breise is gá dúinn a dhéanamh, rather-- is é a shocrú ar an pointeoir Roimhe an ceann d'aois ar an liosta. Cuimhnigh gur mar gheall liostaí de doubly-nasctha, is féidir linn a dul ar aghaidh agus backwards-- a Ciallaíonn sé sin go pointí gach nód iarbhír le dhá nóid eile seachas díreach ceann amháin. Agus mar sin ní mór dúinn a shocrú an ceann d'aois ar an liosta a chur in iúl ar gcúl go dtí an ceann nua de an liosta nasctha, a raibh rud éigin nach raibh againn a dhéanamh os comhair. Agus mar a rinneadh cheana, muid ar ais ach pointeoir leis an ceann nua ar an liosta. Mar sin, tá anseo liosta. Is mian linn a chur isteach 12 isteach sa liosta seo. Fógra go bhfuil an léaráid Is beagán difriúil. Tá gach nód trí fields-- sonraí, agus a pointeoir Next i dearg, agus pointeoir roimhe seo i gorm. Ní dhéanfaidh aon ní a thagann roimh an 15 nód, mar sin is é a pointeoir Roimhe null. Tá sé an tús an liosta. Níl rud ar bith os a chomhair. Agus a thagann aon rud tar éis an 10 nód, agus mar sin tá sé go bhfuil pointeoir Next null chomh maith. Mar sin, a ligean ar chur 12 leis an liosta. Ní mór dúinn [inaudible] spás le haghaidh an nód. Chuir muid 12 taobh istigh de sé. Agus ansin arís, ní mór dúinn a bheith i ndáiríre cúramach gan bhriseadh an slabhra. Ba mhaith linn a athshocrú an leideanna san ord ceart. Agus uaireanta a d'fhéadfadh a mean-- mar beidh orainn a fheiceáil go háirithe leis an delete-- a dhéanaimid bhfuil roinnt leideanna iomarcach, ach sin ceart go leor. Mar sin, cad ba mhaith linn a dhéanamh ar dtús? Ba mhaith liom a mholadh an rudaí a ba chóir duit is dócha dhéanamh iad a líonadh isteach ar an leideanna an 12 nód sula tú teagmháil duine ar bith eile. Mar sin, cad é 12 ag dul a chur in iúl chun seo chugainn? 15. Cad a thagann roimh 12? Ní dhéanfaidh aon ní. Anois tá muid líonadh an eolas breise i 12 mar sin tá sé Roimhe, Aghaidh, agus luach. Anois is féidir linn a bheith 15-- seo sa bhreis céim bhí muid ag caint about-- muid a Is féidir go mbeadh 15 pointe ar ais go dtí 12. Agus anois is féidir linn bogadh an ceann an liosta a bhaineann le bheith chomh maith 12. Mar sin, tá sé deas cosúil leis an méid linn a a bhí á dhéanamh le liostaí ina n-aonar-nasctha, ach amháin i gcás an chéad chéim breise de nascadh an ceann d'aois ar an liosta ar ais go dtí an ceann nua ar an liosta. Anois, a ligean ar a scriosadh ar deireadh nód ó liosta nasctha. Mar sin, a ligean ar rá ní mór dúinn fheidhm éigin eile a Tá aimsiú nód ba mhaith linn a scriosadh agus tá a thabhairt dúinn pointeoir go díreach an nód a ba mhaith linn a scriosadh. Ní chuirimid need-- rá, fiú an Tá ceann fós dhearbhú ar fud an domhain. Ní gá dúinn ceann anseo. Is léir go bhfuil an fheidhm seo á dhéanamh tá muid aimsigh pointeoir a díreach mar an linn a nód ag iarraidh a fháil haitheantas coibhneasta de. A ligean ar a fháil haitheantas coibhneasta de. Tá sé i bhfad níos éasca le liostaí doubly-nasctha. First-- tá sé i ndáiríre ach rudaí lánúin. Ní mór dúinn ach a shocrú ar an máguaird leideanna nóid 'ionas go mbeidh siad skip thar an nód ba mhaith linn a scriosadh. Agus ansin is féidir linn a scriosadh go nód. Mar sin arís, táimid ag dul díreach trí anseo. Táimid tar éis a chinneadh go cosúil ba mhaith linn a scriosadh an nód X. Agus arís, cad tá mé ag déanamh here-- ag an way-- Is cás ginearálta le haghaidh nód atá i lár. Tá cúpla caveats breise go bhfuil tú Ní mór a mheas nuair a bhíonn tú ag scriosadh an tús an-an liosta nó an deireadh an-an liosta. Níl cúpla speisialta cásanna cúinne chun déileáil leis ann. Mar sin, oibríonn sé seo chun scriosadh aon nód i lár an ceann list-- go Tá pointeoir dlisteanach ar aghaidh agus pointeoir dlisteanach ar gcúl, pointeoir roimhe sin agus seo chugainn dlisteanach. Arís, má tá tú ag obair leis na foircinn, tú Ní mór a láimhseáil sin beagán éagsúil, agus ní táimid ag dul chun labhairt faoi sin anois. Ach is féidir leat is dócha figiúr amach cad is gá le déanamh ach ag breathnú ar an físeán seo. Mar sin, tá muid scoite amach X. X an nód ba mhaith linn a scriosadh ón liosta. Cad a dhéanaimid? Gcéad dul síos, ní mór dúinn a athshocrú na leideanna taobh amuigh. Ní mór dúinn a athshocrú 9 s in aice le scipeáil thar 13 agus pointe a 10-- a Is méid atá déanta againn ach. Agus ní mór dúinn freisin chun athshocrú 10 s Roimhe a chur in iúl go 9 in ionad dírithe ar 13. Mar sin arís, ba é seo an léaráid chun tús a chur leis. Ba é seo ár slabhra. Ní mór dúinn a scipeáil níos mó ná 13, ach is gá dúinn a chaomhnú freisin sláine an liosta. Ní chuirimid ag iarraidh a chailleadh ar aon faisnéis i gceachtar treo. Mar sin, ní mór dúinn a athshocrú na leideanna go cúramach mar sin ní féidir linn a bhriseadh an slabhra ar chor ar bith. Mar sin, is féidir linn a rá 9 s pointeoir Next pointí go dtí an áit chéanna go déag s Next pointeoir pointí ceart anois. Mar táimid ar deireadh thiar dul go dtí gur mian a scipeáil níos mó ná 13. Mar sin, cibé áit 13 pointí seo chugainn, tú Ba mhaith naoi a chur in iúl ann ina ionad. Mar sin, tá go bhfuil. Agus ansin cibé áit 13 pointí ar ais go, is cuma cad a thagann roimh 13, ba mhaith linn a chur in iúl 10 le gur in ionad 13. Anois faoi deara, má leanann tú na saigheada, is féidir linn a titim 13 gan iarbhír a chailliúint aon fhaisnéis. Táimid tar éis choinnigh an sláine an liosta, ag bogadh dá ar aghaidh agus ar gcúl. Agus ansin is féidir linn ach a shórtáil de ghlanadh suas le beagán ag tarraingt ar an liosta le chéile. Mar sin, chuirtear ord nua againn ar an leideanna ar an dá thaobh. Agus ansin freed linn a X an nód go raibh 13, agus ní raibh muid bhriseadh an slabhra. Mar sin, rinne muid go maith. Nóta deiridh anseo ar liostaí nasctha. Mar sin, singly- agus doubly-nasctha araon liostaí, mar atá feicthe againn, tacaíocht a chur isteach i ndáiríre éifeachtach agus scriosadh na n-eilimintí. Is féidir leat a dhéanamh go leor i bhfad sé in am i gcónaí. Cad a rinne mór dúinn a dhéanamh a scriosadh gné ach an dara ó shin? Bhog muid pointeoir amháin. Bhog muid pointeoir eile. Freed táimid ag X-- ghlac trí oibríochtaí. Bíonn sé i gcónaí trí oibríochtaí chun scrios go node-- go saor in aisce nód. Conas is féidir linn a chur isteach? Bhuel, tá muid díreach i gcónaí tacking ar an tús má táimid ag a chur isteach go héifeachtach. Mar sin, ní mór dúinn a rearrange-- ag brath ar má tá sé a singly- nó doubly-nasctha liosta, d'fhéadfadh gá dúinn a dhéanamh trí nó ceithre oibríochtaí max. Ach arís, tá sé i gcónaí trí nó ceithre. Ní chuireann sé cuma cé mhéad Is iad na gnéithe inár liosta, tá sé i gcónaí trí nó ceithre operations-- díreach cosúil go bhfuil a scriosadh i gcónaí trí nó ceithre oibríochtaí. Tá sé am tairiseach. Mar sin, go bhfuil i ndáiríre go hiontach. Le arrays, bhí á dhéanamh againn rud éigin cosúil le leanas a chur isteach saghas. Tú chun cuimhne is dócha go a chur isteach Níl an saghas algartam am tairiseach. Tá sé i ndáiríre go leor daor. Mar sin, tá sé seo ar a lán níos fearr do chur isteach. Ach mar a luaigh mé sa ina n-aonar-nasctha liosta físeán, tá muid fuair downside anseo freisin, ceart? Táimid tar éis chaill an cumas chun randamach rochtain eilimintí. Ní féidir linn a rá, ba mhaith liom eilimint uimhir ceithre nó líon eilimint 10 de liosta nasctha ar an mbealach céanna gur féidir linn é sin a dhéanamh le sraith nó is féidir linn ach go díreach innéacs i eilimint ár sraith ar. Agus ag iarraidh mar sin chun teacht ar an eilimint i list-- nasctha má tá cuardach important-- D'fhéadfadh a ghlacadh anois am líneach. Mar a fhaigheann an liosta níos faide, sé D'fhéadfadh a ghlacadh céim amháin breise le haghaidh gach gné amháin ar an liosta i d'fhonn a fháil ar cad tá muid ag lorg. Mar sin, níl dícheangail trádála. Níl le beagán de pro eilimint agus con anseo. Agus nach bhfuil an bhfuil liostaí doubly-nasctha chineál deireanach de struchtúr sonraí meascán go beidh muid ag labhairt faoi, ag cur an foirgneamh bunúsach bloic C ar a chur le chéile. Mar gheall ar go deimhin, is féidir linn fiú a dhéanamh níos fearr ná sin a chruthú struchtúr sonraí a d'fhéadfá a bheith in ann a chuardach trí in am tairiseach freisin. Ach níos mó ar sin i físeán eile. Tá mé Doug Lloyd. Is é seo an CS50.