Linkitetty lista on lineaarinen tietorakenne, jossa elementtejä ei tallenneta vierekkäiseen paikkaan, vaan ne linkitetään osoittimien avulla. Linked List muodostaa sarjan yhdistettyjä solmuja, joihin kukin solmu tallentaa tiedot ja seuraavan solmun osoitteen.

Solmurakenne: Linkitetyn luettelon solmu koostuu tyypillisesti kahdesta osasta:
Tiedot: Se sisältää todellisen arvon tai solmuun liittyvät tiedot.
Seuraava osoitin: Se tallentaa sekvenssin seuraavan solmun muistiosoitteen (viitteen).
Pää ja häntä: Linkitettyyn luetteloon päästään pääsolmun kautta, joka osoittaa luettelon ensimmäiseen solmuun. Listan viimeinen solmu osoittaa NULL tai nullptr, mikä osoittaa luettelon lopun. Tämä solmu tunnetaan häntäsolmuna.

Miksi linkitetty listatietorakenne tarvitaan?

Tässä on muutamia alla olevan linkitetyn luettelon etuja. Se auttaa sinua ymmärtämään, miksi se on tarpeen tietää.

• Dynaaminen tietorakenne: Muistin koko voidaan varata tai purkaa ajon aikana toiminnon lisäämisen tai poistamisen perusteella.
• Lisäämisen/poistamisen helppous: Elementtien lisääminen ja poistaminen on yksinkertaisempaa kuin taulukot, koska mitään elementtejä ei tarvitse siirtää lisäämisen ja poistamisen jälkeen, vain osoite on päivitettävä.
• Tehokas muistin käyttö: Kuten tiedämme, linkitetty luettelo on dynaaminen tietorakenne, jonka koko kasvaa tai pienenee tarpeen mukaan, joten tämä välttää muistin tuhlauksen.
• Toteutus: Erilaisia ​​edistyneitä tietorakenteita voidaan toteuttaa käyttämällä linkitettyä luetteloa, kuten pino, jono, kaavio, hash-kartat jne.

Esimerkki:

Jos järjestelmässä ylläpidetään lajiteltua ID-luetteloa taulukossa id[] = [1000, 1010, 1050, 2000, 2040].

Jos haluamme lisätä uuden tunnuksen 1005, niin järjestyksen säilyttämiseksi meidän on siirrettävä kaikki elementit 1000:n jälkeen (lukuun ottamatta 1000).

Poistaminen on myös kallista taulukoiden kanssa, kunnes ei käytetä erityisiä tekniikoita. Esimerkiksi 1010:n poistamiseksi id[]:stä kaikki 1010:n jälkeinen on siirrettävä tämän vuoksi niin paljon työtä tehdään, mikä vaikuttaa koodin tehokkuuteen.

Linkitettyjen luetteloiden tyypit :

Linkitettyjä luetteloita on pääasiassa kolmenlaisia:

1. Yksi linkitetty luettelo
2. Kaksoislinkitetty lista
3. Pyöreä linkitetty luettelo

1. Yksi linkitetty luettelo :

Yksittäin linkitetyssä luettelossa jokainen solmu sisältää viittauksen sekvenssin seuraavaan solmuun. Yksittäin linkitetyn luettelon läpikulku tapahtuu eteenpäin.

Yksi linkitetty luettelo

2. Kaksoislinkitetty luettelo :

Kaksoislinkitetyssä luettelossa jokainen solmu sisältää viittaukset sekä seuraavaan että edelliseen solmuun. Tämä mahdollistaa liikkumisen sekä eteen- että taaksepäin, mutta vaatii lisämuistia taaksepäin suuntautuvaa referenssiä varten.

Kaksoislinkitetty luettelo

3. Pyöreä linkitetty luettelo :

Ympyränmuotoisessa linkitetyssä luettelossa viimeinen solmu osoittaa takaisin pääsolmuun luoden pyöreän rakenteen. Se voi olla joko yksittäin tai kaksinkertaisesti linkitetty.

javascript trim alimerkkijono

Pyöreä linkitetty luettelo

Toiminnot linkitetyillä listoilla

1. Lisäys : Uuden solmun lisääminen linkitettyyn luetteloon edellyttää olemassa olevien solmujen osoittimien säätämistä oikean järjestyksen ylläpitämiseksi. Lisäys voidaan suorittaa luettelon alkuun, loppuun tai mihin tahansa kohtaan
2. Poistaminen : Solmun poistaminen linkitetystä luettelosta edellyttää naapurisolmujen osoittimien säätämistä poistetun solmun jättämän aukon kattamiseksi. Poistaminen voidaan suorittaa luettelon alussa, lopussa tai missä tahansa kohdassa.
3. Etsitään : Tietyn arvon etsiminen linkitetystä luettelosta edellyttää luettelon läpikulkua pääsolmusta, kunnes arvo löytyy tai luettelon loppu on saavutettu.

Linkitettyjen luettelon monimutkaisuusanalyysi :

• Aika monimutkaisuus: O(n)
• Aputila: O(n)

Linkitettyjen luetteloiden edut

• Dynaaminen koko: Linkitetyt luettelot voivat kasvaa tai pienentyä dynaamisesti, koska muistin varaus tehdään suorituksen aikana.
• Lisääminen ja poistaminen: Elementtien lisääminen tai poistaminen linkitetystä luettelosta on tehokasta, etenkin suurille luetteloille.
• Joustavuus: Linkitetyt luettelot voidaan helposti järjestää uudelleen ja muokata ilman jatkuvaa muistilohkoa.

Linkitettyjen listojen haitat

• Random Access: Toisin kuin taulukot, linkitetyt luettelot eivät salli suoraa pääsyä elementteihin indeksin mukaan. Tietyn solmun saavuttaminen edellyttää läpikulkua.
• Ylimääräinen muisti: Linkitetyt luettelot vaativat lisämuistia osoittimien tallentamiseen verrattuna taulukoihin.

Johtopäätös:

Linkitetyt listat ovat monipuolisia tietorakenteita, jotka mahdollistavat dynaamisen muistin varauksen ja tehokkaat lisäys- ja poistotoiminnot. Linkitettyjen luetteloiden perusteiden ymmärtäminen on välttämätöntä jokaiselle ohjelmoijalle tai tietojenkäsittelytieteen harrastajalle. Tämän tiedon avulla voit toteuttaa linkitettyjä listoja ratkaistaksesi erilaisia ​​​​ongelmia ja laajentaa ymmärrystäsi tietorakenteista ja algoritmeista.