Lesson Data Structures in AI - Artificial Intelligence - ثالث ثانوي

Lesson 2 Data Structures in Al Link to digital lesson www.ien.edu.sa The Importance of Data Structures in Al Data is critical in Al as it is the foundation for training machine learning models. The quality and quantity of data available determine the accuracy and effectiveness of Al models. Without sufficient relevant data, Al algorithms cannot learn patterns, make predictions or perform tasks effectively. Hence, data plays a crucial role in shaping Al systems' decision-making abilities and capabilities. Data structures are important in Al because they provide an efficient way to organize and store data that allows for efficient retrieval and manipulation. They determine the complexity and efficiency of algorithms used to process data and thus directly impact the performance of Al systems. For instance, using an appropriate data structure can improve the speed and scalability of Al algorithms, making them more suitable for real-world applications. Additionally, well-designed data structures can help reduce memory usage and make algorithms more memory-efficient, enabling the processing of larger datasets. Computers store and process data with extraordinary speed and accuracy. So, it is highly essential that the data is stored efficiently and can be accessed quickly. Data Structures can be classified as follows: • Primitive Data Structures. • Non-Primitive Data Structures. The diagram in figure 1.11 visualizes the classification of data structures. Data Structure A Data Structure is a technique for storing and organizing data in memory so that it can be used efficiently. Simple data is also called primitive, raw, or basic data. Primitive Data Structures Data Structures Boolean Character Float Integer Linked List Queue Stack وزارة التعليم Ministry of Education 2024-1446 Non-Primitive Data Structures Linear Data Structures Non-Linear Data Structures Dictionary Tuple Figure 1.11: Data structures diagram Graphs Trees Array List 23

Primitive Data Structures Primitive Data Structures are also referred to as basic data structures in Python. This type of structure contains simple values of data. Simple data types tell the compiler which type of data to store in it. The basic data structures in Python are: Different types of data structure are used for different computer applications and tasks, based on the requirements of the project and the restrictions on memory. • Numbers (Numbers are used to represent numeric data) - Integers - Floating point number • Strings (Strings are collections of characters and words) • Boolean (A Boolean data type takes one of two values, True or False) Non-Primitive Data Structures Non-Primitive Data Structures are specialized structures which store a group of values. They are created by the programmer and they are not defined by Python like the primitives. Non-primitive data structures can also be divided into two categories: • Linear or sequential data structures Linear data structures store the data elements in a sequence. • Non-linear data structures Non-linear data structures do not have a sequential linking between data elements. Any pair or group of data elements can be linked to each other and can be accessed without a strict sequence. Linear Data Structures Linear data structures store data elements in a sequence. In this lesson, you will learn about some linear data structures such as stacks and queues. These are two of the most common structures you will come across in your daily life. Stack A stack can actually be represented by a group of books stacked on top of each other, as shown in figure 1.12. To group a stack, you have to put the books one on top of another. When you want to use a book, you have to pick up the book at the top of the stack. To access the other books in the stack, you will have to remove the books from the top of the stack. A stack can either have a fixed size or it can resize dynamically. Python implements stacks using lists. Figure 1.12: A stack of books as a real-life example Last In First Out (LIFO) rule The element which is added last is accessed first. من التعليم Ministry of Education 24 2024-1446

Operations on the stack There are two main operations on the stack: • Push: This operation is used to add an element to the top of the stack. • Pop: This operation is used to remove an element from the top of the stack. Push Operation The operation of adding a new element on the stack is called a push. The stack uses a pointer called Top. The pointer points to the element on the top of the stack. When a new element is added to the stack: • The value of the top pointer is increased by one to show the new position the element will be placed in. • The new element is added to the top of the stack. Stack Overflow The stack has a specific capacity that depends on the computer's memory. If that capacity is full, adding a new element will cause the stack overflow. The stack should be checked for fullness before adding an element. Pop Operation The operation of removing an element from the stack is called a pop. When removing an element from the stack: • The element at the top of the stack is removed. • The value of the top pointer is decreased by one to show the element on the top of the stack. Stack Underflow If you want to remove an element from the stack, you must check first that the stack contains at least one element; If the stack is empty, you will cause a stack underflow. وزارة التعليم Ministry of Education 2024-1446 Push element Top element Top element E E D D D C C C B B B A A A Initial Stack Final Stack Figure 1.13: Push operation Pop element Top element Top element E E D D D C C C B B B A A A Initial Stack Final Stack Figure 1.14: Pop operation 25

Stack in Python Stacks are represented in Python using Lists, which in turn provide some ready-to-use operations with stacks. Table 1.2: Stack operations Methods listName.append(x) listName.pop() Description Adds the x element to the end of the list. Removes the last element from the list. Let's see an example of the implementation of a stack in Python. 1 Create a stack to store a set of numbers (1, 21, 32, 45). Use the pop operation twice to remove the last two elements (45, 32) from the stack. ③ Use the push operation to add a new element (78) to the stack. The push operation of the stack is implemented in Python using the append function. Push element Push element 45 Top element 45 Push element 32 32 32 21 Push element 21 21 21 ་ 21 1 1 1 1 1 1 45 Pop element 45 32 Pop element 32 32 21 21 21 Push element 78 78 21 21 1 1 1 1 1 2 3 وزارة التعليم Ministry of Education 26 ZU24-1446 Figure 1.15: Stack Example

Jupyter Notebook In this unit, you will write a Python program using Jupyter Notebook. Jupyter Notebook is an online web application to create and share computational documents. Each document, called a notebook, includes your code, comments, raw and processed data, and data visualizations. You will use the offline version of Jupyter Notebook. The easiest way to install it locally is through Anaconda, an open-source distribution platform, which is free for students and hobbyists. Download and install Anaconda from here: https://www.anaconda.com/products/distribution. Python and Jupyter Notebook will be installed automatically. ANACONDA. Jupyter 2 Adobe Acrobat DC New Alarms & Clock Anaconda3 (64-bit) Anaconda Navigator (Anaconda3) New Anaconda Powershell Prompt (Anac... New Anaconda Prompt (Anaconda3) New A To open Jupyter Notebook: > Click Start 1, click Anaconda3. 2 , > Select Jupyter Notebook. 3 > The Jupyter Notebook home page opens in the browser. Home Page - Select or create a x + CA Jupyter Files Running localhost:8888/tree Clusters Select items to perform actions on them. 3D Objects Anaconda3 Contacts Creative Cloud Files Desktop Documents Downloads Favorites Links Music OneDrive Pictures وزارة التعليم Ministry of Education 2024-1446 Searches Videos New Jupyter Notebook (Anaconda3) New Reset Spyder Settings (Anaconda3) New Spyder (Anaconda3) New 1 B D Quit Logout Upload New C Jupyter Notebook home page Name Last Modified File size a year ago 2 hours ago Figure 1.16: Jupyter Notebook home page a year ago 2 hours ago 26 minutes ago 2 hours ago 2 hours ago a year ago a year ago a year ago 2 years ago 2 hours ago 2 months ago a month ago 3 x 27

To create a new notebook: > At the top right corner of your screen, click New. > Select Python 3 (ipykernel). 2 > Your notebook opens in a new tab in your browser. 3 You can Upload a notebook from your computer. Home Page Select or create a x + C Jupyter Files Running localhost:8888/tree Clusters Select items to perform actions on them. 0 3D Objects Anaconda3 Contacts Creative Cloud Files O Desktop Documents A B - Quit Logout 1 Upload New C Notebook: Name↓ Python 3 (ipykernel) 2 Other: Create a ne 3 Home Page - Select or create a x Untitled - Jupyter Notebook + →> C ①localhost:8888/notebooks/Untitled.ipynb... A Jupyter Untitled (unsaved changes) B Text File Folder Terminal 4 hours ago 2 hours ago 3 hours ago Logout File Edit View %1 Insert Cell Kernel Widgets Help Run C Code Trusted Python 3 (ipykernel) O In [ ] : Code cell. You can type text, a math expression or a Python command. وزارة التعليم Ministry of Education 28 ZU24-1446 Notebook toolbar. The default name of the notebook is Untitled. Figure 1.17: Create a new Jupyter Notebook

Now that your notebook is ready, it's time to write and run your first program in Jupyter Notebook. You can have as many different cells as you need in the same notebook. Each cell contains its own code. To create a program in Jupyter Notebook: > Type the commands inside the code cell. 1 > Click the Run button. 2 > The result is displayed under the commands. Jupyter Untitled (unsaved changes) Logout File Edit View Insert 2 2 Kernel Widgets Help Trusted | Python 3 (ipykernel) O B+% Run C Code In [1]: print ("Welcome to Jupyter Notebook") 1 Welcome to Jupyter Notebook 3 In []: When you run your program, a new code cell is automatically added. Figure 1.18: Create a program in Jupyter Notebook You can run your program by pressing Shift + Enter + It's time to save your notebook. To save your notebook: > Click File. 1 When you are working, the notebook is autosaved. > Select Save as. 2 > Type a name for your notebook. 3 > Press Save. 4 1 upyter Untitled (autosaved) File Edit View Insert Cell Kernel Widgets New Notebook Open... Run C Code Jupyter My first notebook (autosaved) File Edit View Insert Cell Kernel B + Run C The name of the notebook has changed. عناية التعليم Ministry of Education 2024-1446 Make a Copy... Save as... 2 Rename... Save and Checkpoint sl he to Jupyter Notebook") upyter Notebook Save As Revert to Checkpoint Figure 1.19: Save your notebook Enter a notebook path relative to notebook dir My first notebook 3 4 Cancel Save 29

Let's see the example from figure 1.15 in Jupyter. 1. Create a stack to store a set of numbers (1, 21, 32, 45). 2. Use the pop operation twice to remove the last two elements from the stack. 3. Use the push operation to add a new element to the stack. myStack [1,21,32,45] print("Initial stack: ", myStack) print(myStack.pop()) print(myStack.pop()) print("The new stack after pop: myStack) myStack.append(78) "I ' print("The new stack after push: ", myStack) Initial stack: [1, 21, 32, 45] 45 32 The new stack after pop: [1, 21] The new stack after push: [1, 21, 78] The print(myStack.pop()) function is used to display the value returned by the myStack.Pop() function. myStack [1,21,32,45] print("Initial stack:", myStack) a-len(myStack) print("size of stack",a) # empty the stack for i in range(a): myStack.pop() -- print(myStack) myStack.pop() Initial stack: [1, 21, 32, 45] size of stack 4 The len function returns the length of the stack. This statement is used to delete all elements of the stack. [ ] IndexError Input In [3], in <cell line: 9>() 7 myStack.pop() 8 print(myStack) -> 9 myStack.pop() IndexError: pop from empty list Traceback (most recent call last). The error appeared because the stack is empty and you typed a command to delete an element from the empty stack. IndexError You will notice that an error appears. You typed a command to delete an element from the empty stack and this caused underflow to the stack. You should always check that there are elements in the stack before trying to delete an element from it. وزارة التعليم Ministry of Education 30 2024-1446

In the following program, you will create a stack and you will add or remove elements from it. The program displays a menu which asks you about the action you want to do each time. • To add an element to the stack, you have to press the number 1 in the program menu. • To remove an element from the stack, you have to press the number 2 in the program menu. • To exit the program, you have to press the number 3 in the program menu. def push(stack, element): stack.append(element) def pop(stack): return stack.pop() def is Empty(stack): return len(stack)==0 def createStack(): return [ ] newStack-createStack() while True: print("The stack so far is: ", newStack) وزارة التعليم Ministry of Education 2024-1446 print(" print("Choose 1 for push") print("Choose 2 for pop") print("Choose 3 for end") print(". -") -") choice=int(input("Enter your choice: ")) while choice! =1 and choice! =2 and choice! -3: print ("Error") choice=int(input("Enter your choice: ")) if choice==1: x=int(input("Enter element for push: ")) push(newStack,x) elif choice==2: if not isEmpty(newStack): print("The pop element is:", pop(newStack)) else: print("The stack is empty") print("End of program") else: break; 31

Execute the previous program as follows: • Create a stack of three numbers, and • Add elements to the stack. The stack so far is: [] Choose 1 for push. Choose 2 for pop Choose 3 for end Enter your choice: 1 Enter element for push: 26 The stack so far is: [26] Choose 1 for push Push element Choose 2 for pop Choose 3 for end Push element 23 Enter your choice: 1 Enter element for push: 18 The stack so far is: [26, 18] Choose 1 for push. Push element 18 Choose 2 for pop Choose 3 for end 18 26 26 26 Enter your choice: 1 Enter element for push: 23 The stack so far is: [26, 18, 23] Figure 1.20: Pushing elements Now, you will remove two elements from the stack and then exit the program. Choose 1 for push Choose 2 for pop Choose 3 for end Enter your choice: 2 The pop element is: 23 The stack so far is: [26, 18] Choose 1 for push Choose 2 for pop Pop element Pop element Choose 3 for end 23 23 18 18 18 Enter your choice: 2 The pop element is: 18 The stack so far is: [26] Choose 1 for push Choose 2 for pop Choose 3 for end 26 26 26 وزارة التعليم Ministry of Education 32 ZU24-1446 Figure 1.21: Popping elements Enter your choice: 3 End of program

Queue The next data structure you are going to explore is the queue. We often come across queues in our everyday life. The most common queue is the queue of cars waiting at a traffic light. When the traffic light turns green, the car that entered first in the queue will be the one which exits first. A queue is a data structure that follows the First In First Out (FIFO) rule, meaning that each element in the queue is served in the order it reaches the queue. First In First Out (FIFO) rule The first element added in the list is processed first and the newest element is processed last. First In First Out rule The difference between the stack and the queue is that in the stack, the addition and the deletion of an element are done from the same side. In the queue, the addition is done on one side and the deletion is done on the other side. So, in the stack, when deleting, the last added element is deleted, while in the queue, the first added element is deleted. Operations on the Queue: There are two main operations on the queue: . . Enqueue: This operation is used to add an element to the rear of the queue. Dequeue: This operation is used to remove an element from the front of the queue. Pointer The pointer is a variable which stores or points to the address of another variable. The pointer is like a page number in the index of a book that guides the reader to the required content. Queue Pointers The queue has two pointers: • Front pointer: Points to the first element of the queue. • Rear: points to the last element of the queue. Index Index is a number that describes the position of an element in a data structure. Front pointer Dequeue Index وزارة الكليم Ministry of Education 2024-1446 Queue Rear pointer Enqueue 9 17 43 21 7 12 56 23 4 14 31 1 2 3 4 5 6 7 88 6 10 Figure 1.22: Operations on the Queue 33

Enqueue Operation The operation of adding a new element to the queue is called Enqueue. To insert a new element into the queue: ⚫ the value of the rear pointer is increased by one and points to the position of the new element to be entered. ⚫ the element is inserted. You cannot add or remove an element from the middle of the queue. Front Rear Front Rear Front Rear A B C A B C <--- D A B C D 0 1 2 0 1 2 Before Enqueue 0 1 2 3 After Figure 1.23: Enqueue operation Dequeue Operation The operation of removing an element to a queue is called dequeue. To remove an element from the queue: ⚫ the element indicated by the front pointer is removed. • the value of the front pointer is increased by one to point to the next available element of the queue. Before any action you must check if there is free space in the queue to add a new element or if there is at least one element for export. Front Rear Front Rear Front Rear <-- A B C D A в/ с D B C D 0 1 2 3 0 1 2 3 0 1 2 وزارة التعليم Ministry of Education 34 2024-1446 Before Dequeue Figure 1.24: Dequeue operation After

Queue in Python In Python, the queue can be represented in several ways, including lists. This is due to the fact that a list represents a group of linear elements and also to the possibility of adding an element at the end of the list and the possibility of deleting an element from its beginning. Below you will learn the general formulas for some of the operations that can be performed on a queue: Table 1.3: Queue methods Method listName.append(x) listName.pop(0) Description Enqueue the element x to the list representing the queue. Dequeue the first element from the list. The listName.pop() method can be used for both stack and queue data structures. When it is used with a stack, the method has no arguments. When it is used with a queue, a zero needs to be added to the arguments: listName.pop(0). The difference between the two functions is presented in table 1.4 below. Table 1.4: listName.pop() vs listName.pop(0) method Method listName.pop() listName.pop(0) Description If the function argument is empty, the last element is removed from the end of the list that represents the stack. If the function argument is zero, the first element of the list representing the queue is removed. Let's see an example of the implementation of a queue in Python. • Create a queue to store the set of numbers (1, 21, 32, 45). • Use the dequeue operation twice to remove the first two elements from the queue. • Use the enqueue operation to add a new element to the queue. Front Rear Front Rear Front Rear 1 21 32 45 1 <-- 21 32 45 21 <--- 32 45 0 1 2 3 Dequeue 0 1 2 Dequeue 0 1 وزارة التعليم Ministry of Education 2024-1446 Front Rear Front Rear 32 45- 78 32 45 78 Final queue 0 1 0 1 2 Enqueue Figure 1.25: Graphical example of queue operations 35

To program the above steps in Python, you will use a Python list to implement the queue structure, as you did with the stack. myQueue [1,21,32,45] print("Initial queue: myQueue) ' myQueue.pop(0) myQueue.pop(0) print("The new queue after pop: myQueue.append(78) print("The new queue after push: Initial queue: [1, 21, 32, 45] "I , myQueue) "I myQueue) The new queue after pop: [32, 45] The new queue after push: [32, 45, 78] Let's see what happens if you try to remove an element from an empty queue. First you have to empty the queue. myQueue=[1,21,32,45] print("Initial queue: ", myQueue) a len(myQueue) print("size of queue ",a) # empty the queue for i in range(a): myQueue.pop(0) print(myQueue) myQueue.pop(0) Initial queue: [1, 21, 32, 45] size of queue 4 [ ] IndexError Input In [6], in <cell line: 9>() 7 myQueue.pop() 8 print(myQueue) ----> 9 myQueue.pop() IndexError: pop from empty list You should always check that there are elements in the queue before trying to delete an element. وزارة التعليم Ministry of Education 36 2024-1446 Traceback (most recent call last) The error appeared because you tried to delete an element from an empty queue.

Queue Applications One example of a queue in Computer Science is the printing queue. For example, you have a computer lab with 30 computers connected to one printer. When students want to print, their print jobs create a queue. The tasks are queued to be processed using a First In First Out (FIFO) method. Tasks will be printed in the order they were submitted. The task that was submitted first will be printed before the one that was submitted after. The task at the end of the queue will not be printed until all tasks before it have been printed. When the printer completes a job it will look in the queue to see if there are any jobs left to process. Stack and Queue Using Queue Module A list in Python can act as a queue and a stack as well. Python offers the Queue module which is another way to implement these two data structures. The Queue module includes some ready-to-use functions that can be used with both stack and queue. Table 1.5: Queue module methods Methods queueName=queue.Queue() queueName.put(x) queueName.qsize() queueName.get() queueName.full() queueName.empty() Description Creates a new queue named queueName. Adds the element x to the queue. Returns the size of the queue. Gets and removes the first element from the queue and the last element from the stack. Returns True if the queue is full and False if the queue is empty. Can be applied to the stack as well. Returns True if the queue is empty and False if the queue is full. Can be applied to the stack as well. The methods of the Queue module can be used with both the stack and the queue. You will use the Queue module to create a queue. In this example you should: Import the queue module to use the queue's methods. • Create an empty queue named myQueue. Add the elements a, b, c, d, e to myQueue. • Print elements of the queue. from queue import *• myQueue Queue() = # add the elements to the queue myQueue.put("a") myQueue.put("b") myQueue.put("c") myQueue.put("d") myQueue.put("e") # print the elements of the queue for element in list (myQueue.queue): print(element) You import the Queue module at the beginning of your code. وزارة التعليم Ministry of Education 2024-1446 a b C d 37

Create a queue in which five values are entered by the user during program execution, and then print these values and finally print the size of the queue. from queue import * myQueue Queue() = # the user enters the elements of the queue for i in range(5): for i in range(5): element input("enter queue element: ") myQueue.put(element) #print the elements of the queue for element in list(myQueue.queue): print(element) print ("Queue size is: ",myQueue.qsize()) enter queue element: 5 enter queue element: f enter queue element: 12 enter queue element: b enter queue element: 23 5 f 12 b 23 Queue size is: 5 Create a program to check if the queue is empty or full. from queue import * myQueue = Queue() myQueue.put("a") myQueue.put("b") myQueue.put("c") myQueue.put("d") myQueue.put("e") checkFull-myQueue. full() print("Is the queue full? ", checkFull) checkEmpty = myQueue.empty() print("Is the queue empty? ", checkEmpty) Is the queue full? False Is the queue empty? False وزارة التعليم Ministry of Education 38 2024-1446

Create a queue in which five values are entered by the user during program execution, and then print these values and finally print the size of the queue. from queue import * myQueue Queue() = # the user enters the elements of the queue for i in range(5): for i in range(5): element input("enter queue element: ") myQueue.put(element) #print the elements of the queue for element in list(myQueue.queue): print(element) print ("Queue size is: ",myQueue.qsize()) enter queue element: 5 enter queue element: f enter queue element: 12 enter queue element: b enter queue element: 23 5 f 12 b 23 Queue size is: 5 Create a program to check if the queue is empty or full. from queue import * myQueue = Queue() myQueue.put("a") myQueue.put("b") myQueue.put("c") myQueue.put("d") myQueue.put("e") checkFull-myQueue. full() print("Is the queue full? ", checkFull) checkEmpty = myQueue.empty() print("Is the queue empty? ", checkEmpty) Is the queue full? False Is the queue empty? False وزارة التعليم Ministry of Education 38 2024-1446

You can use the following algorithm: 1 Create a print job queue 2 Insert files from A to G into the print job queue A B с D E G 0 1 2 3 4 5 6 FL 10 3 Output file A and insert file H Printed A B C D E பட F G H 0 1 2 3 4 5 6 4 Output file B and insert file I Printed B C D E LL F G H 0 1 2 3 4 5 6 5 Output file C and insert file J Printed C D E F G H J 0 1 2 3 4 5 6 6 Output files that have been printed (D-E-F-G-H-I-J) one by one. D E F G H J 0 1 2 3 4 5 6 # import the queue library from queue import * # import the time library to use the sleep function import time #initialize the variables and the queue printDocument = printQueueSize = 0 printQueueMaxSize = 7 printQueue = Queue(printQueueMaxSize) # add a document to print the queue def addDocument(document): printQueueSize = printQueue.qsize() if printQueueSize == printQueueMaxSize: print("!! ", document, " was not sent to print queue.") print("The print queue is full.") print() return printQueue.put(document) time.sleep(0.5) #Wait 5.0 seconds print(document, sent to print queue.") printQueueSizeMessage() # print a document from the print queue def printDocument(): printQueueSize = printQueue.qsize() .if printQueueSize == 0: print("!! The print queue is empty.") وزارة التعليم Ministry of Education 40 2024-1446

print() return printDocument = printQueue.get() time.sleep(1) #wait one second print ("OK", printDocument, printQueueSizeMessage() # print a message with the size of the queue def printQueueSizeMessage(): is printed.") printQueueSize = printQueue.qsize() if printQueueSize == 0: print ("There are no documents waiting for printing.") elif printQueueSize == 1: else: print ("There is 1 document waiting for printing.") "I print ("There are ", printQueueSize, documents waiting for printing.") print() #the main program #send documents to the print queue for printing addDocument("Document A") addDocument("Document B") addDocument("Document C") addDocument("Document D") addDocument("Document E") addDocument("Document F") addDocument("Document G") printDocument() addDocument("Document H") printDocument() addDocument("Document I") printDocument() addDocument("Document J") addDocument("Document K") printDocument() printDocument() printDocument() printDocument() printDocument( ) print Document ( ) printDocument ( ) printDocument() Document A sent to print queue. There is 1 document waiting for printing. Document B sent to print queue. There are 2 documents waiting for printing. Document C sent to print queue. There are 3 documents waiting for printing. وزارة التعليم Ministry of Education 2024-1446 41

Document D sent to print queue. There are 4 documents waiting for printing. Document E sent to print queue. There are 5 documents waiting for printing. Document F sent to print queue. There are 6 documents waiting for printing. Document G sent to print queue. There are 7 documents waiting for printing. OK Document A is printed. There are 6 documents waiting for printing. Document H sent to print queue. There are 7 documents waiting for printing. OK Document B is printed. - There are 6 documents waiting for printing. Document I sent to print queue. There are 7 documents waiting for printing. OK - Document C is printed. There are 6 documents waiting for printing. Document J sent to print queue. There are 7 documents waiting for printing. !! Document K was not sent to print queue. The print queue is full. OK Document D is printed. - There are 6 documents waiting for printing. OK - Document E is printed. There are 5 documents waiting for printing. OK - Document F is printed. There are 4 documents waiting for printing. - OK Document G is printed. There are 3 documents waiting for printing. OK - Document H is printed. There are 2 documents waiting for printing. OK Document I is printed. - There is 1 document waiting for printing. OK - Document Jis printed. There are no documents waiting for printing. !! The print queue is empty. وزارة التعليم Ministry of Education 42 2U24-1446

Static and Dynamic Data Structures As mentioned before, a data structure is a way to efficiently store and organize data. You have also learned about the classification of data structures as primitive and non-primitive. Data structures can also be classified as Static and Dynamic. Static Data Structure In a static data structure, the size of the structure is fixed. The elements of the data are allocated to contiguous memory locations. The most representative example of a static data structure is the Array. Dynamic Data Structure In a dynamic data structure, the size is not fixed and it can be modified during the execution of the program, depending on the operations performed on it. Dynamic data structures are designed to facilitate the change in size of the data structures during run time. The most representative example of a dynamic data structure is the Linked List. Table 1.7: Static Data Structures vs Dynamic Data Structures Memory size Types of memory storage Data access speed Static Fixed memory size. The elements are stored in contiguous locations in the main memory. Faster to access. Dynamic The size can be changed during run time. The elements are stored in random places in the main memory. Slower to access. Memory Allocation Linked lists are dynamic data structures. This means that the nodes of the linked list are not stored in contiguous memory locations like the data of arrays. This is the reason you need to store the pointer from one node to another. = one byte of used memory Dynamic Static 1 ☐ 2 3 7: 77: 45 71 7 2 1 = one byte of used memory 3 5 4 <-- 77 Arrays need a contiguous block of memory. وزارة التعليم Ministry of Education 2024-1446 Linked lists don't need to be contiguous in memory, they can grow dynamically. Figure 1.26: Example of static and dynamic memory allocations 43

Linked List A Linked List is a linear data structure, and it is one of the most popular data structures in programming. A linked list is like a chain of nodes. Each node contains two fields: the data field where the data are stored and a field containing the pointer to the next node. This excludes the last node in which the address field does not carry any data. One of the advantages of the linked list is that it can dynamically increase or decrease its size by adding or deleting nodes. Head A Linked List 5 --> 7.2 -2 ༢-- ABC Null Linked List A Linked List is a linear data structure which is like a chain of nodes. Node A node is an individual block of a data structure which contains data and one or more links to other nodes Head Figure 1.27: Graphical representation of a linked list Node Each node in the linked list consists of two parts. • The first section contains the data. • The second part contains a pointer pointing to the next node. 12 To read the content of a specific node, you must pass through all previous nodes. Data field A pointer to the next node Figure 1.28: Graphical representation of a node Here you can see an example of an integer linked list. The linked list consists of five nodes. 21 Null Null means having no value, not defined or empty. Although sometimes we use the number 0 to symbolize null, O is a specific number and can be a real value. 1-8-1-8- 12 Figure 1.29: Graphical representation of an integer linked list The nodes in a list do not have names. What you know about the node is the address (memory location) at which it is stored. To access any node of the list, you only need to know the address of the first node. Then you follow the chain of nodes to reach the node you need. وزارة التعليم Ministry of Education 44 2024-1446

For example, if you want to access the third node of the list, to process the data it contains, you have to start from the first node of the list. From the first node you access the second, and from the second you reach the third. • The address of the first node is stored in a special (independent) variable that is usually called the head. • The pointer of the last node of the list is null and is represented with the symbol .. • When the list is empty, the head pointer points to a null value. Head 15 25 30 Null First Node Second Node Third Node Figure 1.30: Access the third node of the linked list Let's look at the graphic example of a linked list in figure 1.31. As mentioned above, each node consists of data and a pointer pointing to the next node. Each node is also stored in memory at a specific address. Specific node example: • The node data is number 15. • The address of the node in memory is 10. • The next node will be at address 20. Let's connect the previous node with the next node with data value 42, which in turn points to the third and last node at address 30 with data value 37. 10 15 20 Address/Head Data Next Address 15 20 42 30 37 Figure 1.31: Pointers in a linked list Table 1.8: Differences between lists and linked lists Differences List Linked List Memory storage method Contiguous locations in the memory. Random locations in the memory. Structure Size Each element can be accessed by Its elements can be accessed through the the index number. pointer. Each element is stored one after the Elements are stored as nodes containing other. the data and the address of the next element. Memory usage Only data is stored in memory. Data and pointers are stored in memory. Data access type Random access to any list element. Sequential access to elements. The speed of addition and Adding and removing elements is slower. Faster addition and removal. removal وزارة التعليم Ministry of Education 2024-1446 45

Linked List in Python Python does not provide a predefined data type for linked lists. You have to create your own data type or use additional python libraries that provide a representation of this data type. To create a linked list, you can use Python classes. In the following example, illustrated in figure 1.32, you will create a linked list with three nodes, each containing a day of the week. Monday Tuesday Wednesday • Class A class is a user defined data structure that holds its own data members (properties) and methods (behavior). Classes are used as a template for creating objects. Figure 1.32: Linked list example You will first create a node using Class. # single node class Node: def __init__(self, data, next=None): self.data = data # node data self.next = next # Pointer to the next node # Create a single node first Node("Monday") print (first.data) Monday The next step is to create a single-node linked list, this time you will use the head pointer to point to the first node. # single node class Node: def __init__(self, data = None, next=None): self.data = data self.next = next #linked list with one head node class LinkedList: def __init__(self): self.head = None #list linked with a single node Linkedlist1 = LinkedList() Linkedlist1.head = Node("Monday") print(Linkedlist1.head.data) Monday وزارة التعليم Ministry of Education 46 2024-1446

Now add more nodes to your linked list. # single node class Node: def __init__(self, data = None, next=None): self.data = data self.next = next # an empty linked list with a head node class LinkedList: def __init__(self): self.head = None #the main program linked list = LinkedList() linked_list # the first node linked_list.head = Node("Monday") # the second node linked_list.head.next = Node("Tuesday") # the third node linked list.head.next.next = Node("Wednesday") #print the linked list node = linked_list.head while node: print (node.data) node = node.next Monday Tuesday Wednesday Add a Node to a Linked List The actions required to add the new node are: The while statement is used to move from one node to another. • The pointer of the first node must point to the address of the new node, so that the new node becomes the second node. • The pointer of the new (second) node must point to the address of the third node. In this way, you do not have to shift the elements if a new element is added in the middle. The process is limited to changing the address values in the node, that makes the addition faster in the case of linked lists compared to sequential lists. 12 node 1. Create the new node. 37 1 99 node.next 3--> 2- 12 37 99 node node.next node.next.next Example: You have a linked list of two elements: 12, 99. You want to insert the element 37 as a second element. In the end, you will have a pildist of three elements: 12, 37, 99. Ministry of Education 2. Link the 37 node to the 99 node. 3. Link the 12 node to the 37 (new node created). 2024-1446 47

# single node class Node: def __init__(self, data = None, next=None): self.data = data self.next = next # linked list with one head node class LinkedList: def __init__(self): self.head = None def insertAfter(new, prev): # create the new node new_node = Node(new) # make the next of the new node the same as the next of the previous node new_node.next = prev.next # make the next of the previous node the new node = prev.next new_node # create the linked list L_list LinkedList() = # add the first two nodes L_list.head = Node(12) second = Node(99) L_list.head.next = second # insert the new node after node 12 (the head of the list) insertAfter(37, L_list.head) #print the linked list node =L_list.head while node: print (node.data) node node.next = 12 37 99 Delete a Node from a Linked List To delete a node, you must change the pointer of its predecessor to point to the node following the deleted node. The deleted (second) node is "useless data" and the memory space it occupies is allocated for other uses. Example: 12 37 99 node node.next node.next.next 1. Link the 12 node pointer to 99 node. 2. Delete node 37 1 12 99 node node.next 2 37 node.next 3. Final result 12 99 3 You have a linked list of three elements: 12, 37, 99. You want to delete the element 37. In the end, you will have a list of two elements: 12, 99. node node.next Ministry of Education 48 2024-1446

# single node class Node: def __init__(self, data = None, next=None): self.data = : data self.next = next # linked list with one head node class LinkedList: def __init__(self): self.head = None def deleteNode(key, follow): # store the head node temp = follow.head #find the key to be deleted, # the trace of the previous node to be changed while(temp is not None): if temp.data == key: break If you want to delete the first node of a linked list, you must move the head to the second node of the list. prev = temp temp = temp.next #unlink the node from the linked list prev.next temp.next temp = = None # create the linked list L_list = LinkedList() # add the first three nodes L_list.head = Node(12) second = Node(37) third Node (99) L_list.head.next = second second.next # delete node 37 = third deleteNode(37,L_list) # print the linked list node =L_list.head while node: print (node.data) node = node.next وزارة التعليم Ministry of Education 2024-1446 12 99 49

Exercises 1 Read the sentences and tick ✔ True or False. 2 1. Python defines non-Primitive Data Structures. 2. Linear Data Structures store data items exclusively in random order. 3. Adding and removing items in a linked list is slower than a list. 4. The items in a list can only be accessed through their index number. 5. The size of a static data structure can be modified during the execution of a program. True False State the differences between static and dynamic data structures. Static data structures Dynamic data structures 3 Write two examples of uses for linked lists. وزارة التعليم Ministry of Education 50 2024-1446

4 You have a stack with six empty spaces. • You will add the following letters C, E, B, A and D in positions 0 to 4. 5 Stack Final Output 5 • Fill the stack indicating the position of the top pointer. 4 4 • Execute the following operations: pop pop → push X → push K pop Show the final output after performing the above operations, indicating the position of the top pointer. Write a program that creates the stack shown above, and then perform the above operations using the standard queue library. 5 You have the following number sequence: 4, 8, 2, 5, 9, 13. 3 3 2 2 1 1 0 0 • What is the process used to add the above elements into the queue? Complete the queue after adding the elements. 0 1 2 3 4 5 • What is the process used to remove elements from the queue? • How many times should the above operation be performed to remove the element with value 5? وزارة التعليم Ministry of Education 2024-1446 Write Python code to create the previous queue. 51

6 7 Given the following nodes, draw the linked list and then write the values in the list in the correct order. Head = 3 9 2 0 4 1 5 -3 Create a list with the following numbers: 5, 20, 45, 8, 1. • Draw the nodes of the linked list. • Describe the process of adding the number 7 after the number 45. • Draw the new list. • Describe the process required to delete the second node of the list. . Draw the final linked list. وزارة التعليم Ministry of Education 52 ZU24-1446