狠狠撸

YZM 2116
Veri Yap?lar?
Yrd. Do?. Dr. Deniz KILIN?
Celal Bayar ?niversitesi
Hasan Ferdi Turgutlu Teknoloji Fakültesi
Yaz?l?m Mühendisli?i

B?L?M - 3
Bu b?lümde,
? Motivasyon: Neden Listeye ?htiya? Var?
? Ba?l? Liste (Linked List)Veri Yap?s?
konusuna de?inilecektir.
Celal Bayar ?niversitesi – YZM 2116 Veri Yap?lar?

3Celal Bayar ?niversitesi – YZM 2116 Veri Yap?lar?
? Dizi, bellek y?neticisi taraf?ndan atanan ve
uzunlu?u ba?tan belli ard???k bir haf?zada
saklan?r.
? int[] A = {6, 5, 4, 2} ?eklinde 4 elemanl?
int türünde bir dizi oldu?unu varsayal?m.
? Haf?zaya s?rayla
o int x = 8; say?s?n? ve
o daha sonra A dizisini
saklad???m?z? dü?ünelim.
Motivasyon: Neden Listeye ?htiya? Var?

int x = 8;
int[] A = {6, 5, 4, 2};
Haf?za
A_1
A_2
x
A_3
A_4
0
1
2
Adres
L0
L0 + c
L0 + 2c
L0 + 3c
L0 + 4c
c byte
Nas?l bir bellek organizasyonu
bekliyoruz?

? Dizi i?in ayr?lan b?lümün sürekli adreslerden
olu?tu?una dikkat edelim.
? Bu diziye yeni bir eleman (?rne?in 3) eklemek
istedi?imizde
o 2’den sonraki alan, yani 217 nolu haf?za dolu
oldu?u i?in haf?zay? geni?letme se?ene?imiz
yoktur.
? ??züm olarak ne yapabiliriz?

? ??züm olarak bir?ok haf?za de?i?imi ve i?lemi
gerektiren a?a??daki ad?mlar uygulan?r:
o Daha büyük bir dizi i?in yer alan? olu?turulur.
o Eski dizideki elemanlar yeni diziye kopyalan?r ve
ta??ma (move) i?lemi ger?ekle?tirilir.
o Eski dizi haf?zadan silinir.
Eski Dizi
Yeni Dizi

? Bu problemi ??zmek i?in ne yapabiliriz?
o Büyük bir haf?za alan?n? dizi i?in ay?rabiliriz.
o Ancak bu durumda da haf?zada saklanan eleman
say?s? azken haf?za bo?a i?gal edilmi? olur.
??Z?M 1: Büyük Haf?za Alan?
o Haf?zay? ihtiya? halinde büyütebilmektir.
o ?nceden alan ay?rmayarak haf?zay? verimli
kullanmak ad?na elemanlar? elemanlar? haf?zaya tek
tek yerle?tirmektir.
??Z?M 2: Ba?l? Liste

? int[] A = {6, 5, 4, 2} dizisini a?a??daki
gibi tutabildi?imizi varsayal?m.
? Elemanlar aras?nda bir ba?lant? sa?lanmas?
zorunludur. Neden?
Ba?l? Liste – ??züm

? Haf?za sürekli olmad??? i?in dizi elemanlar?n?n
birbirleriyle ba?? yoktur. Bu nedenle her bir eleman
sonrakinin adresini g?steren bir referansla
ba?lanmal?d?r.
? Her eleman sonraki eleman?n adresini tutarken son
eleman?n adresi NULL olur.
? Bu ?ekilde elde edilen veri yap?s?, Ba?l? Liste (Linked
List) olarak adland?r?l?r.
Ba?l? Liste – ??züm (devam…)

Haf?za
0
1
2
A_1 Y
A_5 NULL
A_3 Z
A_2 X
A_4 W
Adres
T
W
X
Y
Z
Ba? = T
? Ba?l? listenin haf?za
organizasyonu ve
yerle?imi yandaki
gibi de olabilir.

? Listenin sonuna “3” say?s?n? eklersek,
? Yeni eleman NULL’a i?aret ederken, yani listenin
son eleman? olurken,
? 2 art?k “252” ye (3’ün adresine) i?aret eder.
? A?a??daki ?ekilde dizinin ba?l? liste yap?s?
verilmi?tir.

? Bir ba?l? liste, elemanlar?n?n bir sonraki (Next)
eleman?n haf?zadaki yerine i?aret etti?i zincir
?eklinde bir veri yap?s?d?r.
? 3 tip ba?l? liste bulunmaktad?r.
o Tek y?nlü ba?l? liste
o ?ift y?nlü ba?l? liste
o Dairesel ba?l? liste
Ba?l? Liste – ?zet

? Ba?l? listede her bir
elemana dü?üm (node)
ad? verilir.
? Her dü?üm
o Data: Veri (bir tamsay?,
bir dizi, bir nesne
olabilir)
o Next: Sonraki verinin
adresine i?aret eden bir
referanstan olu?ur.
Ba?l? Liste – ?zet (devam…)
public class Node
{
public int Data;
public Node Next;
}

? ?lk dü?ümün adresini i?eren ve ba?lang?? (Head)
olarak adland?r?lan bir referans de?i?keni bulunur.
o Bir listeyi gezmek i?in bu adrese mutlaka ihtiya?
vard?r.
o Bo? bir listede Head NULL’a i?aret eder.
? Ba?l? listede, son dü?ümde listenin sonuna
i?aret eden ?zel NULL (veya s?f?r) de?eri
bulunur.
Ba?l? Liste – ?zet (devam…)

Ba?l? Liste – ADT
public abstract class LinkedListADT
{
public Node Head;
public int Size = 0;
public abstract void InsertFirst(int value);
public abstract void InsertLast(int value);
public abstract void InsertPos(int position, int value);
public abstract void DeleteFirst();
public abstract void DeleteLast();
public abstract void DeletePos(int position);
public abstract Node GetElement(int position);
public override string DisplayElements()
}
public class Node
{
public int Data;
public Node Next;
}

Ba?l? Liste – ADT (devam…)
? InsertFirst(int value): Listenin ba??na bir node ekler.
? InsertLast(int value): Listenin sonuna bir node ekler.
? InsertPos(int position, int value): Listenin
belirtilen pozisyonuna bir node ekler.
? DeleteFirst(): Listenin ba??ndaki node’u siler.
? DeleteLast(): Listenin sonundaki node’u siler.
? DeletePos(int position): Listenin belirtilen
pozisyondaki node’unu siler.
? GetElement(int position): Listenin belirtilen
pozisyondaki node’unu getirir.
? int Size: Listedeki eleman say?s?n? d?ndürür.
? string DisplayElements(): Listedeki elemanlar?
geriye d?ndürür.
? Node Head: Listenin ilk eleman?n? verir.

Ba?l? Liste – Traverse (Gezinme)
? Head dü?ümünden ba?layarak, sonuncu dü?üme kadar
do?rusal ?ekilde nas?l ilerleriz? Algoritma, mant?k?
Node temp = Head;
while (temp != null)
{
if (temp.Next != null)
temp = temp.Next;
else
break;
}
34 11 122Head
NULL

Ba?l? Liste – InsertFirst
? Listenin ilk eleman? olan Head’i yeni gelen
elemanla yer de?i?tirdi?imiz metottur.
? Traverse i?lemine gerek yoktur.
? A?a??daki listede Head 34’tür.
? Listenin ba??na 45 eleman?n? eklemek istiyoruz.
Yani yeni Head 45 olmal?. Nas?l?
Head 34 11 122Head 45
NULL

Ba?l? Liste – InsertFirst (devam…)
? S?zde kod:
a) Yeni Head dü?üm olu?turulur (tmpHead),
b) Head NULL ise (Liste BO?SA)
o Head ? tmpHead
c) Yeni dü?ümün i?aret?isi Head’a i?aret eder,
o tmpHead.Next ? Head
d) Head yeni dü?üme i?aret eder.
o Head ? tmpHead

Ba?l? Liste – InsertFirst (devam…)
public override void InsertFirst(int value)
{
Node tmpHead = new Node
{
Data = value
};
if (Head == null)
Head = tmpHead;
else
{
//En kritik nokta: tmpHead'in next'i
//eski Head'i g?stermeli
tmpHead.Next = Head;
//Yeni Head art?k tmpHead oldu
Head = tmpHead;
}
//Ba?l? listedeki eleman say?s? bir artt?
Size++;
}

Ba?l? Liste – InsertLast
? Listenin son eleman?n? yeni gelen elemanla yer
de?i?tirdi?imiz metottur.
? Traverse i?lemi gereklidir. Eski sonuncu eleman?n
bulunmas? gerekmektedir.
? A?a??daki listede Son eleman 122’dir.
? Listenin sonuna 35 eleman?n? eklemek istiyoruz.
Nas?l?
34 11 122Head
NULL35 NULL

Ba?l? Liste – InsertLast (devam…)
? S?zde kod:
a) Yeni dü?üm olu?turulur (newLast),
o InsertFirst()
c) “Eski son dü?üm” bulunur (oldLast),
d) Eski son dü?üm, eklenen dü?üme i?aret eder.
o oldLast.Next ? newLast

Ba?l? Liste – InsertPos
? Listenin i. pozisyonundaki eleman?n sonras?na yeni
gelen eleman?, ekleyen metottur.
? Traverse i?lemi gereklidir. i. Pozisyona sahip
eleman?n bulunmas? gerekmektedir.
? A?a??daki listede i=2 i?in 11 eleman? ile 142 eleman?
aras?na 122 eleman?n? ekleyelim. Nas?l?
34 11 142Head NULL122 NULL142

Ba?l? Liste – InsertPos (devam…)
? S?zde kod:
a) Yeni dü?üm olu?turulur (newNode),
o InsertFirst()
c) “i. Pos dü?üm” bulunur (posNode),
d) posNode eleman?n?n Next’i tempNext’e atan?r.
o tempNext ? posNode.Next
e) posNode eleman?n?n Next’ine newNode atan?r.
o posNode.Next ? newNode
f) newNode eleman?n?n Next’ine tempNext atan?r.
o newNode.Next ? tempNext

Ba?l? Liste – DeleteFirst
? Listenin ilk eleman? olan Head’i silen metottur.
? Traverse i?lemine gerek yoktur.
? A?a??daki listede Head 45’dir.
? Listenin ba??ndaki eleman? silmek istiyoruz.
? Yeni Head 34 olmal?. Nas?l?
Head 34 11 122Head 45
NULL

Ba?l? Liste – DeleteFirst (devam…)
? S?zde kod:
a) Head’in sonraki eleman? - Next’i temp bir de?i?kene
atan?r
o tempHeadNext ? Head.Next
b)tempHeadNext NULL ise Head NULL olur,
o Liste bo?al?r
c)tempHeadNext NULL de?ilse Head eleman?
tempHeadNext olur,
o Head ? tempHeadNext

Ba?l? Liste – DeleteLast
? Listenin son eleman?n? silen metottur.
? Traverse i?lemi gereklidir. Sonuncu eleman?n
bulunmas? gerekmektedir.
? A?a??daki listede Son eleman 35’dir.
? Son eleman silindi?inde yeni son eleman 122
olmal?d?r. Nas?l?
34 11 122Head
NULL35 NULL

Ba?l? Liste – DeleteLast (devam…)
? S?zde kod:
a) Son eleman bulunmas? i?in Head’ten itibaren do?rusal
ilerlenir.
b) Son eleman last de?i?kenine atan?r.
c) Son eleman bulundu?unda, sondan bir ?nceki eleman
bulunur ve bir de?i?kene atan?r (lastPrevNode).
d)lastPrevNode eleman?n?n Next’ine NULL atan?r.
e)last de?i?kenine NULL atan?r.

Ba?l? Liste – DeletePos
? Listenin i. pozisyonundaki eleman?n? silen metottur.
? Traverse i?lemi gereklidir. i. Pozisyona sahip
eleman?n bulunmas? gerekmektedir.
? A?a??daki listede i=2 i?in 122 eleman?n? silelim ve 11
eleman? art?k 122’yi de?il, 142’yi i?aret etsin. Nas?l?
34 11 142Head
NULL122 NULL142

Ba?l? Liste – DeletePos (devam…)
? S?zde kod:
a) i. Pozisyondaki eleman?n bulunmas? i?in Head’ten
itibaren do?rusal ilerlenir.
b) i. Pozisyonundaki eleman pos de?i?kenine atan?r.
c) i. Pozisyonundaki eleman bulundu?unda, ondan bir
?nceki eleman?n Next’ine pos’un Next’i atan?r.
d)pos de?i?kenine NULL atan?r.

Ba?l? Liste ve Dizi Kar??la?t?rmas?
? Eri?im Maliyeti
o Dizinin 1. veya en sonuncu eleman?na eri?mek i?in
sadece base adresle ilgili eleman?n s?ras?n?n byte
de?eri (6. s?ra * 4 byte) toplan?r. Bu her eleman i?in
sabit bir zamand?r ve karma??kl??? O(1) olur.
o Ba?l? liste, sürekli bir adreste tutulmad???ndan en
k?tü durumda (worst-case) son eleman?n adresine
eri?mek i?in Head eleman?ndan ba?lanarak s?rayla her
dü?ümden bir sonraki adres elde edilir. Bu nedenle
karma??kl?k eleman say?s? n kadar ya da O(n) olur.

Ba?l? Liste ve Dizi Kar??la?t?rmas? (devam..)
? Eri?im Maliyeti

? Veri Giri? (Insert) Maliyeti
o En Ba?a: Dizide tüm elemanlar bir kayar O(n). Ba?l? listede
sabit bir i?lem O(1).
o En Sona: Dizi bo?sa O(1) de?ilse yeni bir dizi
gerekece?inden en k?tü O(n). Ba?l? listede sonuncu elemana
en k?tü O(n) le ula??l?r ve eklenir.
o i. Pozisyona: Dizide ilgili elemana ula?mak ve duruma g?re
elemanlar? kayd?rmak gerekece?i i?in en k?tü durumda
O(n) zamana ihtiya? vard?r. Ba?l? listede ise kayd?rma
olmad??? halde bir elemana eri?mek i?in head adresinden
istenen adrese kadar gezmek gerekece?inden en k?tü
durumda O(n) olur.

? Veri Giri? (Insert) Maliyeti

? Silme (Delete) Maliyeti
o Insert i?lemleri ile tamamen ayn? senaryolara ve ayn? Big-
O karma??kl?k maliyetlerine sahiptirler.

??lem Dizi Tabanl? Liste Ba?l? Liste
Access, Retrieve
(Eri?im)
O(1) O(n)
InsertFirst O(n) O(1)
InsertLast O(n) O(n)
Sonuncu elemana
pointer varsa = O(1)
InsertPos O(n) O(n)
DeleteFirst O(n) O(1)
DeleteLast O(n) O(n)
Sonuncu elemana
pointer varsa = O(1)
DeletePos O(n) O(n)

?Y? ?ALI?MALAR…

Yararlan?lan Kaynaklar
? Ders Kitab?:
? Data Structures through JAVA, V.V.Muniswamy
? Yard?mc? Okumalar:
? Data Structures and Algorithms in Java, Narashima
Karumanchi
? Data Structures, Algorithms and Applications in Java,
Sartaj Sahni
? Algorithms, Robert Sedgewick

狠狠撸

YZM 2116 - B?lüm 3 - Listeler

More Related Content

YZM 2116 - B?lüm 3 - Listeler

Editor's Notes