Liste veri yapisi nedir?

Question

Ingilizcede linked list olarak gecen veri yapisi nedir ?

Answer 1

Liste veri yapisi degerlerin hafizada daginik bir bicimde saklanmasini saglayan bi yapidir.

Bu yapida bir deger ve ondan sonraki degerin hafizasi bulunur. Sematik olarak gostermek gerekirse

 _________           __________              
| d1 | a1-|-------->|  d0 | a0-|-------->NULL
 _________           __________ 

Burada d0 listeye ilk eklenmis deger ve adresi a0, NULL u gosteriyor (yani listenin sonu). d1 ise listeye ikinci eklenmis deger ve adresi a1 listenin ilk elemanini gosteriyor.

 

• Listede $n$ eleman saklamak $O(2n)$ hafiza tutar (burada $O$ notasyonunu biraz yanlis kullandim $O(2n) = O(n)$ sadece adresi de saklamamiz gerektigine dikkat cekmek icin yaptim bunu).
• Listede $n$ inci elemana bakmak $O(n)$ islem tutar.
• Listenin basina eleman eklemek/cikarmak $O(1)$ islem tutar.
• Listenin sonuna eleman eklemek/cikarmak $O(n)$ islem tutar. Eger listenin son elemani biliniyorsa (cifte bagli liste [doubly linked list] veya liste yapisini kapsayan bir yapi yaratip listenin son elemaninin adresini de saklayabilirsiniz ) $O(1)$ islem tutar.
• Listede rastgele bir yere eleman eklemek cikarmak elemani bulma zamani kadar tutar.

 

Listeler bir cok fonksiyonel programlama dilinin temelinde yatar. Bunun sebebini kalici (persistent) bir veri yapisi olmasina baglayabiliriz. Dogru implementasyon ile her operasyondan sonra listenin onceki durumunu verimli bir bicimde koruyabiliriz. Bu LISP ve Haskell gibi degismezlige (immutability) ye dayanan diller icin onemli bir ozellik.

 

C programla dilinde ornek

#include <stdlib.h>
#include <stdio.h>

typedef struct Eleman_T
{
  int veri;
  struct Eleman_T *adres;
} Eleman;

typedef struct Liste_T
{
  Eleman *ilk_eleman;
  Eleman *son_eleman;
  int eleman_sayisi;
} Liste;


Eleman *
eleman_yarat (int n)
{
  Eleman *sonuc = calloc (1, sizeof (Eleman));
  if (sonuc)
    {
      sonuc->veri = n;
      return sonuc;
    }
  else
    {
      printf ("Hafiza rezerve edemedim !\n");
      exit (0);
    }
}


void
basa_eleman_ekle (Liste * L, int n)
{
  Eleman *e = eleman_yarat (n);
  e->adres = L->ilk_eleman;
  L->ilk_eleman = e;
  if (L->eleman_sayisi == 0)
    {
      L->son_eleman = e;
    }
  L->eleman_sayisi += 1;
}

void
sona_eleman_ekle (Liste * L, int n)
{
  Eleman *e = eleman_yarat (n);
  L->son_eleman->adres = e;
  L->son_eleman = e;
  L->eleman_sayisi += 1;
}

void
listeyi_goster (Liste * L)
{
  for (Eleman * e = L->ilk_eleman; e != NULL; e = e->adres)
    {
      printf ("%d \n", e->veri);
    }
}

void
listeyi_sil (Liste * L)
{

  Eleman *e = L->ilk_eleman;
  if (e == NULL)
    {
      return;
    }
  L->ilk_eleman = L->ilk_eleman->adres;
  free (e);
  L->eleman_sayisi -= 1;
  listeyi_sil (L);
}

int
listeye_bak (Liste * L, int n)
{
  if (n < 0)
    {
      printf ("Listenin boyu %d \n lutfen uygun bir indeks girin\n",
	      L->eleman_sayisi);
      return 0;
    }
  if (n > L->eleman_sayisi)
    {
      printf ("Listenin boyu %d \n lutfen uygun bir indeks girin\n",
	      L->eleman_sayisi);
      return 0;
    }

  int i = 0;
  for (Eleman * e = L->ilk_eleman; e != NULL; e = e->adres)
    {
      if (n == i)
	{
	  return e->veri;
	}
      i += 1;
    }
  return 0;

}

int
main ()
{
  Liste l;
  l.ilk_eleman = NULL;
  l.son_eleman = NULL;
  l.eleman_sayisi = 0;
  basa_eleman_ekle (&l, 10);
  basa_eleman_ekle (&l, 5);
  basa_eleman_ekle (&l, 7);
  sona_eleman_ekle (&l, 7);

  listeyi_goster (&l);
  int n = listeye_bak (&l, 0);
  printf ("listenin 0. elemani %d\n", n);
  n = listeye_bak (&l, 1);
  printf ("listenin 1. elemani %d\n", n);
  n = listeye_bak (&l, 2);
  printf ("listenin 2. elemani %d\n", n);

  listeyi_sil (&l);

}