TechCodeview

Sıralamak Ve Bağlantılı liste bellekteki verileri düzenlemenin iki yoludur. arasındaki farkları anlamadan önce Sıralamak ve Bağlantılı liste , ilk önce bakıyoruz bir dizide Ve bağlantılı liste .

linux dizin adını değiştir

Dizi nedir?

Aynı türdeki öğeleri içeren bir veri yapısı. Veri yapısı, verileri düzenlemenin bir yoludur; dizi bir veri yapısıdır çünkü verileri sırayla düzenler. Dizi, belleğin küçük-küçük bloklara bölündüğü ve her bloğun bir miktar değer depolayabildiği büyük bir bellek yığınıdır.

10 değerden oluşan bir dizi oluşturduğumuzu varsayalım, o zaman her blok bir tamsayı tipinin değerini saklayacaktır. Değeri farklı türden bir dizide saklamaya çalışırsak, bu doğru bir dizi değildir ve derleme zamanı hatası verir.

Dizi bildirimi

Bir dizi şu şekilde bildirilebilir:

 data_type name of the array[no of elements] 

Bir diziyi bildirmek için önce dizinin türünü, sonra da dizinin adını belirtmemiz gerekir. Köşeli parantezlerin içinde dizimizin içermesi gereken eleman sayısını belirtmemiz gerekiyor.

Bir örnek üzerinden anlayalım.

 int a[5]; 

Yukarıdaki durumda, ' ile 5 öğeden oluşan bir dizi bildirdik. A 'birinin adı tamsayı veri tipi.

Bağlantılı liste nedir?

Bağlantılı liste, rastgele depolanan düğümlerin koleksiyonudur. Her düğüm iki alandan oluşur; veri Ve bağlantı . Burada veri, söz konusu düğümde depolanan değerdir ve bağlantı, bir sonraki düğümün adresini tutan işaretçidir.

Dizi ve Bağlantılı Liste arasındaki farklar

Hangi veri yapısının daha iyi olduğunu söyleyemeyiz, yani dizi veya bağlantılı liste . Bir veri yapısının bir tür gereksinim için daha iyi olması, diğer veri yapısının ise başka bir gereksinim türü için daha iyi olması ihtimali olabilir. Veri yapısında hangi sıklıkta yapılan işlemler, veri büyüklüğü gibi faktörler olduğu gibi veri yapısının hangi esaslara göre seçildiği gibi çeşitli faktörler de bulunmaktadır. Şimdi dizi ile bağlantılı liste arasında bazı parametrelere bağlı olarak bazı farklılıklar göreceğiz.

1. Bir öğeye erişmenin maliyeti

Dizi durumunda, dizinin boyutundan bağımsız olarak dizinin bir öğeye erişmesi sabit bir zaman alır. Bir dizide öğeler bitişik bir şekilde saklanır, dolayısıyla öğenin temel adresini bilirsek dizideki herhangi bir öğenin adresini kolayca alabiliriz. Bir dizideki herhangi bir elemanın adresini elde etmek için basit bir hesaplama yapmamız gerekir. Yani bir dizideki öğeye erişim Ç(1) Zaman karmaşıklığı açısından.

Bağlantılı listede öğeler bitişik bir şekilde saklanmaz. Birden fazla bloktan oluşur ve her blok bir düğüm olarak temsil edilir. Her düğümün iki alanı vardır, yani biri veri alanı içindir, diğeri ise bir sonraki düğümün adresini saklar. Bağlantılı listede herhangi bir düğümü bulmak için öncelikle baş düğüm olarak bilinen ilk düğümü belirlememiz gerekir. Listedeki ikinci düğümü bulmamız gerekiyorsa, ilk düğümden geçmemiz gerekir ve en kötü durumda, son düğümü bulmak için tüm düğümleri geçeceğiz. Öğeye erişim için ortalama durum O(n)'dir.

Dizideki bir öğeye erişmenin maliyetinin bağlantılı listeden daha az olduğu sonucuna vardık. Bu nedenle, eğer öğelere erişim için herhangi bir gereksinimimiz varsa, o zaman dizi daha iyi bir seçimdir.

2. Bir öğe eklemenin maliyeti

Eklemede üç senaryo olabilir:

işaretleme resmi

Öğeyi başlangıca eklemek:Yeni elemanı en başa eklemek için öncelikle elemanı sağa doğru kaydırarak ilk pozisyonda boşluk yaratmamız gerekiyor. Yani zaman karmaşıklığı listenin boyutuyla orantılı olacaktır. Eğer n dizinin boyutu ise, zaman karmaşıklığı O(n) olacaktır.

Bağlantılı liste durumunda, bağlantılı listenin başına bir öğe eklemek için yeni bir düğüm oluşturacağız ve ilk düğümün adresi yeni düğüme eklenecektir. Bu şekilde yeni düğüm ilk düğüm olur. Dolayısıyla zaman karmaşıklığı listenin boyutuyla orantılı değildir. Zaman karmaşıklığı sabit olacaktır, yani O(1).

Sona bir öğe ekleme

Dizi dolu değilse, yeni öğeyi doğrudan dizin aracılığıyla ekleyebiliriz. Bu durumda zaman karmaşıklığı sabit olacaktır, yani O(1). Dizi doluysa öncelikle diziyi başka bir diziye kopyalayıp yeni bir eleman eklememiz gerekir. Bu durumda zaman karmaşıklığı O(n) olacaktır.

Bağlantılı listenin sonuna bir öğe eklemek için tüm listeyi geçmemiz gerekir. Eğer bağlantılı liste n elemandan oluşuyorsa zaman karmaşıklığı O(n) olacaktır.

Ortaya bir öğe ekleme

Öğeyi i'ye eklemek istediğimizi varsayalım.^budizinin konumu; n/2 elemanını sağa kaydırmamız gerekiyor. Bu nedenle zaman karmaşıklığı elementlerin sayısıyla orantılıdır. Ortalama durum için zaman karmaşıklığı O(n) olacaktır.

img css hizalama

Bağlantılı liste durumunda, yeni elemanı eklememiz gereken konuma geçmemiz gerekir. Gerçi herhangi bir kaydırma yapmamıza gerek yok ama n/2 konumuna geçmemiz gerekiyor. Harcanan zaman n eleman sayısıyla orantılıdır ve ortalama durum için zaman karmaşıklığı O(n) olacaktır.

Sonuçta ortaya çıkan bağlantılı liste şöyledir:

Kullanım kolaylığı

Bir dizinin uygulanması bağlantılı listeye kıyasla kolaydır. Bağlantılı liste kullanarak program oluştururken program, segmentasyon hatası veya bellek sızıntısı gibi hatalara daha yatkındır. Bu nedenle bağlantılı listede bir program oluştururken çok dikkatli olunması gerekir.

Boyut olarak dinamik

Bağlantılı listenin boyutu dinamik, dizi ise statiktir. Burada statik, boyuta çalışma zamanında karar veremeyeceğimiz anlamına gelmez, ancak boyuta karar verdikten sonra onu değiştiremeyiz.

3. Bellek gereksinimleri

Bir dizideki öğeler bitişik bir bellek bloğunda depolandığından, dizi sabit boyuttadır. Diyelim ki 7 boyutunda bir dizimiz var ve dizi 4 öğeden oluşuyor, o zaman alanın geri kalanı kullanılmaz. 7 elementin kapladığı hafıza:

Bellek alanı = 7*4 = 28 bayt

7, bir dizideki öğelerin sayısı ve 4, bir tamsayı türünün bayt sayısıdır.

Bağlantılı liste durumunda kullanılmayan bellek yoktur ancak fazladan bellek işaretçi değişkenleri tarafından kullanılır. Veriler tamsayı tipindeyse, bir düğümün kapladığı toplam bellek 8 bayttır; yani veriler için 4 bayt ve işaretçi değişkeni için 4 bayt. Bağlantılı liste 4 öğeden oluşuyorsa bağlantılı listenin kapladığı bellek alanı şu şekilde olacaktır:

web sürücüsü

Bellek alanı = 8*4 = 32 bayt

Veri bölümünün boyutu daha büyükse bağlantılı liste daha iyi bir seçim olacaktır. Verinin 16 bayt olduğunu varsayalım. Dizinin kapladığı bellek alanı 16*7=112 bayt, bağlantılı liste ise 20*4=80 olacaktır, burada 20 baytı veri boyutu için 16 bayt artı işaretçi değişkeni için 4 bayt olarak belirledik. Daha büyük veri boyutunu seçiyorsak bağlantılı liste daha az bellek tüketir; aksi takdirde boyutu belirlemek için benimsediğimiz faktörlere bağlıdır.

Dizi ile bağlantılı liste arasındaki farklara tablo halinde bakalım.