Data structure & algorithms (Link list & arrays notes)

Data Structures and Algorithm
(CC-2042)
Lecture 7 & 8
E N G R. D R B I L A L A S H FA Q A H M E D
S C H O O L O F S Y S T E M S A N D T E C H N O LO GY ( S S T )
C O M P U T E R S C I E N C E FA C U LT Y

, Link List
•Definition: A Linked List is a linear data
structure where elements are stored in nod
each containing data and a pointer to the n
node.
Key Characteristics:
• Dynamic Size: Can grow or shrink as nee
• Memory Allocation: Non-contiguous me
allocation, unlike arrays.

Types of Linked Lists: Singly, Doubly, and
Circular Linked Lists.




10/31/2024 DS

,Linked List and Array
 Linked lists and arrays are similar since they both store
collections of data.
 The array's features all follow from its strategy of allocating
the memory for all its elements in one block of memory.
 Linked lists use an entirely different strategy: linked lists
allocate memory for each element separately and only when
necessary.




10/31/2024 DS

, Linked List vs. Array
• In a linked list, nodes are not necessarily contiguous in memory
(each node is allocated with a separate “new” call)
• Compare this to arrays which are contiguous
Array



head Linked List
NULL
4
10/31/2024 DS