Theory
Request number 101
BookBridge issue requests ને array માં queue કરે છે:
String[] queue = new String[100];
Exam week આવે છે. Request 101 show up થાય છે, અને array full છે: Java માં, array નું size birth પર fixed હોય છે. વધુ ખરાબ, જ્યારે first request serve થાય છે, 99 entries ને forward shift કરવું real work છે, દરેક single time.
જે queue જોઈએ છે એ છે એક request એક સમયે grow થવું અને served ones ને instantly shed કરવા. Arrays નથી કરી શકતા. આ unit એ build કરે છે જે કરી શકે છે, માત્ર Java classes થી.
Theory
Treasure hunt, shelf નહીં
Array એ numbered slots ધરાવતી shelf છે: slot 47 શોધવા માટે તમે ત્યાં straight jump કરો છો, પણ shelf ની length welded છે.
Linked structure એ treasure hunt છે: દરેક clue એક prize (data) hold કરે છે અને next clue તરફ directions. કોઈપણ જગ્યાએ clue add કરો એક direction rewrite કરીને; એક remove કરો same રીતે. કોઈ shelf નહીં, કોઈ welding નહીં, માત્ર clues જે જાણે છે કે hunt ક્યાં continue થાય છે. છેલ્લું clue કહે છે: hunt over.
Theory
self-referential class
Clue, Java માં, એ class છે જે its own type ને refer કરે છે:
class Node {
String title; // data (એક request)
Node next; // NEXT node નો reference
}
Node next ને carefully વાંચો: એ reference છે, address slot છે, Node ની અંદર stuffed Node નહીં. એટલે જ આ infinite Russian doll create કર્યા વગર compile થાય છે: object બીજા object તરફ directions hold કરે છે, object itself નહીં.
next == null નો અર્થ છે: hunt over, chain નું end.
Practical
પહેલી chain ને હાથથી forge કરવી
class Node {
String title;
Node next;
Node(String t) { title = t; } // next null તરીકે start થાય છે (field default)
}
public class IssueQueue {
public static void main(String[] args) {
Node first = new Node("Let Us C");
Node second = new Node("Java Complete Reference");
first.next = second; // એક assignment: chain form થાય છે
// second.next પહેલેથી null છે: chain નું end
System.out.println(first.title);
System.out.println(first.next.title); // reached VIA the link
}
}
At a glance
Array vs linked chain
| Aspect | Array | Linked chain |
|---|---|---|
| Size | creation પર fixed | એક node એક સમયે grows અને shrinks |
| front માં Insert/delete | everything shift કરો | 1 અથવા 2 references re-link કરો |
| i-th item ને reach કરો | Instant: queue[i] | start થી chain ને walk કરો |
| Memory | એક solid block, possibly half empty | item દીઠ exactly one node, plus link slots |
Think first
Russian-doll worry
classmate objection કરે છે: "class Node એ Node contain કરે છે, જે Node contain કરે છે... surely એક new Node("x") infinite tower allocate કરે છે?" tap કરતા પહેલા: એ picture માં શું wrong છે?
Show the answer
field એ reference છે, embedded object નહીં. new Node("x") એ ONE node allocate કરે છે: તેનું title slot અને એક address-sized next slot, જે null તરીકે start થાય છે (Unit 2 નું field default). બીજું કંઈ build નથી થતું જ્યાં સુધી તમે explicitly create અને link ન કરો. BCA304 ના C++ માં આ struct Node { Node* next; } હતું: asterisk એ indirection ને visible બનાવતું હતું. Java references same indirection છે syntax hidden સાથે, અને કોઈ pointer arithmetic allowed નથી.
Quiz
Nodes ની chain માં, program કેવી રીતે જાણે છે કે છેલ્લા node પર પહોંચી ગયું છે?
- તેનો next reference null છે
- તેનું title field ખાલી છે
- Java છેલ્લા node પર exception throw કરે છે
- Node class chain ની total length store કરે છે
Show the answer
તેનો next reference null છે
next slot માં null એ agreed full stop છે: કોઈ further clue નહીં. એ convention coming lessons ના દરેક loop ને drive કરે છે: while (cur != null) chain ને walk કરે છે, અને cur.next == null તેના tail ને શોધે છે. Option B data ને structure સાથે confuse કરે છે; request નું title position વિશે કંઈ કહેતું નથી. Option C એ થાય છે જ્યારે તમે null ને IGNORE કરો અને cur.next.title ને એક step too far call કરો: NullPointerException. Option D bookkeeping ને describe કરે છે જે plain node deliberately carry નથી કરતું.
Watch out
chain ને hurt કરવાની બે રીતો
end થી આગળ walking: cur.next.title જ્યારે cur already last node હોય ત્યારે null ને dereference કરે છે: NullPointerException, chain-builder ની signature crash. step કરતા પહેલા check કરો.
only reference ને dropping: આ listing માં, first એ આખી chain નો sole handle છે. એને overwrite કરો (first = null) અને બંને nodes unreachable બની જાય છે; garbage collector એને reclaim કરે છે. Java માં delete નથી, પણ તમે head ને let go કરીને structure ને LOSE કરી શકો છો.
Theory
એક class, many structures
આ unit નું everything, અને પછીના દરેક data-structures course નો અડધો ભાગ, આ એક idea છે differently dressed: nodes plus links. nodes ને line માં string કરો અને તમારી પાસે singly linked list છે (next lesson); last link ને start પર back bend કરો અને એ circular બને છે (unit નું finale). BCA304 ના stacks અને queues બધા એના પર rebuild થઈ શકે છે. node ને once, deeply learn કરો; બાકીનું clues ને arrange કરવાનું છે.
Summary
Key takeaways
- Data structures self-referential class થી build થાય છે: data fields plus same type નો next reference.
- next એ reference છે (address), embedded object નહીં: infinite nesting નહીં, new દીઠ one node.
- Chains assignment દ્વારા form થાય છે (first.next = second); next માં null end mark કરે છે.
- Arrays fixed અને shift-heavy છે; chains per node grow થાય છે અને cheaply re-link થાય છે, પણ search કરવા માટે walk કરવી પડે છે.
- null ને dereference કરવું (end થી એક step past) NullPointerException throw કરે છે.
- head reference ને lose કરવાથી આખી chain garbage collection માં lost થાય છે.
- Memory hook: દરેક node એ clue છે: એક prize, next તરફ એક direction.