Formula Sheets: Linked Lists | Programming and Data Structures - Computer Science Engineering (CSE) PDF Download

 Page 1


Link ed List F orm ula Sheet
Link ed List Basics
• Definition : Dynamic data structure with no des con taining data and p oin ter(s) to next/previous
no de(s).
• No de Structure (Singly Link ed List) : No de = { data, next} , where next is p oin ter to next
no de.
• Memory Size : S
list
= n·(S
data
+S
p oin ter
) , where n is n um b er of no des, S
p oin ter
= 4 or 8 b ytes
(32/64-bit system).
• A ccess Time : O(n) for index-based access, unlik e arra ys (O(1) ).
T yp es of Link ed Lists
• Singly Link ed List : Eac h no de has next p oin ter, prev = NULL.
• Doubly Link ed List : Eac h no de has next and prev p oin ters, S
no de
=S
data
+2·S
p oin ter
.
• Circular Link ed List : Last no de p oin ts to first, tra v ersal time O(n) p er cycle.
• Memory Ov erhead :
– Singly: n·S
p oin ter
.
– Doubly: 2n·S
p oin ter
.
– Circular: Same as singly or doubly , no NULL p oin ter.
Basic Op erations
• Insertion :
– A t Head: Time Complexit y O(1) , Space Complexit y O(1) .
– A t T ail: Time Complexit y O(n) (singly , without tail p oin ter), O(1) (with tail or doubly).
– A t P osition k : Time Complexit y O(k) , 1=k =n .
• Deletion :
– A t Head: Time Complexit y O(1) .
– A t T ail: Time Complexit y O(n) (singly), O(1) (doubly with tail).
– A t P osition k : Time Complexit y O(k) .
• T ra v ersal : Time Complexit y O(n) , Space Complexit y O(1) (iterativ e), O(n) (recursiv e).
• Searc h : Time Complexit y O(n) , A v erage Comparisons:
n+1
2
.
• Length : Time Complexit y O(n) , or O(1) with stored coun ter.
Common Algorithms
• Rev erse Link ed List :
– Iterativ e: Time Complexit y O(n) , Space Complexit y O(1) .
– Recursiv e: Time Complexit y O(n) , Space Complexit y O(n) (call stac k).
– Op eration: next? prev, for e ac h no de.
• Detect Cycle (Flo yd’s Cycle-Finding Algorit hm) :
– Time Complexit y: O(n) , Space Complexit y O(1) .
– T w o-P oin ter Metho d: Slo w mo v es 1 step, fast mo v es 2 steps, meet if cycle exists.
– Cycle Length: L
cycle
=O(n) steps after meeting p oin t.
1
Page 2


Link ed List F orm ula Sheet
Link ed List Basics
• Definition : Dynamic data structure with no des con taining data and p oin ter(s) to next/previous
no de(s).
• No de Structure (Singly Link ed List) : No de = { data, next} , where next is p oin ter to next
no de.
• Memory Size : S
list
= n·(S
data
+S
p oin ter
) , where n is n um b er of no des, S
p oin ter
= 4 or 8 b ytes
(32/64-bit system).
• A ccess Time : O(n) for index-based access, unlik e arra ys (O(1) ).
T yp es of Link ed Lists
• Singly Link ed List : Eac h no de has next p oin ter, prev = NULL.
• Doubly Link ed List : Eac h no de has next and prev p oin ters, S
no de
=S
data
+2·S
p oin ter
.
• Circular Link ed List : Last no de p oin ts to first, tra v ersal time O(n) p er cycle.
• Memory Ov erhead :
– Singly: n·S
p oin ter
.
– Doubly: 2n·S
p oin ter
.
– Circular: Same as singly or doubly , no NULL p oin ter.
Basic Op erations
• Insertion :
– A t Head: Time Complexit y O(1) , Space Complexit y O(1) .
– A t T ail: Time Complexit y O(n) (singly , without tail p oin ter), O(1) (with tail or doubly).
– A t P osition k : Time Complexit y O(k) , 1=k =n .
• Deletion :
– A t Head: Time Complexit y O(1) .
– A t T ail: Time Complexit y O(n) (singly), O(1) (doubly with tail).
– A t P osition k : Time Complexit y O(k) .
• T ra v ersal : Time Complexit y O(n) , Space Complexit y O(1) (iterativ e), O(n) (recursiv e).
• Searc h : Time Complexit y O(n) , A v erage Comparisons:
n+1
2
.
• Length : Time Complexit y O(n) , or O(1) with stored coun ter.
Common Algorithms
• Rev erse Link ed List :
– Iterativ e: Time Complexit y O(n) , Space Complexit y O(1) .
– Recursiv e: Time Complexit y O(n) , Space Complexit y O(n) (call stac k).
– Op eration: next? prev, for e ac h no de.
• Detect Cycle (Flo yd’s Cycle-Finding Algorit hm) :
– Time Complexit y: O(n) , Space Complexit y O(1) .
– T w o-P oin ter Metho d: Slo w mo v es 1 step, fast mo v es 2 steps, meet if cycle exists.
– Cycle Length: L
cycle
=O(n) steps after meeting p oin t.
1
• Merge T w o Sorted Link ed Lists :
– Time Complexit y: O(n+m) , where n,m are lengths of lists.
– Space Complexit y: O(1) (in-place merging).
– Comparisons: =n+m-1 .
• Middle No de (T w o-P oin ter T ec hnique) :
– Time Complexit y: O(n) , Space Complexit y O(1) .
– Slo w p oin ter: 1 step, F ast p oin ter: 2 steps, slo w reac hes middle when fast reac hes end.
• In tersection of T w o Link ed Lists :
– Time Complexit y: O(n+m) , Space Complexit y O(1) (length-based) or O(min(n,m)) (hash-
based).
– Length Difference: d =|n-m| , skip d no des in longer list.
Applications of Link ed Lists
• P olynomial Represen tation : Eac h no de stores co e?icien t and exp onen t, S
no de
=S
co eff
+S
exp
+
S
p oin ter
.
• LR U Cac he : Doubly link ed list for orde r, Time Complexit y O(1) for get/put with hash map.
• Stac k/Queue Implemen tation : Time Complexit y O(1) for push/p op o r enqueue/dequeue.
• Memory Allo cation : F ree list in OS, O(n) to find free blo c k.
Link ed List vs. Arra y
• A ccess :
– Arra y: O(1) , Link ed List: O(n) .
• Insertion/Deletion :
– Arra y: O(n) (shifting), Link ed List: O(1) (at head/tail), O(k) (at p osition k ).
• Memory :
– Arra y: Con tiguous, S =n·S
elemen t
.
– Link ed List: Non-con tiguous, S =n·(S
data
+S
p o in ter
) .
• Cac he P erformance : Arra ys b etter due to lo calit y , Link ed Lists suffer from p oin ter c hasing.
P erformance M etrics
• Time Complexit y Comparison :
– A ccess/Searc h: O(n) vs. Arra y O(1) access.
– Insert/Delete: O(1) (head/tail) vs. Arra y O(n) .
– Merge: O(n+m) vs. Arra y O(nlogn) for sorting-based merge.
• Space Complexit y :
– Singly: O(n) , Doubly: O(n) with 2·S
p oin ter
o v erhead.
– Extra Space: O(1) for most op erations, O(n) for recursiv e or cop y op erations.
• Op eration Ov erhead :
– P oin ter Up dates: O(1) p er no de for insert/delete.
– T ra v ersal: O(n) vs. Arra y O(n) but w orse cac he p erformance.
• Scalabilit y : Dynamic size vs. Arra y’s fixed size (or amortized O(1) for dynamic arra ys).
2