Linked List I
Linked List I
Linked List I
Session 02
1
Learning Outcomes
At the end of this session, students will be able to:
LO 1: Explain the concept of data structures and its usage in
Computer Science
LO 2: Illustrate any learned data structure and its usage in
application
LO 3: Apply data structures using C
2
Outline
1. Linked List Introduction
2. Linked List vs Array
3. Single Linked List
4. Polynomial Representation
3
Linked List Introduction
• Linked list is a data structure that consists of a sequence
of data records such that each record there is a field that
contains a reference to the next record in the sequence.
• Linked list allows insertion and deletion of any element
at any location.
• Linked list is used in many algorithms for solving real-
time problems, when the number of elements to be
stored is unpredictable and also during sequential access
of elements.
• A linked list consists of two types:
– Single Linked List
– Double Linked List
4
Linked List Introduction
• Take a look at the following figure:
5
Linked List versus Array
Array:
Linear collection of data elements
Store value in consecutive memory locations
Can be random in accessing of data
Linked List:
Linear collection of nodes
Doesn’t store its nodes in consecutive memory locations
Can be accessed only in a sequential manner
6
Memory Allocation: Dynamic
• If you need to allocate memory dynamically (in
runtime), you can use malloc in C/C++.
• To de-allocate you can use free.
7
Single Linked List
• To create a linked list, we first need to define a node structure
for the list.
struct tnode {
int value; head is the pointer to the
struct tnode *next; first element in our linked
}; list.
8
Single Linked List
• To create a list, we first need to define a node structure for the
list.
struct tnode {
int value;
struct tnode *next;
}; head is the pointer to the
first element in our linked
list.
struct tnode *head = 0;
Single Linked List: Insert
6 3 9 2 7 1 1 0 x
Summary
• Linked list is useful, especially in solving real-time
problems where the number of elements to be
stored is unpredictable and also during sequential
access of elements.
• Linked List has two types, single and double linked
list.
• Single linked list is characterized by having a single
one way link from a list pointing to another list
18
References
• S. Sridhar. 2015. Design and Analysis of Algorithms.
Oxford University Press. New Delhi. ISBN:
9780198093695. Chapter 5
• Reema Thareja. 2014. Data structures using C.
Oxford University Press. New Delhi.
ISBN:9780198099307. Chapter 6
• Thomas H. Cormen, Charles E. Leiserson, Ronald L.
Rivest, & Clifford Stein. (2009). Introduction to
Algorithms. 03. The MIT Press. London. ISBN:
9780262033848. Chapter 10
• Linked List, https://visualgo.net/en/list?slide=3
19