The study underscores the importance of collaborative efforts and technological solutions in tackling pension contribution issues.ppt

This chapter explores the knowledge gap in pension regulation compliance among SMEs. It examines the impact of financial literacy, the complexity of pension laws, and industry-specific challenges on compliance. The analysis reveals that lack of awareness and understanding, rather than deliberate evasion, often leads to non-compliance.

1. Linked Lists
(Part 1)
Data Structures

2. CT077-3-2-DSTR Data Structures 2
Objectives
By the end of this lesson, you will be able to:
•Explain linked list linear data structure
•Explain the basic properties of a linked list and
its advantages
•Be able to implement some of the basic
operations on linked lists
•Create, manipulate, and use linked list objects in
your programs

3. CT077-3-2-DSTR Data Structures 3
Introduction
•A collection of items can be organized and
processed in memory using a list data structure
–A list as an abstract type is a linear structure which
contains a sequence or elements (first element,
second element, last element, previous element, etc.)
•A particular example of lists is array (Array List)
–Adjacent chunks of memory, where elements
are accessed directly through integer indices
beada
01234
…

4. CT077-3-2-DSTR Data Structures 4
Introduction
•Another example of lists is Linked Lists
•Array lists have advantages
–Fast random access to any element
–Easy to use and program with
•but also have disadvantages
–Array size is fixed (changing it is costly)
–Insertion of new elements and deleting existing elements
are slow operations (unless happening at the end)
Why need
one?

5. CT077-3-2-DSTR Data Structures 5
•It is a series of connected nodes, where each
node is a data structure
•Every node (except last)
–Contains address of the next (following) node
•Node components
–Data: stores relevant information
–Link: stores address
Linked Lists
Structure of a node

6. CT077-3-2-DSTR Data Structures 6
•An arrow points to the following node’s address
–A pointer value stored in node
•Down arrow in last node indicates NULL link field,
i.e. a pointer pointing at nothing
–X mark is also used in diagrams instead of down arrow
•Head (or first) address allows access to list
elements
–Address of the first node in the list
Linked Lists
Linked list

7. CT077-3-2-DSTR Data Structures 7
•Example: a list containing two elements (45 and 65)
–supposing the first node is at memory location
1200, and the second node is at memory
location 1575, linked list will look like this
–Most of the time, we just draw arrows to indicate
pointers pointing at memory locations, since the
exact address values are not of high importance
Linked Lists
Linked list and values of the links
0

8. CT077-3-2-DSTR Data Structures 8
Linked List Nodes
•Because each node of a linked list has two
components, we need to declare each node as a
class (or struct)
–Data type (or info) of a node depends on the
specific application (linked list of what?)
–The link component of each node is a pointer
struct NodeType {
int info;
NodeType* link;
};
class NodeType {
public:
int info;
NodeType*
link;
};
Or a struct can be used similarly

9. CT077-3-2-DSTR Data Structures 9
Linked Lists: Some Properties
•A head variable is declared as
and it stores address of first node in the list
•For each node
–Info stores information
–Link stores address of next node
•For example, we can have the following list
NodeType *
head;

10. CT077-3-2-DSTR Data Structures 10
Linked Lists: Some Properties

11. CT077-3-2-DSTR Data Structures 11
Linked Lists: Some Properties
•NodeType * current = head;
–Copies value of head into current
Value
current
current->info
current->link
current->link->info 92
2000
17
2800

12. CT077-3-2-DSTR Data Structures 12
Linked Lists: Some Properties
•current = current->link;
–Copies value of current->link (2800)
into current
Value
current
current->info
current->link
current->link->info 63
2800
92
1500

13. CT077-3-2-DSTR Data Structures 13
Linked Lists: Some Properties
Value
head->link->link
head->link->link->info
head->link->link->link
head->link->link->link->info
current>link->link
current->link->link->info
current>link->link->link
current>link->link->link->info
45
1500
63
3600
Does not exist
3600
45
0 (that is, NULL)
gives runtime error

14. CT077-3-2-DSTR Data Structures 14
Traversing a Linked List
•The basic operations of a linked list are:
–Determine the size of the list
–Insert an item in the list
–Search to determine if an item is in the list
–Accessing list elements (get and set element at index i)
–Delete an item from the list
•These operations require list traversal
–Given a pointer to the first node of the list, step through
all nodes of the list, one by one

15. CT077-3-2-DSTR Data Structures 15
Traversing a Linked List
•To traverse a linked list given its head pointer:
•Example, printing list’s elements:

16. CT077-3-2-DSTR Data Structures 16
Getting Linked List Size
•Using traversal, how to calculate the number of
elements (nodes) in the list?
•Is there a better way to know linked list’s size other
than scanning (traversing) the whole list every time?
current = head;
int size = 0;
while(current != NULL){
size++;
current = current->link;
}

17. CT077-3-2-DSTR Data Structures 17
Creating a LinkedList Structure
•A class will be created to represent a Linked List object
•It encapsulates the head pointer, and possibly other data
members (will make everything public in this course to keep it
simple, but you know that proper info hiding should be used)
•It provides all the methods necessary to utilize and
manipulate a particular linked list object
class LinkedList {
public:
NodeType* head;
LinkedList();
int getSize();
...
};

18. CT077-3-2-DSTR Data Structures 18
Size of a LinkedList
•Create a size field (data member) encapsulated in the
LinkedList data structure (initialized to zero in constructor)
•Update the field upon insertion and deletion (+1 or -1)
class LinkedList {
public:
NodeType* head;
int size;
int getSize(){
int size = 0;
NodeType * current = head;
while(current != NULL){
size++;
current = current->link;
}
return size;
}
};
This is a simple example
of how a data structure
and an algorithm
cooperate to implement
efficient solutions.

We traded off extra small
memory (not necessarily
always small) to gain
speed in calculating the
size of the linked list.
Improve getSize() ?

19. CT077-3-2-DSTR Data Structures 19
Inserting a New Element
•We can insert new elements at the beginning of
the list, at the end of it, or at given position index
LinkedList(){
this->size = 0;
this->head= NULL;
}
void insertAtBeginning(int value){
NodeType * newNode= new
NodeType;
newNode->info = value;
newNode->link = head;
head = newNode;
size++;
}
// .. the other implemented methods
};
class NodeType {
public:
int info;
NodeType* link;
};
class LinkedList {

public:
NodeType* head;
int size;

20. CT077-3-2-DSTR Data Structures 20
Why the New Node Should be in
the Heap?
•What happens if we change the implementation of
insert so that a new node is created in the stack?
void insertAtBeginning(int
value){
NodeType newNode;
newNode.info = value;
newNode.link = head;
head = & newNode;
size++;
}
void main(){
LinkedList list;
list.insertAtBeginning(5);
cout << list.head->info;
}
The object newNode will be
deleted from memory after
insertAtBeginning function
ends, and therefore the
head of the list will be a
dangling pointer.

21. CT077-3-2-DSTR Data Structures 21
Inserting a New Element
•Draw a diagram representing what happens in
the memory by running this program:
void main(){
LinkedList l1;
LinkedList l2;
l1.insertAtBeginning(5);
l1.insertAtBeginning(9);
l1.insertAtBeginning(3);
cout << l1.getSize() << endl;
l2.insertAtBeginning(9);
l2.insertAtBeginning(7);
cout << l2.getSize() << endl;
}

22. CT077-3-2-DSTR Data Structures 22
Inserting a New Element at the End
•Write the code that navigates until the last node,
and then inserts the new node there
void insertAtEnd(int value){
NodeType * newNode= new
NodeType;
newNode->info = value;
newNode->link = NULL;
if (head == NULL)
head = newNode;
else{
NodeType * last = head;
while(last->link != NULL)
last= last->link;
last->link = newNode;
}
size++;
}
Create and setup
the new node
If the list is empty
The general case
requires finding
the last node in
the list and make
its link point at
the new node

23. CT077-3-2-DSTR Data Structures 23
Clearing a Linked List
•Sometimes you fill up a list, and want to empty it so that it
can be filled up again with new elements
•Simply assigning NULL to head and zero to size will create
a memory leak problem
void clear (){

NodeType * current = head;
while(head != NULL){
current = current->link;
delete head;
head = current;
}
size = 0;
}

24. CT077-3-2-DSTR Data Structures 24
Proper Cleaning of the Memory
•What should happen to the dynamically created nodes
should when the linked list object gets destructed?
•Implement the destructor to delete all the nodes when the
list object is deleted
–It can simply just call clear() method
•What is the print output of the following main program?
void main(){
if (true) {
LinkedList list;

list.insertAtBeginning(5);

list.insertAtBeginning(9);
}
LinkedList list2;

list2.insertAtBeginning(3);
}
~LinkedList(){
cout <<"Going to delete all " << size
<<" elements of the list." <<
endl;
NodeType * current = head;
while(head != NULL){
current = current->link;
delete head;
head = current;
}
}

25. CT077-3-2-DSTR Data Structures 25
Homework
•Define the classes NodeType and LinkedList in C++ project
•Provide the implementation necessary for the following code
sample to work. Confirm your correct implementation by
examining generated output
void main(){
LinkedList list;
list.insertAtBeginning(5);
list.insertAtEnd(9);
list.insertAtBeginning(3);
cout << list.getSize() << endl;
list.print();

list.insertAtEnd(11);
cout << list.getSize() << endl;
list.print();
}

26. CT077-3-2-DSTR Data Structures 26