The array must move 7,5,2 one position right before storing 8: three moves.
Week 04 · Lecture 4
Arrays, linked lists, stacks and queues
Compare data structures by the operations they support. Draw storage, links, and the order in which items leave.
Read alongside the document
Use the lecture headings below in the English–Turkish notes. Document lecture numbers and course week numbers are different.
- Lecture 4: Elementary Data Structures
Warm-up: functions that fit a description; Two sides of every data structure; Contiguous versus linked; Arrays; Pointers and linked lists; Stacks and queues; The dictionary operations.
Which operation does the problem need to be cheap?
Insert 8 at the front of the packed array [2,5,7]. Then compare a singly linked list with a known head.
For n existing items, this front insertion is Θ(n), assuming enough capacity.
For a linked list, create a node pointing to the old head, then update the head: O(1).
The tradeoff reverses for arbitrary indexed access: array O(1), linked-list traversal O(n).
Change the case. Linked-list insertion is constant time only when the necessary location/link is already known. Finding it may require a full search.
Explain before coding
State the input and required output. Trace a small example. Explain why each step is valid, count the work under a stated model, and test an edge case.
Python support for this week
A Python list behaves like a dynamic array, not a linked list. A stack is last-in first-out; a queue is first-in first-out.
values = [2, 5, 7]
values.insert(0, 8)
print(values) # [8, 2, 5, 7]Run this small demonstration after predicting its result. It illustrates the selected example; its input assumptions are part of the example.
Open the optional Python support library. Programming fluency is not required to complete the paper trace.
Read the related bilingual explanations here
Sections from the supplied lecture notes. Turkish paragraphs appear in red. Use this as a reference after the worked example.
Lecture 4 · Warm-up: functions that fit a description
Hazırlık: bir tanıma uyan fonksiyonlar
Find functions f and g satisfying each condition, or say none exist (recall that little-o, f = o(g), means f grows strictly slower than g):
Her koşulu sağlayan f ve g fonksiyonları bulun veya böyle fonksiyonların bulunmadığını söyleyin (küçük-o gösteriminin, f = o(g), f’nin g’den kesin olarak daha yavaş büyüdüğü anlamına geldiğini hatırlayın):
| Condition | Answer |
| Koşul | Yanıt |
| f = o(g) and f ≠ Θ(g) | f = n, g = n² (strictly slower, so certainly not the same growth) |
| f = o(g) ve f ≠ Θ(g) | f = n, g = n² (kesin olarak daha yavaş; dolayısıyla büyüme hızları kesinlikle aynı değil) |
| f = Θ(g) and f = o(g) | None: “same growth” and “strictly slower” contradict each other |
| f = Θ(g) ve f = o(g) | Yok: “aynı hızda büyüme” ile “kesin olarak daha yavaş büyüme” çelişir. |
| f = Θ(g) and f ≠ O(g) | None: Θ includes O by definition |
| f = Θ(g) ve f ≠ O(g) | Yok: Θ, tanımı gereği O’yu içerir. |
| f = Ω(g) and f ≠ O(g) | f = n², g = n (at least as fast, but not bounded above by g) |
| f = Ω(g) ve f ≠ O(g) | f = n², g = n (en az onun kadar hızlı, ancak g ile üstten sınırlı değil) |
Lecture 4 · Two sides of every data structure
Her veri yapısının iki yönü
Skiena quotes Whitehead: “Mankind’s progress is measured by the number of things we can do without thinking.” Data structures let us do exactly that, because each one has two separable sides:
Skiena, Whitehead’den şu sözü aktarır: “İnsanlığın ilerlemesi, düşünmeden yapabildiğimiz şeylerin sayısıyla ölçülür.” Veri yapıları tam olarak bunu sağlar; çünkü her birinin birbirinden ayrılabilen iki yönü vardır:
The abstract operations it supports, such as Push(x, s) (put item x on top of stack s) and Pop(s) (remove and return the top item). This is the what.
Desteklediği soyut işlemler; örneğin Push(x, s) (x elemanını s yığınının tepesine koy) ve Pop(s) (tepedeki elemanı çıkar ve döndür). Bu, ne yapıldığıdır.
The implementation of those operations. This is the how, and there is usually more than one.
Bu işlemlerin gerçekleştirimi. Bu, nasıl yapıldığıdır ve genellikle birden fazla seçenek vardır.
Because an algorithm only depends on the abstract operations, we can swap implementations to suit the situation without changing the algorithm.
Bir algoritma yalnızca soyut işlemlere bağlı olduğundan, algoritmayı değiştirmeden duruma uygun gerçekleştirimi seçebiliriz.
Lecture 4 · Contiguous versus linked
Bitişik ve bağlı yapılar
Every data structure is one of two kinds:
Her veri yapısı iki türden birine girer:
Contiguous structures live in a single slab of memory: arrays, matrices, heaps (Lecture 7) and hash tables (Lecture 6).
Bitişik yapılar, tek bir bellek bloğunda bulunur: diziler, matrisler, öbekler (Ders 7) ve karma tabloları (Ders 6).
Linked structures are many separate chunks of memory tied together by pointers: linked lists, trees (Lecture 5) and the adjacency lists used for graphs (Lecture 10).
Bağlı yapılar, işaretçilerle birbirine bağlanan çok sayıda ayrı bellek parçasıdır: bağlı listeler, ağaçlar (Ders 5) ve çizgeler için kullanılan komşuluk listeleri (Ders 10).
Lecture 4 · Arrays
Diziler
An array is a row of fixed-size slots, numbered 0, 1, 2, …, so that any slot can be found instantly from its number (its index). Its advantages:
Dizi, 0, 1, 2, … biçiminde numaralandırılmış sabit boyutlu gözlerden oluşan bir sıradır; böylece her göze numarasından (indisinden) anında ulaşılabilir. Avantajları:
Constant-time access by index: the address of slot i is just (start + i × slot size), one multiplication and one addition.
İndisle sabit zamanlı erişim: i gözünün adresi yalnızca (başlangıç + i × göz boyutu) ile bulunur; bir çarpma ve bir toplama.
No wasted space: an array is pure data, with no pointers or bookkeeping.
Boşa harcanan alan yoktur: bir dizi, işaretçiler veya yönetim bilgileri içermeyen saf veridir.
Memory locality: neighbouring items sit next to each other in memory, which the fast cache memory of modern processors rewards.
Bellek yerelliği: komşu elemanlar bellekte yan yana durur; modern işlemcilerin hızlı önbellekleri bu durumdan yararlanır.
The drawback: a plain array has a fixed size chosen when it is created. Guessing too big wastes memory; guessing too small breaks the program.
Dezavantajı: basit bir dizinin, oluşturulurken seçilen sabit bir boyutu vardır. Fazla büyük tahmin etmek belleği boşa harcar; fazla küçük tahmin etmek programı bozar.
Dynamic arrays fix this. Start with an array of size 1. Whenever it fills up, allocate a new array of double the size, copy everything across, and carry on. To hold n items you double only ⌈log₂ n⌉ times.
Dinamik diziler bunu düzeltir. Boyutu 1 olan bir diziyle başlayın. Her dolduğunda iki kat büyüklüğünde yeni bir dizi ayırın, her şeyi oraya kopyalayın ve devam edin. n eleman tutmak için yalnızca ⌈log₂ n⌉ kez iki katına çıkarma gerekir.
Doesn’t all that copying cost a lot? Count it. The last doubling copied n/2 items, the one before that n/4, and so on. Half the items were copied once, a quarter twice, an eighth three times. The total number of moves is
Bütün bu kopyalamalar çok maliyetli değil mi? Sayalım. Son iki katına çıkarma n/2 elemanı, bir önceki n/4 elemanı kopyaladı; böyle devam eder. Elemanların yarısı bir kez, dörtte biri iki kez, sekizde biri üç kez kopyalandı. Toplam taşıma sayısı şöyledir:
So each item moves on average only twice, and managing a dynamic array costs O(n) in total, the same as a plain array. Skiena calls a shrinking geometric series like this “the free lunch of algorithm analysis”: the halving terms add up to a constant multiple of the first one.
Dolayısıyla her eleman ortalama yalnızca iki kez taşınır; dinamik bir diziyi yönetmenin toplam maliyeti, basit bir dizide olduğu gibi O(n)’dir. Skiena, böyle küçülen bir geometrik seriyi “algoritma analizinin bedava öğünü” olarak adlandırır: yarıya inen terimlerin toplamı, ilk terimin sabit bir katıdır.
Sentinels. A sentinel is a dummy item that is never removed, placed at the boundary of a structure. Start a list with a fake item whose key is +∞, and two annoying special cases vanish: the list is never empty, so you never test for that, and no real item is ever the minimum, so insertion sort never has to check whether it has run off the left end. It changes nothing in the Big-O, but it can simplify code.
Gözcüler (sentinels). Gözcü, bir yapının sınırına yerleştirilen ve hiç kaldırılmayan yapay bir elemandır. Bir listeyi anahtarı +∞ olan yapay bir elemanla başlatın; iki can sıkıcı özel durum ortadan kalkar: liste hiçbir zaman boş olmaz, bu yüzden boşluk sınaması yapmazsınız; hiçbir gerçek eleman da minimum olmaz, bu yüzden eklemeli sıralama sol uçtan taşıp taşmadığını denetlemek zorunda kalmaz. Büyük-O açısından hiçbir şeyi değiştirmez, ancak kodu basitleştirebilir.
Lecture 4 · Pointers and linked lists
İşaretçiler ve bağlı listeler
A pointer is the address of a location in memory. Skiena’s analogy: a mobile phone number is a pointer to a person, and it keeps working wherever that person goes. In C, *p means “the thing p points at” and &x means “the address of x”. A special value, NULL, marks a pointer that points at nothing, and is used to mark the end of a structure.
İşaretçi, bellekteki bir konumun adresidir. Skiena’nın benzetmesi: cep telefonu numarası bir kişiye işaret eden işaretçidir; kişi nereye giderse gitsin çalışmayı sürdürür. C dilinde *p, “p’nin işaret ettiği şey”; &x, “x’in adresi” demektir. Özel bir değer olan NULL, hiçbir şeyi işaret etmeyen bir işaretçiyi belirtir ve bir yapının sonunu işaretlemek için kullanılır.
A linked list is a chain of nodes, each holding one data item and a pointer to the next node; the last node’s pointer is NULL:
Bağlı liste, her biri bir veri elemanı ve sonraki düğüme işaretçi tutan düğümler zinciridir; son düğümün işaretçisi NULL’dır:
node:
item (the data)
next (pointer to the following node, or NULL)node:
item (veri)
next (sonraki düğüme işaretçi veya NULL)The three basic operations:
Üç temel işlem:
Search. Start at the head. If this node is NULL, the item is not there. If this node holds the item, done. Otherwise move to next and repeat. This visits nodes one by one, so it costs O(n).
Arama. Baş düğümden başlayın. Bu düğüm NULL ise eleman yoktur. Düğüm aranan elemanı tutuyorsa işlem tamamdır. Aksi hâlde next’e ilerleyin ve tekrarlayın. Düğümler tek tek ziyaret edilir; dolayısıyla maliyet O(n)’dir.
Insert. Since the list is not kept in any order, put the new node at the front: make its next point to the old head, then make the head point to the new node. Two pointer changes: O(1).
Ekleme. Liste herhangi bir sırada tutulmadığından yeni düğümü başa koyun: next işaretçisini eski başa, ardından baş işaretçisini yeni düğüme yönlendirin. İki işaretçi değişikliği: O(1).
Delete. To remove node x you must first find the node before it (its predecessor), because that node’s next pointer has to be redirected to skip x. Finding the predecessor is a search, O(n); the splice itself is O(1). If x is the head there is no predecessor, so the head pointer is moved instead.
Silme. x düğümünü kaldırmak için önce ondan önceki düğümü (öncülünü) bulmalısınız; çünkü bu düğümün next işaretçisi, x’i atlayacak biçimde yeniden yönlendirilmelidir. Öncülü bulmak O(n) maliyetli bir aramadır; bağlantıyı değiştirmek ise O(1)’dir. x baş düğümse öncülü yoktur; bunun yerine baş işaretçisi değiştirilir.
Advantages of linked lists over plain arrays:
Bağlı listelerin basit dizilere göre avantajları:
They can never overflow unless the whole memory is actually full.
Belleğin tamamı gerçekten dolmadığı sürece taşmazlar.
Insertions and deletions are simpler: change a couple of pointers instead of shifting everything along.
Ekleme ve silme daha basittir: her şeyi kaydırmak yerine birkaç işaretçi değiştirilir.
When records are large, moving pointers is cheaper than moving the records themselves.
Kayıtlar büyük olduğunda işaretçileri taşımak, kayıtların kendisini taşımaktan daha ucuzdur.
Singly versus doubly linked. A doubly linked list gives each node a prev pointer as well as next. This doubles the pointer storage but makes predecessor lookups instant, so deletion becomes O(1) when you already hold the node. Since the Big-O cost of maintaining the extra pointer is zero, the course usually assumes lists are doubly linked. (Skiena: a singly linked list is to a doubly linked list as a conga line is to a can-can line.)
Tek bağlı ve çift bağlı listeler. Çift bağlı liste, her düğüme next’in yanı sıra bir prev işaretçisi de verir. Bu, işaretçilerin kapladığı alanı iki katına çıkarır; ancak öncüle erişimi anlık hâle getirir. Böylece düğüm zaten elinizdeyse silme O(1) olur. Ek işaretçiyi sürdürmenin Büyük-O açısından ek maliyeti sıfır olduğundan, derste listelerin genellikle çift bağlı olduğu varsayılır. (Skiena: tek bağlı listenin çift bağlı listeye oranı, conga dansındaki sıranın can-can dansındaki sıraya oranı gibidir.)
Lecture 4 · Stacks and queues
Yığınlar ve kuyruklar
Sometimes we do not care what an item is, only when it arrived. Two containers organise items purely by arrival time:
Bazen bir elemanın ne olduğuyla değil, yalnızca ne zaman geldiğiyle ilgileniriz. İki kapsayıcı yapı, elemanları yalnızca geliş zamanlarına göre düzenler:
A stack is last-in, first-out (LIFO). Push(x, s) puts x on top; Pop(s) removes and returns the top item. Like food in the refrigerator: whatever you put in last is what you take out first.
Yığın (stack), son giren ilk çıkar (LIFO) düzenindedir. Push(x, s), x’i tepeye koyar; Pop(s), tepedeki elemanı çıkarıp döndürür. Buzdolabındaki yiyecekler gibi: en son koyduğunuzu ilk çıkarırsınız.
A queue is first-in, first-out (FIFO). Enqueue(x, q) adds x at the back; Dequeue(q) removes and returns the front item. Like a line at the bank.
Kuyruk (queue), ilk giren ilk çıkar (FIFO) düzenindedir. Enqueue(x, q), x’i arkaya ekler; Dequeue(q), öndeki elemanı çıkarıp döndürür. Bankadaki sıra gibi.
Stacks are easiest as an array with a counter that goes up on push and down on pop. Queues are easiest as a linked list, adding at one end and removing at the other. Either way every operation costs O(1).
Yığınlar en kolay, push sırasında artan ve pop sırasında azalan bir sayaca sahip diziyle gerçekleştirilir. Kuyruklar ise bir uçtan eklenip diğer uçtan çıkarılan bağlı listeyle en kolay gerçekleştirilir. Her iki durumda da her işlem O(1) tutar.
Why this matters: the entire difference between depth-first search and breadth-first search (Lectures 11 and 12) is whether the items waiting to be processed sit in a stack or a queue.
Bunun önemi şudur: derinlik öncelikli arama ile genişlik öncelikli arama (Ders 11 ve 12) arasındaki bütün fark, işlenmeyi bekleyen elemanların bir yığında mı yoksa kuyrukta mı tutulduğudur.
Lecture 4 · The dictionary operations
Sözlük işlemleri
The most important family of data structures maintains a set of items, each identified by a key, and supports these operations:
En önemli veri yapısı ailesi, her biri bir anahtarla tanımlanan elemanlardan oluşan bir kümeyi tutar ve şu işlemleri destekler:
| Operation | Meaning |
| İşlem | Anlamı |
| Search(S, k) | Return the item whose key is k, or nil if none |
| Search(S, k) | Anahtarı k olan elemanı; yoksa nil döndür. |
| Insert(S, x) | Add item x to the set |
| Insert(S, x) | x elemanını kümeye ekle. |
| Delete(S, x) | Remove item x, given a pointer to it (not just its key) |
| Delete(S, x) | Yalnızca anahtarı değil, kendisine bir işaretçi verilen x elemanını kaldır. |
| Min(S), Max(S) | Return the item with the smallest (largest) key |
| Min(S), Max(S) | En küçük (en büyük) anahtarlı elemanı döndür. |
| Predecessor(S, x), Successor(S, x) | Return the item whose key is just below (just above) x’s key |
| Predecessor(S, x), Successor(S, x) | Anahtarı, x’in anahtarından hemen küçük (hemen büyük) olan elemanı döndür. |
There are many ways to implement these, and there is an inherent trade-off: no single implementation is fastest at all seven. The rest of the course is partly a tour of the options. Two array-based ones to start:
Bunları gerçekleştirmenin birçok yolu vardır ve kaçınılmaz bir ödünleşim söz konusudur: hiçbir tek gerçekleştirim yedi işlemin tamamında en hızlı değildir. Dersin geri kalanı, kısmen bu seçenekler arasında bir gezintidir. Başlangıç için dizi tabanlı iki seçenek:
| Operation | Unsorted array | Sorted array |
| İşlem | Sırasız dizi | Sıralı dizi |
| Search | O(n), look at everything | O(log n), binary search |
| Arama | O(n), her şeye bak | O(log n), ikili arama |
| Insert | O(1), drop it in the first free slot | O(n), find the spot then shift items to make room |
| Ekleme | O(1), ilk boş göze koy | O(n), yerini bul; sonra yer açmak için elemanları kaydır |
| Delete | O(1), copy the last item into the hole | O(n), shift items to close the hole |
| Silme | O(1), son elemanı boşluğa kopyala | O(n), boşluğu kapatmak için elemanları kaydır |
| Min / Max | O(n), scan | O(1), first or last slot |
| Minimum / Maksimum | O(n), tara | O(1), ilk veya son göz |
| Predecessor / Successor | O(n), scan | O(1), neighbouring slot |
| Öncül / Ardıl | O(n), tara | O(1), komşu göz |
The sorted array is wonderful for looking things up and terrible for changing anything. The unsorted array is the reverse. Lecture 5 looks for a structure that is good at both.
Sıralı dizi, eleman aramak için harika; bir şeyleri değiştirmek için kötüdür. Sırasız dizi ise tam tersidir. Ders 5’te, her ikisinde de iyi olan bir yapı arayacağız.
Begin with the easy tests and the worked example. Remaining questions provide repeated teaching practice; hard questions are optional depth. Some tests revisit earlier prerequisites. Answers stay visible.
Practice with answers
10 test questions · 10 written questions · 20 total
Each question is followed by its answer and explanation. Hard questions also include a starting hint and smaller reasoning steps.
Test questions
Choose one option. Cost questions state their model and whether the bound is tight, expected or worst-case. Here lg means log₂, and heap positions start at 1.
Question 1 · easy
Which structure guarantees constant-time access by arbitrary numeric index i in the standard fixed-size-word RAM model?
Answer: option B. The address of slot i is start + i × item size.
Question 2 · easy
Push 5, 6, 7 onto a stack, then pop once. You get:
Answer: option C. Last in, first out.
Question 3 · easy
Enqueue 5, 6, 7 into a queue, then dequeue once. You get:
Answer: option A. First in, first out.
Question 4 · easy
Inserting a key into a packed sorted array may require shifting items. What is the tightest listed worst-case upper bound?
Answer: option C. Finding the spot is O(log n), but shifting the later items over is O(n).
Question 5 · easy
A dynamic array starts with capacity 1 and doubles only when full. How many doublings are needed to hold 5,000 items?
Answer: option B. 2¹² = 4,096 is too small and 2¹³ = 8,192 is enough.
Question 6 · easy
In the ordered-dictionary interface used here (search, insert, delete, min, max, predecessor, successor), which operation belongs instead to the stack interface?
Answer: option B. Push belongs to stacks; the dictionary operations are search, insert, delete, min, max, predecessor and successor.
Question 7 · easy · course question
Given the head of a singly linked list, front insertion needs how many existing-node traversals?
Answer: option A. Create a node pointing to the old head and update the head; searching for a different insertion location is a separate cost.
Question 8 · easy · course question
To read array position i in constant time, the model assumes:
Answer: option B. Random-access addressing reaches the location directly. Sorting and uniqueness are unnecessary.
Question 9 · medium
Growing a full dynamic array from capacity 1 to capacity 1,024 by doubling copies exactly how many existing items in total?
Answer: option B. 1 + 2 + 4 + … + 512 = 1,023, less than n.
Question 10 · medium
If the array instead grows by 100 slots each time it fills, inserting n items costs in total:
Answer: option C. About n/100 expansions, each copying up to n items.
Written questions
Read each question together with its explanation, trace or proof. Numbering continues from the test questions.
Question 11 · easy
Which gives O(1) access to the i-th item, an array or a linked list? Which one can grow without a fixed size limit?
Answer & reasoning
An array gives constant-time indexed access in the RAM model. A linked list follows pointers to reach its i-th item, taking linear time in the index. Both linked lists and dynamic arrays can grow subject to memory limits; only a fixed-size array has a predetermined capacity. Python lists are dynamic arrays of references.
Question 12 · easy
Push 1, 2, 3 onto a stack and pop twice: what comes out, in order? Enqueue 1, 2, 3 into a queue and dequeue twice?
Answer & reasoning
stack: 3 then 2 (last in, first out). Queue: 1 then 2 (first in, first out).
Question 13 · easy
Which container for the “to-do list” turns a graph traversal into depth-first search, and which into breadth-first search?
Answer & reasoning
a stack gives DFS, a queue gives BFS.
Question 14 · easy
Starting with a dynamic array of size 1 and doubling whenever it fills, how many doublings are needed before it can hold 1,000 items?
Answer & reasoning
10, since 2¹⁰ = 1,024 ≥ 1,000; in general ⌈lg n⌉.
Question 15 · easy
What is a sentinel, and what does it buy you?
Answer & reasoning
a dummy item placed at a boundary that is never removed, such as a key of +∞ at the start of a list; it removes special-case tests (empty list, running off the end) without changing the Big-O.
Question 16 · medium
A dynamic array holds n = 2ᵏ items after growing from size 1 by doubling. How many item-copies were made in total over all the doublings? Show the total is less than n.
Answer & reasoning
the doublings copied 1, 2, 4, …, 2ᵏ⁻¹ items, totalling 2ᵏ − 1 = n − 1 < n. So the copying costs O(n) in total, or O(1) per item on average (“amortised”).
Question 17 · medium
Suppose the array grows by adding 10 slots each time it fills, instead of doubling. What does inserting n items cost in total?
Answer & reasoning
Θ(n²). About n/10 expansions copy 10, 20, 30, … items, whose sum grows quadratically. A multiplicative factor greater than 1, such as 1.5 or 2, gives linear total copying instead; doubling is convenient but not essential.
Question 18 · medium
You hold a pointer to a node x in a singly linked list, x is not the last node, and you have no pointer to the head. Delete x’s value from the list in O(1).
Answer & reasoning
copy the next node’s item into x, then splice out the next node: x.next = x.next.next. The list now contains the same values minus x’s original one, and no predecessor search was needed.
Question 19 · medium
Build a queue out of two stacks so that every operation is O(1) on average.
Answer & reasoning
enqueue pushes onto stack In. Dequeue pops from stack Out; if Out is empty, first pop everything from In and push it onto Out (which reverses the order). Each item is moved at most twice in its lifetime, so n operations cost O(n) in total.
Question 20 · hard · optional challenge
Design a stack that supports push, pop and get-minimum, all in O(1).
In simpler words: Keep the smallest stack value available without searching.
Starting hint: Remember the minimum after every push.
Answer & reasoning
Step by step
- Push 5,3,7. The main stack is [5,3,7]; the minimum stack is [5,3,3].
- Each minimum entry describes the main-stack prefix ending at the same depth.
- Pop both stacks together. The new minimum is still at the top. On the first push use x itself; handle empty-stack queries explicitly.
keep a second stack of running minima. On push(x), push x onto the main stack and push min(x, current top of the min stack) onto the min stack. On pop, pop both. The top of the min stack is always the minimum of the main stack.