SlideShare a Scribd company logo

05 ds and algorithm session_07

Niit Care
Niit Care

The document discusses implementing a singly-linked list to store prime numbers between 1 and 10,00,000. It explains that a linked list allows dynamic memory allocation as nodes are added, with each node containing a data field and link to the next node. To insert a new prime number, a node is allocated, its data field is set, and it is added to the end of the linked list by making the current last node's next pointer point to the new node. This allows storing an unknown number of prime numbers without predefined array size limits.

1 of 194
Data Structures and Algorithms Objectives In this session, you will learn to: Identify the features of linked lists Implement a singly-linked list Ver. 1.0 Session 7
Data Structures and Algorithms Linked List Suppose you have to write an algorithm to generate and store all prime numbers between 1 and 10,00,000 and display them. How will you solve this problem? Ver. 1.0 Session 7
Data Structures and Algorithms Linked List (Contd.) Consider the following algorithm, which uses an array to solve this problem: 1. Set I = 0 2. Repeat step 3 varying N from 2 to 1000000 3. If N is a prime number a. Set A[I] = N // If N is prime store it in an array b. I = I + 1 • Repeat step 5 varying J from 0 to I-1 • Display A[J] // Display the prime numbers // stored in the array Ver. 1.0 Session 7
Data Structures and Algorithms Linked List (Contd.) What is the problem in this algorithm? The number of prime numbers between 1 and 10,00,000 is not known. Since you are using an array to store the prime numbers, you need to declare an array of arbitrarily large size to store the prime numbers. Disadvantages of this approach, suppose you declare an array of size N: If the number of prime numbers between 1 and 10,00,000 is more than N then all the prime numbers cannot be stored. If the number of prime numbers is much less than N, a lot of memory space is wasted. Ver. 1.0 Session 7
Data Structures and Algorithms Linked List (Contd.) • Thus, you cannot use an array to store a set of elements if you do not know the total number of elements in advance. • How do you solve this problem? By having some way in which you can allocate memory as and when it is required. Ver. 1.0 Session 7
Data Structures and Algorithms Dynamic Memory Allocation • If you knowdeclare an array, a contiguous block ofarray you When you the address of the first element in the memory can calculate the address of any other elements as shown: is allocated. Let Address of theyou declare an array of size 10 to store first us suppose first element + (size of the element × index of the element) 10 prime numbers. 0 1000 1 1002 2 1004 One contiguous block of 3 1006 4 1008 memory allocated for 5 1010 the array to store 10 6 1012 7 1014 elements. 8 1016 9 1018 Memory representation Ver. 1.0 Session 7
Data Structures and Algorithms Dynamic Memory Allocation (Contd.) When memory is allocated dynamically, a block of memory is assigned arbitrarily from any location in the memory. Therefore, unlike arrays, these blocks may not be contiguous and may be spread randomly in the memory. 0 1000 1 1002 2 1004 One contiguous block of 3 1006 4 1008 memory allocated for 5 1010 the array to store 10 6 1012 7 1014 elements. 8 1016 9 1018 Memory representation Ver. 1.0 Session 7
Data Structures and Algorithms Dynamic Memory Allocation (Contd.) Let us see how this happens by allocating memory dynamically for the prime numbers. Allocate memory for 2 1002 2 Memory allocated for 2 Memory representation Ver. 1.0 Session 7
Data Structures and Algorithms Dynamic Memory Allocation (Contd.) Let us see how this happens. Allocate memory for 3 1002 2 Memory allocated for 3 1036 3 Memory representation Ver. 1.0 Session 7
Data Structures and Algorithms Dynamic Memory Allocation (Contd.) Let us see how this happens. Allocate memory for 5 1002 2 Memory allocated for 5 1008 5 1036 3 Memory representation Ver. 1.0 Session 7
Data Structures and Algorithms Dynamic Memory Allocation (Contd.) Let us see how this happens. Allocate memory for 7 1002 2 Memory allocated for 7 1008 5 1020 7 1036 3 Memory representation Ver. 1.0 Session 7
Data Structures and Algorithms Dynamic Memory Allocation (Contd.) Let us see how this happens. Allocate memory for 11 1002 2 Memory allocated for 11 1008 5 1020 7 1030 11 1036 3 Memory representation Ver. 1.0 Session 7
Data Structures and Algorithms Dynamic Memory Allocation (Contd.) To access know the address of the know its address. Now, if youany element, you need to first element, you cannot calculate the address of the rest of the elements. This is because, all the elements are spread at random locations in the memory. 1002 2 1008 5 1020 7 1030 11 1036 3 Memory representation Ver. 1.0 Session 7
Data Structures and Algorithms Dynamic Memory Allocation (Contd.) Therefore, it would be good if every allocated block of memory contains the address of the next block in sequence. This gives the list a linked structure where each block is linked to the next block in sequence. 1002 2 1036 1008 5 1020 1020 7 1030 1030 11 1036 3 1008 Memory representation Ver. 1.0 Session 7
Data Structures and Algorithms Dynamic Memory Allocation (Contd.) An example of a a variable, START, that stores this concept You can declare data structure that implements the address is the first list. of a linked block. You can now begin at START and move through the list by following the links. START 2 1036 1002 1008 5 1020 1020 7 1030 1030 11 1036 3 1008 Memory representation Ver. 1.0 Session 7
Data Structures and Algorithms Defining Linked Lists Linked list: Is a dynamic data structure. Allows memory to be allocated as and when it is required. Consists of a chain of elements, in which each element is referred to as a node. Ver. 1.0 Session 7
Data Structures and Algorithms Defining Linked Lists (Contd.) A node is the basic building block of a linked list. A node consists of two parts: – Data: Refers to the information held by the node – Link: Holds the address of the next node in the list Data Link Node Ver. 1.0 Session 7
Data Structures and Algorithms Defining Linked Lists (Contd.) The last node in a linked list does not point to any other All the nodes in a linked list are present at arbitrary memory node. Therefore, it points to NULL. locations. Therefore, every node in a linked list has link field that stores the address of the next node in sequence. NULL 10 Data 3352 10 Data 5689 10 Data 1012 10 Data 2403 3352 5689 1012 Ver. 1.0 Session 7
Data Structures and Algorithms Defining Linked Lists (Contd.) To keep track of the first node, declare a variable/pointer, START, which always points to the first node. When the list is empty, START contains null. NULL START 10 Data 3352 10 Data 5689 10 Data 1012 10 Data 2403 3352 5689 1012 Ver. 1.0 Session 7
Data Structures and Algorithms Implementing a Singly-Linked List Let us solve the given problem of storing prime numbers using a linked list. 1. Repeat step 2 varying N from 2 to 1000000. 2. If N is a prime number, insert it in the linked list: a. Allocate memory for a new node. b. Store the prime number in the new node. c. Attach the new node in the linked list. 3. Display the prime numbers stored in the linked list. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List • Consider the following linked list that stores prime numbers. START 2 3 5 7 • When a new prime number is generated, it should be inserted at the end of the list. • Initially, when the list is empty, START contains NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. Consider the given algorithm to 3. Assign value to the data field of the new node. insert a node in a linked list. 5. If START is NULL, then: a. Make START point to the new node. b. Go to step 6. 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the following steps: a. Mark the first node as currentNode. b. Repeat step c until the successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. START = that the list is initially Consider NULL 3. Assign value to the data field of the new node. empty. Insert a prime number 2. 5. If START is NULL, then: a. Make START point to the new node. b. Go to step 6. 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the following steps: a. Mark the first node as currentNode. b. Repeat step c until the successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. START = NULL • Assign value to the data field of the new node. Insert a prime number 2. • If START is NULL, then: a. Make START point to the new node. b. Go to step 6. 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the following steps: a. Mark the first node as currentNode. b. Repeat step c until the successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. START = NULL • Assign value to the data field of the new node. • If START is NULL, then: a. Make START point to the new node. b. Go to step 6. 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 following steps: a. Mark the first node as currentNode. b. Repeat step c until the successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. START = NULL • Assign value to the data field of the new node. • If START is NULL, then: a. Make START point to the new node. b. Go to step 6. 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 following steps: a. Mark the first node as currentNode. b. Repeat step c until the successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. START = NULL 3. Assign value to the data field of the new node. 5. If START is NULL, then: • Make START point to the new node. • Go to step 6. START 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 following steps: a. Mark the first node as currentNode. b. Repeat step c until the successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then: • Make START point to the new node. • Go to step 6. START • Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 following steps: a. Mark the first node as currentNode. b. Repeat step c until the successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then: a. Make START point to the new node. b. Go to step 6. START 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 following steps: a. Mark the first node as currentNode. b. Repeat step c until the successor of currentNode Insertion complete becomes NULL. c. Make currentNode point to the next node in sequence. • Make the next field of currentNode point to the new node. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. Insert a prime number 3. 3. Assign value to the data field of the new node. 5. If START is NULL, then: a. Make START point to the new node. b. Go to step 6. START 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 following steps: a. Mark the first node as currentNode. b. Repeat step c until the successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. • Insert a prime number 3. • Assign value to the data field of the new node. • If START is NULL, then: a. Make START point to the new node. b. Go to step 6. START 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 following steps: a. Mark the first node as currentNode. b. Repeat step c until the successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. • Assign value to the data field of the new node. • If START is NULL, then: a. Make START point to the new node. b. Go to step 6. START 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 3 10 following steps: a. Mark the first node as currentNode. b. Repeat step c until the successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. • Assign value to the data field of the new node. • If START is NULL, then: a. Make START point to the new node. b. Go to step 6. START 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 3 10 following steps: a. Mark the first node as currentNode. b. Repeat step c until the successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then: a. Make START point to the new node. b. Go to step 6. START • Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 3 10 following steps: a. Mark the first node as currentNode. b. Repeat step c until the successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then: a. Make START point to the new node. b. Go to step 6. START 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 3 10 following steps: • Mark the first node as currentNode. • Repeat step c until the currentNode successor of currentNode becomes NULL. • Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then: a. Make START point to the new node. b. Go to step 6. START 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 3 10 following steps: • Mark the first node as currentNode. • Repeat step c until the currentNode successor of currentNode becomes NULL. • Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then: a. Make START point to the new node. b. Go to step 6. START 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 3 10 following steps: a. Mark the first node as currentNode. b. Repeat step c until the currentNode successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. • Make the next field of currentNode point to the new node. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then: a. Make START point to the new node. b. Go to step 6. START 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 3 10 following steps: a. Mark the first node as currentNode. b. Repeat step c until the currentNode successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. Insertion complete • Make the next field of currentNode point to the new node. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. • Insert a prime number 5. 3. Assign value to the data field of the new node. 5. If START is NULL, then: a. Make START point to the new node. b. Go to step 6. START 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 3 10 following steps: a. Mark the first node as currentNode. b. Repeat step c until the currentNode successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. Insert a prime number 5. • Assign value to the data field of the new node. • If START is NULL, then: a. Make START point to the new node. b. Go to step 6. START 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 3 10 following steps: a. Mark the first node as currentNode. b. Repeat step c until the successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. • Assign value to the data field of the new node. • If START is NULL, then: a. Make START point to the new node. b. Go to step 6. START 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 3 10 5 10 following steps: a. Mark the first node as currentNode. b. Repeat step c until the successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. • Assign value to the data field of the new node. • If START is NULL, then: a. Make START point to the new node. b. Go to step 6. START 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 3 10 5 10 following steps: a. Mark the first node as currentNode. b. Repeat step c until the successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then: a. Make START point to the new node. b. Go to step 6. START • Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 3 10 5 10 following steps: a. Mark the first node as currentNode. b. Repeat step c until the successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then: a. Make START point to the new node. b. Go to step 6. START 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 3 10 5 10 following steps: • Mark the first node as currentNode. • Repeat step c until the currentNode successor of currentNode becomes NULL. • Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then: a. Make START point to the new node. b. Go to step 6. START 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 3 10 5 10 following steps: • Mark the first node as currentNode. • Repeat step c until the currentNode successor of currentNode becomes NULL. • Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then: a. Make START point to the new node. b. Go to step 6. START 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 3 10 5 10 following steps: • Mark the first node as currentNode. • Repeat step c until the currentNodecurrentNode successor of currentNode becomes NULL. • Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then: a. Make START point to the new node. b. Go to step 6. START 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 3 10 5 10 following steps: a. Mark the first node as currentNode. b. Repeat step c until the currentNode successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. • Make the next field of currentNode point to the new node. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then: a. Make START point to the new node. b. Go to step 6. START 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 3 10 5 10 following steps: a. Mark the first node as currentNode. b. Repeat step c until the currentNode successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. Insertion complete • Make the next field of currentNode point to the new node. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. What is thea better approach is to Therefore, problem with this 3. Assign value to the data field of the new node. algorithm?variable, LAST, which declare a 5. If START is NULL, then: will Consider a address of the last store the list of 10000 numbers. a. Make START point to the node in the a number at the end of To insert list. new node. b. Go to step 6. the list, you first need to locate the Hence, you need to maintain two 7. Locate the last node in the list, and variables, STARTlist. LAST, to last node in the and mark it as currentNode. To locate To reach the last node, you have keep track of the first and last the last node in the list, execute the following steps: to start from the first node and nodes in the list respectively. a. Mark the first node as visit all the preceding nodes currentNode. If the list is empty, START node. before you reach the last and b. Repeat step c until the successor of currentNode LAST point to NULL. becomes NULL. This approach is very time c. Make currentNode point to consuming for lengthy lists. the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. Refer to the given algorithm to 3. Assign value to the data field of the new node. insert a node at the end of the 5. If START is NULL, then (If the list is linked list. empty): a. Make START point to the new node. b. Make LAST point to the new node. c. Go to step 6. • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. START = NULL Consider that the list is initially 3. Assign value to the data field of the new node. empty. NULL LAST = 5. If START is NULL, then (If the list is Insert a prime number 2. empty): a. Make START point to the new node. b. Make LAST point to the new node. c. Go to step 6. • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. START = NULL • Assign value to the data field of the new node. LAST = NULL • If START is NULL, then (If the list is Insert a prime number 2. empty): a. Make START point to the new node. b. Make LAST point to the new node. c. Go to step 6. • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. START = NULL • Assign value to the data field of the new node. LAST = NULL • If START is NULL, then (If the list is empty): a. Make START point to the new node. b. Make LAST point to the new node. c. Go to step 6. 2 10 • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. START = NULL • Assign value to the data field of the new node. LAST = NULL • If START is NULL, then (If the list is empty): a. Make START point to the new node. b. Make LAST point to the new node. c. Go to step 6. 2 10 • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. START = NULL 3. Assign value to the data field of the new node. LAST = NULL 5. If START is NULL, then (If the list is empty): • Make START point to the new node. START • Make LAST point to the new node. • Go to step 6. 2 10 • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. LAST = NULL 5. If START is NULL, then (If the list is empty): • Make START point to the new node. START LAST • Make LAST point to the new node. • Go to step 6. 2 10 • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then (If the list is empty): • Make START point to the new node. START LAST • Make LAST point to the new node. • Go to step 6. 2 10 • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then (If the list is empty): a. Make START point to the new node. START LAST b. Make LAST point to the new node. c. Go to step 6. 2 10 • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node Insertion complete point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. Insert a prime number 3. 3. Assign value to the data field of the new node. 5. If START is NULL, then (If the list is empty): a. Make START point to the new node. START LAST b. Make LAST point to the new node. c. Go to step 6. 2 10 • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. Insert a prime number 3. • Assign value to the data field of the new node. • If START is NULL, then (If the list is empty): a. Make START point to the new node. START LAST b. Make LAST point to the new node. c. Go to step 6. 2 10 • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. • Assign value to the data field of the new node. • If START is NULL, then (If the list is empty): a. Make START point to the new node. START LAST b. Make LAST point to the new node. c. Go to step 6. 2 10 3 10 • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. • Assign value to the data field of the new node. • If START is NULL, then (If the list is empty): a. Make START point to the new node. START LAST b. Make LAST point to the new node. c. Go to step 6. 2 10 3 10 • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then (If the list is empty): a. Make START point to the new node. START LAST b. Make LAST point to the new node. c. Go to step 6. 2 10 3 10 • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then (If the list is empty): a. Make START point to the new node. START LAST LAST b. Make LAST point to the new node. c. Go to step 6. 2 10 3 10 • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then (If the list is empty): a. Make START point to the new node. START LAST b. Make LAST point to the new node. c. Go to step 6. 2 10 3 10 • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node Insertion complete point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. Insert a prime number 5. 3. Assign value to the data field of the new node. 5. If START is NULL, then (If the list is empty): a. Make START point to the new node. START LAST b. Make LAST point to the new node. c. Go to step 6. 2 10 3 10 • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. Insert a prime number 5. • Assign value to the data field of the new node. • If START is NULL, then (If the list is empty): a. Make START point to the new node. START LAST b. Make LAST point to the new node. c. Go to step 6. 2 10 3 10 • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. • Assign value to the data field of the new node. • If START is NULL, then (If the list is empty): a. Make START point to the new node. START LAST b. Make LAST point to the new node. c. Go to step 6. 2 10 3 10 5 10 • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. • Assign value to the data field of the new node. • If START is NULL, then (If the list is empty): a. Make START point to the new node. START LAST b. Make LAST point to the new node. c. Go to step 6. 2 10 3 10 5 10 • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then (If the list is empty): a. Make START point to the new node. START LAST b. Make LAST point to the new node. c. Go to step 6. 2 10 3 10 5 10 • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then (If the list is empty): a. Make START point to the new node. START LAST LAST b. Make LAST point to the new node. c. Go to step 6. 2 10 3 10 5 10 • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then (If the list is empty): a. Make START point to the new node. START LAST b. Make LAST point to the new node. c. Go to step 6. 2 10 3 10 5 10 • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node Insertion complete point to NULL. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) Now consider another problem. Suppose you have to store the marks of 20 students in the ascending order. How will you solve this problem? Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) Consider the following algorithm, which uses an array to solve this problem. 1. Set N = 0 // Number of marks entered 2. Repeat until N = 20 a. Accept marks. b. Locate position I where the marks must be inserted. c. For J = N – 1 down to I Move A[J] to A[J+1] // Move elements to make // place for the new element d. Set A[I] = marks e. N = N + 1 Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 Let us perform some insert 2. Repeat until N = 20 • Accept marks. operations in the array by placing the • Locate position I where elements at their appropriate the marks must be inserted positions to get a sorted list. • For J = N-1 down to I Move A[J] to A[J+1] d. Set A[I] = marks e. N=N+1 0 1 2 3 4… …19 Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Set N = 0 Let us perform some insert operations • Repeat until N = 20 • Accept marks in the array by placing the elements at • Locate position I where their appropriate positions to get a the marks must be inserted sorted list. • For J = N-1 down to I Move A[J] to A[J+1] d. Set A[I] = marks e. N=N+1 10 0 1 2 3 4… …19 N=0 Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Set N = 0 • Repeat until N = 20 a. Accept marks b. Locate position I where the marks must be inserted c. For J = N-1 down to I Move A[J] to A[J+1] d. Set A[I] = marks e. N=N+1 10 0 1 2 3 4… …19 N=0 Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 10 • Accept marks • Locate position I where the marks must be inserted • For J = N-1 down to I Move A[J] to A[J+1] d. Set A[I] = marks e. N=N+1 10 0 1 2 3 4… …19 N=0 Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 10 • Accept marks • Locate position I where I=0 the marks must be inserted • For J = N-1 down to I Move A[J] to A[J+1] I d. Set A[I] = marks e. N=N+1 10 0 1 2 3 4… …19 N=0 Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 10 • Accept marks • Locate position I where I=0 the marks must be inserted • For J = N-1 down to I Move A[J] to A[J+1] I d. Set A[I] = marks e. N=N+1 10 0 1 2 3 4… …19 N=0 Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 10 • Accept marks • Locate position I where I=0 the marks must be inserted • For J = N-1 down to I Move A[J] to A[J+1] I • Set A[I] = marks • N=N+1 10 10 0 1 2 3 4… …19 N=0 Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 • Accept marks • Locate position I where I=0 the marks must be inserted • For J = N-1 down to I Move A[J] to A[J+1] I • Set A[I] = marks • N=N+1 10 10 0 1 2 3 4… …19 N=0 Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 • Accept marks • Locate position I where I=0 the marks must be inserted • For J = N-1 down to I Move A[J] to A[J+1] I • Set A[I] = marks • N=N+1 10 10 0 1 2 3 4… …19 N=1 Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 20 • Accept marks • Locate position I where I=0 the marks must be inserted • For J = N-1 down to I Move A[J] to A[J+1] I d. Set A[I] = marks e. N=N+1 10 10 0 1 2 3 4… …19 N=1 Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 20 • Accept marks • Locate position I where 0 I=1 the marks must be inserted • For J = N-1 down to I Move A[J] to A[J+1] I I d. Set A[I] = marks e. N=N+1 10 10 0 1 2 3 4… …19 N=1 Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 20 • Accept marks • Locate position I where I=1 the marks must be inserted • For J = N-1 down to I Move A[J] to A[J+1] I d. Set A[I] = marks e. N=N+1 10 10 0 1 2 3 4… …19 N=1 Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 20 • Accept marks • Locate position I where I=1 the marks must be inserted • For J = N-1 down to I Move A[J] to A[J+1] I • Set A[I] = marks • N=N+1 10 20 10 0 1 2 3 4… …19 N=1 Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 • Accept marks • Locate position I where I=1 the marks must be inserted • For J = N-1 down to I Move A[J] to A[J+1] I • Set A[I] = marks • N=N+1 10 20 10 0 1 2 3 4… …19 N=1 Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 • Accept marks • Locate position I where I=1 the marks must be inserted • For J = N-1 down to I Move A[J] to A[J+1] I • Set A[I] = marks • N=N+1 10 20 10 0 1 2 3 4… …19 N=2 Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 17 • Accept marks • Locate position I where I=1 the marks must be inserted • For J = N-1 down to I Move A[J] to A[J+1] I d. Set A[I] = marks e. N=N+1 10 20 10 0 1 2 3 4… …19 N=2 Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 17 • Accept marks • Locate position I where I=1 the marks must be inserted • For J = N-1 down to I I Move A[J] to A[J+1] d. Set A[I] = marks e. N=N+1 10 20 10 0 1 2 3 4… …19 N=2 Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 17 • Accept marks • Locate position I where I=1 the marks must be inserted J=1 • For J = N-1 down to I I Move A[J] to A[J+1] d. Set A[I] = marks e. N=N+1 10 20 10 0 1 2 3 4… …19 N=2 Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 17 • Accept marks • Locate position I where I=1 the marks must be inserted J=1 • For J = N-1 down to I I Move A[J] to A[J+1] d. Set A[I] = marks e. N=N+1 10 20 10 0 1 2 3 4… …19 N=2 Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 17 a. Accept marks b. Locate position I where I=1 the marks must be inserted J=1 c. For J = N-1 down to I I Move A[J] to A[J+1] d. Set A[I] = marks e. N=N+1 10 20 10 20 0 1 2 3 4… …19 N=2 Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 17 a. Accept marks b. Locate position I where I=1 the marks must be inserted J=1 c. For J = N-1 down to I I Move A[J] to A[J+1] • Set A[I] = marks • N=N+1 10 17 10 20 0 1 2 3 4… …19 N=2 Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 a. Accept marks b. Locate position I where I=1 the marks must be inserted c. For J = N-1 down to I I Move A[J] to A[J+1] • Set A[I] = marks • N=N+1 10 17 10 20 0 1 2 3 4… …19 N=3 Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 15 • Accept marks • Locate position I where the marks must be inserted • For J = N-1 down to I Move A[J] to A[J+1] d. Set A[I] = marks e. N=N+1 10 17 10 20 0 1 2 3 4… …19 N=3 Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 15 • Accept marks • Locate position I where I=1 the marks must be inserted • For J = N-1 down to I I Move A[J] to A[J+1] d. Set A[I] = marks e. N=N+1 10 17 10 20 0 1 2 3 4… …19 N=3 Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 15 • Accept marks • Locate position I where I=1 the marks must be inserted J=2 • For J = N-1 down to I I Move A[J] to A[J+1] d. Set A[I] = marks e. N=N+1 10 17 10 20 0 1 2 3 4… …19 N=3 Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 15 a. Accept marks b. Locate position I where I=1 the marks must be inserted J=2 c. For J = N-1 down to I I Move A[J] to A[J+1] d. Set A[I] = marks e. N=N+1 10 17 10 20 0 1 2 3 4… …19 N=3 Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 15 a. Accept marks b. Locate position I where I=1 the marks must be inserted J=2 c. For J = N-1 down to I I Move A[J] to A[J+1] d. Set A[I] = marks e. N=N+1 10 17 10 20 20 0 1 2 3 4… …19 N=3 Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 15 • Accept marks • Locate position I where I=1 the marks must be inserted J=1 • For J = N-1 down to I I Move A[J] to A[J+1] d. Set A[I] = marks e. N=N+1 10 17 10 20 0 1 2 3 4… …19 N=3 Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 15 a. Accept marks b. Locate position I where I=1 the marks must be inserted J=1 c. For J = N-1 down to I I Move A[J] to A[J+1] d. Set A[I] = marks e. N=N+1 10 17 10 20 0 1 2 3 4… …19 N=3 Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 15 a. Accept marks b. Locate position I where I=1 the marks must be inserted J=1 c. For J = N-1 down to I I Move A[J] to A[J+1] d. Set A[I] = marks e. N=N+1 10 17 10 17 20 0 1 2 3 4… …19 N=3 Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 15 a. Accept marks b. Locate position I where I=1 the marks must be inserted J=1 c. For J = N-1 down to I I Move A[J] to A[J+1] • Set A[I] = marks • N=N+1 10 15 10 17 20 0 1 2 3 4… …19 N=3 Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 a. Accept marks b. Locate position I where I=1 the marks must be inserted J=1 c. For J = N-1 down to I I Move A[J] to A[J+1] • Set A[I] = marks • N=N+1 10 15 10 17 20 0 1 2 3 4… …19 N=4 Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) What the preceding example we conclude that insertion and From is the problem in this algorithm? deletion at any element at any position other thanan arrayof the To insert an position other than the end of the end is complex and inefficient. overhead of shifting all succeeding list, there is an additional How can you overcome forward. elements one position this limitation? By using a data structure that does not requireother than the Similarly, to delete an element at any position shifting of data elements after you need to shift the operation. elements one end of the list, every insert / delete succeeding position backwards. A linked list offers this flexibility. When the list is very large, this would be very time consuming. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) Consider a linked list that stores the marks of students in an ascending order. Insert marks (17). 17 should be inserted after 15. 20 1002 10 1011 START 25 1020 15 2496 10 2496 15 1002 20 1020 25 NULL Memory representation Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) Allocate memory for 17. 20 1002 10 1011 Memory allocated for 17 17 1008 17 START 25 1020 15 2496 10 2496 15 1002 20 1020 25 NULL 10 10 10 10 Memory representation Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) In the given list, node 15 contains the address of node 20. To add node 17 after node 15, you need to update the address field of node 15 so that it now contains the address of node 17. 20 1002 10 1011 Memory allocated for 17 17 1008 17 START 25 1020 15 2496 10 2496 15 1002 20 1020 25 NULL 10 10 10 10 Memory representation Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) Update the address field of node 15 to store the address of node 17. 20 1002 10 1011 17 1008 17 START 25 1020 17 15 2496 10 2496 15 1002 20 1020 25 NULL 10 10 10 10 Memory representation Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) Update the address field of node 15 to store the address of node 17. 20 1002 10 1011 17 1008 START 25 1020 17 15 2496 10 2496 1008 15 1002 20 1020 25 NULL 10 10 10 10 Updating the address field Memory representation Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) Store the address of node 20 in the address field of node 17 to make a complete list. 20 1002 10 1011 Node Inserted 17 1008 START 25 1020 17 1002 15 2496 10 2496 15 1008 20 1020 10 25 NULL 10 10 Address updated Memory representation Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) Now, let us solve the given problem using a linked list. Suppose the linked list currently contains the following elements. START 10 15 17 20 The linked list needs to be created in the ascending order of values. Therefore, the position of a new node in the list will be determined by the value contained in the new node. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) Write an algorithm to locate the position of the new node to be inserted in a linked list, where the nodes need to be stored in the increasing order of the values contained in them. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Make current point to the first node. Algorithm for locating the position 2. Make previous point to NULL. of a new node in the linked list. 3. Repeat step 4 and step 5 until current.info becomes greater than the After executing this algorithm the newnode.info or current becomes equal to NULL. variables/pointers previous and 4. Make previous point to current. current will be placed on the 5. Make current point to the next node in nodes between which the new sequence. node is to be inserted. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Make current point to the first node. Insert 16 in the given list. 2. Make previous point to NULL. 3. Repeat step 4 and step 5 until current.info becomes greater than the newnode.info or current becomes equal to NULL. 4. Make previous point to current. 5. Make current point to the next node in START sequence. 10 15 17 20 Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Make current point to the first node. Insert 16 in the given list. • Make previous point to NULL. • Repeat step 4 and step 5 until current.info becomes greater than the newnode.info or current becomes equal to NULL. • Make previous point to current. • Make current point to the next node in START sequence. 10 10 15 17 20 current Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Make current point to the first node. • Make previous point to NULL. • Repeat step 4 and step 5 until current.info becomes greater than the newnode.info or current becomes equal to NULL. • Make previous point to current. • Make current point to the next node in START sequence. 10 10 15 17 20 current previous = NULL Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Make current point to the first node. • Make previous point to NULL. • Repeat step 4 and step 5 until current.info becomes greater than the newnode.info or current becomes equal to NULL. • Make previous point to current. • Make current point to the next node in START sequence. 10 10 15 17 20 current previous = NULL Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Make current point to the first node. • Make previous point to NULL. • Repeat step 4 and step 5 until current.info becomes greater than the newnode.info or current becomes equal to NULL. • Make previous point to current. • Make current point to the next node in START sequence. 10 10 15 17 20 previous current previous = NULL Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Make current point to the first node. • Make previous point to NULL. • Repeat step 4 and step 5 until current.info becomes greater than the newnode.info or current becomes equal to NULL. • Make previous point to current. • Make current point to the next node in START sequence. 10 10 15 17 20 previous current current Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Make current point to the first node. • Make previous point to NULL. • Repeat step 4 and step 5 until current.info becomes greater than the newnode.info or current becomes equal to NULL. • Make previous point to current. • Make current point to the next node in START sequence. 10 10 15 17 20 previous current Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Make current point to the first node. • Make previous point to NULL. • Repeat step 4 and step 5 until current.info becomes greater than the newnode.info or current becomes equal to NULL. • Make previous point to current. • Make current point to the next node in START sequence. 10 10 15 17 20 previous previous current Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Make current point to the first node. • Make previous point to NULL. • Repeat step 4 and step 5 until current.info becomes greater than the newnode.info or current becomes equal to NULL. • Make previous point to current. • Make current point to the next node in START sequence. 10 10 15 17 20 previous current current Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Make current point to the first node. • Make previous point to NULL. • Repeat step 4 and step 5 until current.info becomes greater than the newnode.info or current becomes equal to NULL. • Make previous point to current. • Make current point to the next node in START sequence. 10 10 15 17 20 previous current Node located Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) Once the position of the new node has been determined, the new node can be inserted in the linked list. A new node can be inserted at any of the following positions in the list: Beginning of the list End of the list Between two nodes in the list Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) Write an algorithm to insert a node in the beginning of a linked list. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. Algorithm to insert a node in the 3. Assign value to the data field of beginning of a linked list the new node. 5. Make the next field of the new node point to the first node in the list. 7. Make START, point to the new START node. 10 15 17 20 Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. Insert 7 • Assign value to the data field of the new node. newnode • Make the next field of the new node point to the first node in the list. • Make START, point to the new START node. 10 10 15 17 20 Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. Insert 7 • Assign value to the data field of the new node. newnode • Make the next field of the new node point to the first node in the list. • Make START, point to the new 7 START node. 10 10 15 17 20 Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. • Assign value to the data field of the new node. newnode • Make the next field of the new node point to the first node in the list. • Make START, point to the new 7 START node. 10 10 15 17 20 newnode. next = START Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. • Assign value to the data field of the new node. newnode • Make the next field of the new node point to the first node in the list. • Make START, point to the new 7 START node. 10 10 15 17 20 Insertion complete newnode. next = START START = newnode Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) Write an algorithm to insert a node between two nodes in a linked list. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Identify the nodes between which the new node is to be inserted. Mark them Insert 16 Algorithm to insert a node between as previous and current. To locate previous and current, execute the two nodes in a linked list. following steps: a. Make current point to the first node. START b. Make previous point to NULL. c. Repeat step d and step e until current.info becomes greater than newnode.info or current 10 15 17 20 becomes equal to NULL. d. Make previous point to current. e. Make current point to the next node in sequence. 3. Allocate memory for the new node. 5. Assign value to the data field of the new node. 7. Make the next field of the new node point to current. 9. Make the next field of previous point to the new node. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Identify the nodes between which the new node is to be inserted. Mark them Insert 16 as previous and current. To locate previous and current, execute the following steps: a. Make current point to the first node. START b. Make previous point to NULL. c. Repeat step d and step e until current.info becomes greater than newnode.info or current 10 10 15 17 20 becomes equal to NULL. d. Make previous point to current. e. Make current point to the next node in sequence. 3. Allocate memory for the new node. 5. Assign value to the data field of the new node. 7. Make the next field of the new node point to current. 9. Make the next field of previous point to the new node. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Identify the nodes between which the new node is to be inserted. Mark them Insert 16 as previous and current. To locate previous and current, execute the following steps: • Make current point to the first node. START • Make previous point to NULL. • Repeat step d and step e until current.info becomes greater than newnode.info or current 10 10 15 17 20 becomes equal to NULL. • Make previous point to current. • Make current point to the next node in sequence. current 3. Allocate memory for the new node. 5. Assign value to the data field of the new node. 7. Make the next field of the new node point to current. 9. Make the next field of previous point to the new node. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Identify the nodes between which the new node is to be inserted. Mark them Insert 16 as previous and current. To locate previous and current, execute the following steps: • Make current point to the first node. START • Make previous point to NULL. • Repeat step d and step e until current.info becomes greater than newnode.info or current 10 10 15 17 20 becomes equal to NULL. • Make previous point to current. • Make current point to the next node in sequence. current 3. Allocate memory for the new node. previous = NULL 5. Assign value to the data field of the new node. 7. Make the next field of the new node point to current. 9. Make the next field of previous point to the new node. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Identify the nodes between which the new node is to be inserted. Mark them Insert 16 as previous and current. To locate previous and current, execute the following steps: • Make current point to the first node. START • Make previous point to NULL. • Repeat step d and step e until current.info becomes greater than newnode.info or current 10 10 15 17 20 becomes equal to NULL. • Make previous point to current. • Make current point to the next node in sequence. current 3. Allocate memory for the new node. previous = NULL 5. Assign value to the data field of the new node. 7. Make the next field of the new node point to current. 9. Make the next field of previous point to the new node. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Identify the nodes between which the new node is to be inserted. Mark them Insert 16 as previous and current. To locate previous and current, execute the following steps: • Make current point to the first node. START • Make previous point to NULL. • Repeat step d and step e until current.info becomes greater than newnode.info or current 10 10 15 17 20 becomes equal to NULL. • Make previous point to current. • Make current point to the next node in sequence. previous current 3. Allocate memory for the new node. previous = NULL 5. Assign value to the data field of the new node. 7. Make the next field of the new node point to current. 9. Make the next field of previous point to the new node. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Identify the nodes between which the new node is to be inserted. Mark them Insert 16 as previous and current. To locate previous and current, execute the following steps: • Make current point to the first node. START • Make previous point to NULL. • Repeat step d and step e until current.info becomes greater than newnode.info or current 10 10 15 17 20 becomes equal to NULL. • Make previous point to current. • Make current point to the next node in sequence. previous current current 3. Allocate memory for the new node. 5. Assign value to the data field of the new node. 7. Make the next field of the new node point to current. 9. Make the next field of previous point to the new node. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Identify the nodes between which the new node is to be inserted. Mark them Insert 16 as previous and current. To locate previous and current, execute the following steps: • Make current point to the first node. START • Make previous point to NULL. • Repeat step d and step e until current.info becomes greater than newnode.info or current 10 10 15 17 20 becomes equal to NULL. • Make previous point to current. • Make current point to the next node in sequence. previous current 3. Allocate memory for the new node. 5. Assign value to the data field of the new node. 7. Make the next field of the new node point to current. 9. Make the next field of previous point to the new node. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Identify the nodes between which the new node is to be inserted. Mark them Insert 16 as previous and current. To locate previous and current, execute the following steps: • Make current point to the first node. START • Make previous point to NULL. • Repeat step d and step e until current.info becomes greater than newnode.info or current 10 10 15 17 20 becomes equal to NULL. • Make previous point to current. • Make current point to the next node in sequence. previous previous current 3. Allocate memory for the new node. 5. Assign value to the data field of the new node. 7. Make the next field of the new node point to current. 9. Make the next field of previous point to the new node. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Identify the nodes between which the new node is to be inserted. Mark them Insert 16 as previous and current. To locate previous and current, execute the following steps: • Make current point to the first node. START • Make previous point to NULL. • Repeat step d and step e until current.info becomes greater than newnode.info or current 10 10 15 17 20 becomes equal to NULL. • Make previous point to current. • Make current point to the next node in sequence. previous currentcurrent 3. Allocate memory for the new node. 5. Assign value to the data field of the new node. 7. Make the next field of the new node point to current. 9. Make the next field of previous point to the new node. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Identify the nodes between which the new node is to be inserted. Mark them Insert 16 as previous and current. To locate previous and current, execute the following steps: • Make current point to the first node. START • Make previous point to NULL. • Repeat step d and step e until current.info becomes greater than newnode.info or current 10 10 15 17 20 becomes equal to NULL. • Make previous point to current. • Make current point to the next node in sequence. previous current 3. Allocate memory for the new node. Nodes located 5. Assign value to the data field of the new node. 7. Make the next field of the new node point to current. 9. Make the next field of previous point to the new node. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Identify the nodes between which the newnode new node is to be inserted. Mark them as previous and current. To locate previous and current, execute the following steps: a. Make current point to the first node. START b. Make previous point to NULL. c. Repeat step d and step e until current.info becomes greater than newnode.info or current 10 10 15 17 20 becomes equal to NULL. d. Make previous point to current. e. Make current point to the next node in sequence. previous current • Allocate memory for the new node. Nodes located • Assign value to the data field of the new node. • Make the next field of the new node point to current. • Make the next field of previous point to the new node. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Identify the nodes between which the newnode new node is to be inserted. Mark them as previous and current. To locate previous and current, execute the following steps: a. Make current point to the first 16 node. START b. Make previous point to NULL. c. Repeat step d and step e until current.info becomes greater than newnode.info or current 10 10 15 17 20 becomes equal to NULL. d. Make previous point to current. e. Make current point to the next node in sequence. previous current • Allocate memory for the new node. • Assign value to the data field of the new node. • Make the next field of the new node point to current. • Make the next field of previous point to the new node. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Identify the nodes between which the newnode new node is to be inserted. Mark them as previous and current. To locate previous and current, execute the following steps: a. Make current point to the first 16 node. START b. Make previous point to NULL. c. Repeat step d and step e until current.info becomes greater than newnode.info or current 10 10 15 17 20 becomes equal to NULL. d. Make previous point to current. e. Make current point to the next node in sequence. previous current • Allocate memory for the new node. • Assign value to the data field of the new node. newnode.next = current • Make the next field of the new node point to current. • Make the next field of previous point to the new node. Ver. 1.0 Session 7
Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Identify the nodes between which the newnode new node is to be inserted. Mark them as previous and current. To locate previous and current, execute the following steps: a. Make current point to the first 16 node. START b. Make previous point to NULL. c. Repeat step d and step e until current.info becomes greater than newnode.info or current 10 10 15 17 20 becomes equal to NULL. d. Make previous point to current. e. Make current point to the next node in sequence. previous current • Allocate memory for the new node. • Assign value to the data field of the new node. newnode.next = current • Make the next field of the new node point to current. previous.next = newnode • Make the next field of previous point to the new node. Insertion complete Ver. 1.0 Session 7
Data Structures and Algorithms Traversing a Singly-Linked List 1. Make currentNode point to the first node in the list. Algorithm for traversing a linked singly-linked list. Write an algorithm to traverse a list. 3. Repeat step 3 and 4 until currentNode becomes NULL. 5. Display the information contained in the node marked as currentNode. START 7. Make currentNode point to the next node in sequence. 2 3 5 7 Ver. 1.0 Session 7
Data Structures and Algorithms Traversing a Singly-Linked List (Contd.) • Make currentNode point to the first node in the list. Refer to the algorithm to display the • Repeat step 3 and 4 until elements in the linked list. currentNode becomes NULL. • Display the information contained in the node marked as currentNode. START • Make currentNode point to the next node in sequence. 2 10 3 10 5 10 7 10 currentNode Ver. 1.0 Session 7
Data Structures and Algorithms Traversing a Singly-Linked List (Contd.) • Make currentNode point to the first node in the list. • Repeat step 3 and 4 until currentNode becomes NULL. • Display the information contained in the node marked as currentNode. START • Make currentNode point to the next node in sequence. 2 10 3 10 5 10 7 10 currentNode Ver. 1.0 Session 7
Data Structures and Algorithms Traversing a Singly-Linked List (Contd.) • Make currentNode point to the first node in the list. • Repeat step 3 and 4 until currentNode becomes NULL. • Display the information contained in the node marked as currentNode. START • Make currentNode point to the next node in sequence. 2 10 3 10 5 10 7 10 currentNode 2 Ver. 1.0 Session 7
Data Structures and Algorithms Traversing a Singly-Linked List (Contd.) • Make currentNode point to the first node in the list. • Repeat step 3 and 4 until currentNode becomes NULL. • Display the information contained in the node marked as currentNode. START • Make currentNode point to the next node in sequence. 2 10 3 10 5 10 7 10 currentNode currentNode 2 Ver. 1.0 Session 7
Data Structures and Algorithms Traversing a Singly-Linked List (Contd.) • Make currentNode point to the first node in the list. • Repeat step 3 and 4 until currentNode becomes NULL. • Display the information contained in the node marked as currentNode. START • Make currentNode point to the next node in sequence. 2 10 3 10 5 10 7 10 currentNode 2 Ver. 1.0 Session 7
Data Structures and Algorithms Traversing a Singly-Linked List (Contd.) • Make currentNode point to the first node in the list. • Repeat step 3 and 4 until currentNode becomes NULL. • Display the information contained in the node marked as currentNode. START • Make currentNode point to the next node in sequence. 2 10 3 10 5 10 7 10 currentNode 2 3 Ver. 1.0 Session 7
Data Structures and Algorithms Traversing a Singly-Linked List (Contd.) • Make currentNode point to the first node in the list. • Repeat step 3 and 4 until currentNode becomes NULL. • Display the information contained in the node marked as currentNode. START • Make currentNode point to the next node in sequence. 2 10 3 10 5 10 7 10 currentNode currentNode 2 3 Ver. 1.0 Session 7
Data Structures and Algorithms Traversing a Singly-Linked List (Contd.) • Make currentNode point to the first node in the list. • Repeat step 3 and 4 until currentNode becomes NULL. • Display the information contained in the node marked as currentNode. START • Make currentNode point to the next node in sequence. 2 10 3 10 5 10 7 10 currentNode 2 3 Ver. 1.0 Session 7
Data Structures and Algorithms Traversing a Singly-Linked List (Contd.) • Make currentNode point to the first node in the list. • Repeat step 3 and 4 until currentNode becomes NULL. • Display the information contained in the node marked as currentNode. START • Make currentNode point to the next node in sequence. 2 10 3 10 5 10 7 10 currentNode 2 3 5 Ver. 1.0 Session 7
Data Structures and Algorithms Traversing a Singly-Linked List (Contd.) • Make currentNode point to the first node in the list. • Repeat step 3 and 4 until currentNode becomes NULL. • Display the information contained in the node marked as currentNode. START • Make currentNode point to the next node in sequence. 2 10 3 10 5 10 7 10 currentNode currentNode 2 3 5 Ver. 1.0 Session 7
Data Structures and Algorithms Traversing a Singly-Linked List (Contd.) • Make currentNode point to the first node in the list. • Repeat step 3 and 4 until currentNode becomes NULL. • Display the information contained in the node marked as currentNode. START • Make currentNode point to the next node in sequence. 2 10 3 10 5 10 7 10 currentNode 2 3 5 Ver. 1.0 Session 7
Data Structures and Algorithms Traversing a Singly-Linked List (Contd.) • Make currentNode point to the first node in the list. • Repeat step 3 and 4 until currentNode becomes NULL. • Display the information contained in the node marked as currentNode. START • Make currentNode point to the next node in sequence. 2 10 3 10 5 10 7 10 currentNode 2 3 5 7 Ver. 1.0 Session 7
Data Structures and Algorithms Traversing a Singly-Linked List (Contd.) • Make currentNode point to the first node in the list. • Repeat step 3 and 4 until currentNode becomes NULL. • Display the information contained in the node marked as currentNode. START • Make currentNode point to the next node in sequence. 2 10 3 10 5 10 7 10 currentNode currentNode = NULL 2 3 5 7 Ver. 1.0 Session 7
Data Structures and Algorithms Traversing a Singly-Linked List (Contd.) • Make currentNode point to the first node in the list. • Repeat step 3 and 4 until currentNode becomes NULL. • Display the information contained in the node marked as currentNode. START • Make currentNode point to the next node in sequence. 2 10 3 10 5 10 7 10 currentNode = NULL 2 3 5 7 Traversal complete Ver. 1.0 Session 7
Data Structures and Algorithms Deleting a Node from a Singly-Linked List Delete operation in a linked list refers to the process of removing a specified node from the list. You can delete a node from the following places in a linked list: Beginning of the list Between two nodes in the list End of the list Ver. 1.0 Session 7
Data Structures and Algorithms Deleting a Node From the Beginning of the List Write an algorithm to delete the first node in a linked list. Ver. 1.0 Session 7
Data Structures and Algorithms Deleting a Node From the Beginning of the List (Contd.) 1. Mark the first node in the list Algorithm to delete a node from the as current. beginning of a linked list. 3. Make START point to the next node in its sequence. START 5. Release the memory for the node marked as current. 10 15 17 20 Ver. 1.0 Session 7
Data Structures and Algorithms Deleting a Node From the Beginning of a Linked List (Contd.) • Mark the first node in the list as current. • Make START point to the next node in its sequence. START • Release the memory for the node marked as current. 10 10 15 17 20 current current = START Ver. 1.0 Session 7
Data Structures and Algorithms Deleting a Node From the Beginning of a Linked List (Contd.) • Mark the first node in the list as current. • Make START point to the next node in its sequence. START START • Release the memory for the node marked as current. 10 10 15 17 20 current current = START START = START. next Ver. 1.0 Session 7
Data Structures and Algorithms Deleting a Node From the Beginning of a Linked List (Contd.) • Mark the first node in the list as current. • Make START point to the next node in its sequence. START • Release the memory for the node marked as current. 10 15 17 20 current Memory released current = START START = START. next Delete operation complete Ver. 1.0 Session 7
Data Structures and Algorithms Deleting a Node Between two Nodes in the List Write an algorithm to delete a node between two nodes in a linked list. Ver. 1.0 Session 7
Data Structures and Algorithms Deleting a Node Between two Nodes in the List (Contd.) 1. Locate the node to be deleted. Mark the node to be deleted as current and its Algorithm to delete a node Delete 17 predecessor as previous. To locate between two nodes in the list. current and previous, execute the following steps: a. Set previous = START b. Set current = START START c. Repeat step d and e until either the node is found or current becomes NULL. d. Make previous point to 10 15 17 20 current . e. Make current point to the next node in sequence. 3. Make the next field of previous point to the successor of current. 5. Release the memory for the node marked as current. Ver. 1.0 Session 7
Data Structures and Algorithms Deleting a Node Between two Nodes in the List (Contd.) 1. Locate the node to be deleted. Mark the node to be deleted as current and its Delete 17 predecessor as previous. To locate current and previous, execute the following steps: a. Set previous = START b. Set current = START START c. Repeat step d and e until either the node is found or current becomes NULL. d. Make previous point to 10 10 15 17 20 current. e. Make current point to the next node in sequence. 3. Make the next field of previous point to the successor of current. 5. Release the memory for the node marked as current. Ver. 1.0 Session 7
Data Structures and Algorithms Deleting a Node Between two Nodes in the List (Contd.) • Locate the node to be deleted. Mark the node to be deleted as current and its Delete 17 predecessor as previous. To locate current and previous, execute the following steps: • Set previous = START • Set current = START START • Repeat step d and e until either the node is found or current becomes NULL. • Make previous point to 10 10 15 17 20 • current. Make current point to the next node in sequence. 3. Make the next field of previous point to previous the successor of current. 5. Release the memory for the node marked as current. Ver. 1.0 Session 7
Data Structures and Algorithms Deleting a Node Between two Nodes in the List (Contd.) 1. Locate the node to be deleted. Mark the node to be deleted as current and its Delete 17 predecessor as previous. To locate current and previous, execute the following steps: • Set previous = START • Set current = START START • Repeat step d and e until either the node is found or current becomes NULL. • Make previous point to 10 10 15 17 20 • current. Make current point to the next node in sequence. 3. Make the next field of previous point to previous current the successor of current. 5. Release the memory for the node marked as current. Ver. 1.0 Session 7
Data Structures and Algorithms Deleting a Node Between two Nodes in the List (Contd.) 1. Locate the node to be deleted. Mark the node to be deleted as current and its Delete 17 predecessor as previous. To locate current and previous, execute the following steps: • Set previous = START • Set current = START START • Repeat step d and e until either the node is found or current becomes NULL. • Make previous point to 10 10 15 17 20 • current. Make current point to the next node in sequence. 3. Make the next field of previous point to previous current the successor of current. 5. Release the memory for the node marked as current. Ver. 1.0 Session 7
Data Structures and Algorithms Deleting a Node Between two Nodes in the List (Contd.) 1. Locate the node to be deleted. Mark the node to be deleted as current and its Delete 17 predecessor as previous. To locate current and previous, execute the following steps: • Set previous = START • Set current = START START • Repeat step d and e until either the node is found or current becomes NULL. • Make previous point to 10 10 15 17 20 • current. Make current point to the next node in sequence. 3. Make the next field of previous point to previous current the successor of current. 5. Release the memory for the node marked as current. Ver. 1.0 Session 7
Data Structures and Algorithms Deleting a Node Between two Nodes in the List (Contd.) 1. Locate the node to be deleted. Mark the node to be deleted as current and its Delete 17 predecessor as previous. To locate current and previous, execute the following steps: • Set previous = START • Set current = START START • Repeat step d and e until either the node is found or current becomes NULL. • Make previous point to 10 10 15 17 20 • current. Make current point to the next node in sequence. • Make the next field of previous point to previous current current the successor of current. • Release the memory for the node marked as current. Ver. 1.0 Session 7
Data Structures and Algorithms Deleting a Node Between two Nodes in the List (Contd.) 1. Locate the node to be deleted. Mark the node to be deleted as current and its Delete 17 predecessor as previous. To locate current and previous, execute the following steps: • Set previous = START • Set current = START START • Repeat step d and e until either the node is found or current becomes NULL. • Make previous point to 10 10 15 17 20 • current. Make current point to the next node in sequence. 3. Make the next field of previous point to previous current the successor of current. 5. Release the memory for the node marked as current. Ver. 1.0 Session 7
Data Structures and Algorithms Deleting a Node Between two Nodes in the List (Contd.) 1. Locate the node to be deleted. Mark the node to be deleted as current and its Delete 17 predecessor as previous. To locate current and previous, execute the following steps: • Set previous = START • Set current = START START • Repeat step d and e until either the node is found or current becomes NULL. • Make previous point to 10 10 15 17 20 • current. Make current point to the next node in sequence. 3. Make the next field of previous point to previous previous current the successor of current. 5. Release the memory for the node marked as current. Ver. 1.0 Session 7
Data Structures and Algorithms Deleting a Node Between two Nodes in the List (Contd.) 1. Locate the node to be deleted. Mark the node to be deleted as current and its Delete 17 predecessor as previous. To locate current and previous, execute the following steps: • Set previous = START • Set current = START START • Repeat step d and e until either the node is found or current becomes NULL. • Make previous point to 10 10 15 17 20 • current. Make current point to the next node in sequence. • Make the next field of previous point to previous current current the successor of current. • Release the memory for the node marked as current. Ver. 1.0 Session 7
Data Structures and Algorithms Deleting a Node Between two Nodes in the List (Contd.) 1. Locate the node to be deleted. Mark the node to be deleted as current and its Delete 17 predecessor as previous. To locate current and previous, execute the following steps: • Set previous = START • Set current = START START • Repeat step d and e until either the node is found or current becomes NULL. • Make previous point to 10 10 15 17 20 • current. Make current point to the next node in sequence. 3. Make the next field of previous point to previous current the successor of current. 5. Release the memory for the node marked as current. Ver. 1.0 Session 7
Data Structures and Algorithms Deleting a Node Between two Nodes in the List (Contd.) 1. Locate the node to be deleted. Mark the node to be deleted as current and its Delete 17 predecessor as previous. To locate current and previous, execute the following steps: a. Set previous = START b. Set current = START START c. Repeat step d and e until either the node is found or current becomes NULL. d. Make previous point to 10 10 15 17 20 current. e. Make current point to the next node in sequence. • Make the next field of previous point to previous current the successor of current. • Release the memory for the node marked as current. previous.next = current.next Ver. 1.0 Session 7
Data Structures and Algorithms Deleting a Node Between two Nodes in the List (Contd.) 1. Locate the node to be deleted. Mark the node to be deleted as current and its Delete 17 predecessor as previous. To locate current and previous, execute the following steps: Delete operation complete a. Set previous = START b. Set current = START START c. Repeat step d and e until either the node is found or current becomes NULL. d. Make previous point to 10 10 15 17 20 current. e. Make current point to the next node in sequence. • Make the next field of previous point to previous current the successor of current. • Release the memory for the node marked as current. previous.next = current.next Ver. 1.0 Session 7
Data Structures and Algorithms Group Discussion Problem Statement – Discuss the advantages and disadvantages of linked lists. Ver. 1.0 Session 7
Data Structures and Algorithms Group Discussion (Contd.) Problem Statement Discuss the differences between arrays and linked lists. Ver. 1.0 Session 7
Data Structures and Algorithms Just a minute Linked lists allow _________ access to elements. Answer: sequential Ver. 1.0 Session 7
Data Structures and Algorithms Representing a Singly-Linked List A Linked list is represented in a program by defining two classes: – Node class: This class contains the data members of varying data types, which represent data to be stored in a linked list. It also contains the reference of the class type (Node) to hold the reference of the next node in sequence. // Code in C#: class Node { public int data; public Node next; // Variable containing // the address of the // next node in // sequence } Ver. 1.0 Session 7
Data Structures and Algorithms Representing a Singly-Linked List (Contd.) // Code in C++ class Node { public: int data; Node *next; // Pointer to the // next node in // sequence }; Ver. 1.0 Session 7
Data Structures and Algorithms Representing a Singly-Linked List (Contd.) List class: This class consists of a set of operations implemented on a linked list. These operations are insertion, deletion, search, and traversal. It also contains the declaration of a variable/pointer, START that always points to the first node in the list. // Code in C#: class Node { public int data; public Node next; // Variable containing // the address of the // next node in // sequence } Ver. 1.0 Session 7
Data Structures and Algorithms Representing a Singly-Linked List (Contd.) // Code in C#: class List { private Node START; List() { START = NULL; } public void addNode(int element){} public bool search(int element, ref Node previous, ref Node current) {} public bool delNode(int element) {} public void traverse() {} } Ver. 1.0 Session 7
Data Structures and Algorithms Representing a Singly-Linked List (Contd.) // Code in C#: class List { Node * START; public: List() { START = NULL; } void addNode(int element); bool search(int element, Node *previous, Node *current); bool delNode(int element); void traverse(); }; Ver. 1.0 Session 7
Data Structures and Algorithms Activity: Implementing a Singly-Linked List Problem Statement: Write a program to implement insert, search, delete, and traverse operations on a singly-linked list that stores the records of the students in a class. Each record holds the following information: – Roll number of the student – Name of the student Ver. 1.0 Session 7
Data Structures and Algorithms Summary In this session, you learned that: In a singly-linked list, each node contains: – The information – The address of the next node in the list – Singly-linked list can be traversed only in a single direction. – Insertion and deletion in a linked list is fast as compared to arrays. However, accessing elements is faster in arrays as compared to linked lists. Ver. 1.0 Session 7
Ad

Recommended

11.optimal nonlocal means algorithm for denoising ultrasound image
11.optimal nonlocal means algorithm for denoising ultrasound image11.optimal nonlocal means algorithm for denoising ultrasound image
11.optimal nonlocal means algorithm for denoising ultrasound image
Alexander Decker
 
Optimal nonlocal means algorithm for denoising ultrasound image
Optimal nonlocal means algorithm for denoising ultrasound imageOptimal nonlocal means algorithm for denoising ultrasound image
Optimal nonlocal means algorithm for denoising ultrasound image
Alexander Decker
 
071bct537 lab4
071bct537 lab4071bct537 lab4
071bct537 lab4
shailesh kandel
 
Kernels in convolution
Kernels in convolutionKernels in convolution
Kernels in convolution
Revanth Kumar
 
APPLIED MACHINE LEARNING
APPLIED MACHINE LEARNINGAPPLIED MACHINE LEARNING
APPLIED MACHINE LEARNING
Revanth Kumar
 
CVPR2009 tutorial: Kernel Methods in Computer Vision: part I: Introduction to...
CVPR2009 tutorial: Kernel Methods in Computer Vision: part I: Introduction to...CVPR2009 tutorial: Kernel Methods in Computer Vision: part I: Introduction to...
CVPR2009 tutorial: Kernel Methods in Computer Vision: part I: Introduction to...
zukun
 
Neural network
Neural networkNeural network
Neural network
marada0033
 
Artificial Neural Network
Artificial Neural NetworkArtificial Neural Network
Artificial Neural Network
Pratik Aggarwal
 
DCT
DCTDCT
DCT
aniruddh Tyagi
 
Deep neural networks & computational graphs
Deep neural networks & computational graphsDeep neural networks & computational graphs
Deep neural networks & computational graphs
Revanth Kumar
 
Deep learning algorithms
Deep learning algorithmsDeep learning algorithms
Deep learning algorithms
Revanth Kumar
 
Image Recognition With the Help of Auto-Associative Neural Network
Image Recognition With the Help of Auto-Associative Neural NetworkImage Recognition With the Help of Auto-Associative Neural Network
Image Recognition With the Help of Auto-Associative Neural Network
CSCJournals
 
Efficient Variable Size Template Matching Using Fast Normalized Cross Correla...
Efficient Variable Size Template Matching Using Fast Normalized Cross Correla...Efficient Variable Size Template Matching Using Fast Normalized Cross Correla...
Efficient Variable Size Template Matching Using Fast Normalized Cross Correla...
Gurbinder Gill
 
Deep Learning Interview Questions And Answers | AI & Deep Learning Interview ...
Deep Learning Interview Questions And Answers | AI & Deep Learning Interview ...Deep Learning Interview Questions And Answers | AI & Deep Learning Interview ...
Deep Learning Interview Questions And Answers | AI & Deep Learning Interview ...
Simplilearn
 
Multilayer Backpropagation Neural Networks for Implementation of Logic Gates
Multilayer Backpropagation Neural Networks for Implementation of Logic GatesMultilayer Backpropagation Neural Networks for Implementation of Logic Gates
Multilayer Backpropagation Neural Networks for Implementation of Logic Gates
IJCSES Journal
 
Soft Computering Technics - Unit2
Soft Computering Technics - Unit2Soft Computering Technics - Unit2
Soft Computering Technics - Unit2
sravanthi computers
 
Image Compression Using Wavelet Packet Tree
Image Compression Using Wavelet Packet TreeImage Compression Using Wavelet Packet Tree
Image Compression Using Wavelet Packet Tree
IDES Editor
 
Artificial neural network
Artificial neural networkArtificial neural network
Artificial neural network
Ildar Nurgaliev
 
Distilling Free-Form Natural Laws from Experimental Data
Distilling Free-Form Natural Laws from Experimental DataDistilling Free-Form Natural Laws from Experimental Data
Distilling Free-Form Natural Laws from Experimental Data
swissnex San Francisco
 
A Mixed Binary-Real NSGA II Algorithm Ensuring Both Accuracy and Interpretabi...
A Mixed Binary-Real NSGA II Algorithm Ensuring Both Accuracy and Interpretabi...A Mixed Binary-Real NSGA II Algorithm Ensuring Both Accuracy and Interpretabi...
A Mixed Binary-Real NSGA II Algorithm Ensuring Both Accuracy and Interpretabi...
IJECEIAES
 
03 ds and algorithm session_04
03 ds and algorithm session_0403 ds and algorithm session_04
03 ds and algorithm session_04
Niit Care
 
Ds 1
Ds 1Ds 1
Ds 1
Niit Care
 
01 ds and algorithm session_01
01 ds and algorithm session_0101 ds and algorithm session_01
01 ds and algorithm session_01
Niit Care
 
Chapter 15
Chapter 15Chapter 15
Chapter 15
Bangabandhu Sheikh Mujibur Rahman Science and Technology University
 
Operations on linked list
Operations on linked listOperations on linked list
Operations on linked list
Sumathi Kv
 
04 ds and algorithm session_05
04 ds and algorithm session_0504 ds and algorithm session_05
04 ds and algorithm session_05
Niit Care
 
Lec6 mod linked list
Lec6 mod linked listLec6 mod linked list
Lec6 mod linked list
Ibrahim El-Torbany
 
07 ds and algorithm session_10
07 ds and algorithm session_1007 ds and algorithm session_10
07 ds and algorithm session_10
Niit Care
 
Chap 13(dynamic memory allocation)
Chap 13(dynamic memory allocation)Chap 13(dynamic memory allocation)
Chap 13(dynamic memory allocation)
Bangabandhu Sheikh Mujibur Rahman Science and Technology University
 
02 ds and algorithm session_02
02 ds and algorithm session_0202 ds and algorithm session_02
02 ds and algorithm session_02
Niit Care
 
Ad

More Related Content

What's hot (12)

DCT
DCTDCT
DCT
aniruddh Tyagi
 
Deep neural networks & computational graphs
Deep neural networks & computational graphsDeep neural networks & computational graphs
Deep neural networks & computational graphs
Revanth Kumar
 
Deep learning algorithms
Deep learning algorithmsDeep learning algorithms
Deep learning algorithms
Revanth Kumar
 
Image Recognition With the Help of Auto-Associative Neural Network
Image Recognition With the Help of Auto-Associative Neural NetworkImage Recognition With the Help of Auto-Associative Neural Network
Image Recognition With the Help of Auto-Associative Neural Network
CSCJournals
 
Efficient Variable Size Template Matching Using Fast Normalized Cross Correla...
Efficient Variable Size Template Matching Using Fast Normalized Cross Correla...Efficient Variable Size Template Matching Using Fast Normalized Cross Correla...
Efficient Variable Size Template Matching Using Fast Normalized Cross Correla...
Gurbinder Gill
 
Deep Learning Interview Questions And Answers | AI & Deep Learning Interview ...
Deep Learning Interview Questions And Answers | AI & Deep Learning Interview ...Deep Learning Interview Questions And Answers | AI & Deep Learning Interview ...
Deep Learning Interview Questions And Answers | AI & Deep Learning Interview ...
Simplilearn
 
Multilayer Backpropagation Neural Networks for Implementation of Logic Gates
Multilayer Backpropagation Neural Networks for Implementation of Logic GatesMultilayer Backpropagation Neural Networks for Implementation of Logic Gates
Multilayer Backpropagation Neural Networks for Implementation of Logic Gates
IJCSES Journal
 
Soft Computering Technics - Unit2
Soft Computering Technics - Unit2Soft Computering Technics - Unit2
Soft Computering Technics - Unit2
sravanthi computers
 
Image Compression Using Wavelet Packet Tree
Image Compression Using Wavelet Packet TreeImage Compression Using Wavelet Packet Tree
Image Compression Using Wavelet Packet Tree
IDES Editor
 
Artificial neural network
Artificial neural networkArtificial neural network
Artificial neural network
Ildar Nurgaliev
 
Distilling Free-Form Natural Laws from Experimental Data
Distilling Free-Form Natural Laws from Experimental DataDistilling Free-Form Natural Laws from Experimental Data
Distilling Free-Form Natural Laws from Experimental Data
swissnex San Francisco
 
A Mixed Binary-Real NSGA II Algorithm Ensuring Both Accuracy and Interpretabi...
A Mixed Binary-Real NSGA II Algorithm Ensuring Both Accuracy and Interpretabi...A Mixed Binary-Real NSGA II Algorithm Ensuring Both Accuracy and Interpretabi...
A Mixed Binary-Real NSGA II Algorithm Ensuring Both Accuracy and Interpretabi...
IJECEIAES
 
DCT
DCTDCT
DCT
aniruddh Tyagi
 
Deep neural networks & computational graphs
Deep neural networks & computational graphsDeep neural networks & computational graphs
Deep neural networks & computational graphs
Revanth Kumar
 
Deep learning algorithms
Deep learning algorithmsDeep learning algorithms
Deep learning algorithms
Revanth Kumar
 
Image Recognition With the Help of Auto-Associative Neural Network
Image Recognition With the Help of Auto-Associative Neural NetworkImage Recognition With the Help of Auto-Associative Neural Network
Image Recognition With the Help of Auto-Associative Neural Network
CSCJournals
 
Efficient Variable Size Template Matching Using Fast Normalized Cross Correla...
Efficient Variable Size Template Matching Using Fast Normalized Cross Correla...Efficient Variable Size Template Matching Using Fast Normalized Cross Correla...
Efficient Variable Size Template Matching Using Fast Normalized Cross Correla...
Gurbinder Gill
 
Deep Learning Interview Questions And Answers | AI & Deep Learning Interview ...
Deep Learning Interview Questions And Answers | AI & Deep Learning Interview ...Deep Learning Interview Questions And Answers | AI & Deep Learning Interview ...
Deep Learning Interview Questions And Answers | AI & Deep Learning Interview ...
Simplilearn
 
Multilayer Backpropagation Neural Networks for Implementation of Logic Gates
Multilayer Backpropagation Neural Networks for Implementation of Logic GatesMultilayer Backpropagation Neural Networks for Implementation of Logic Gates
Multilayer Backpropagation Neural Networks for Implementation of Logic Gates
IJCSES Journal
 
Soft Computering Technics - Unit2
Soft Computering Technics - Unit2Soft Computering Technics - Unit2
Soft Computering Technics - Unit2
sravanthi computers
 
Image Compression Using Wavelet Packet Tree
Image Compression Using Wavelet Packet TreeImage Compression Using Wavelet Packet Tree
Image Compression Using Wavelet Packet Tree
IDES Editor
 
Artificial neural network
Artificial neural networkArtificial neural network
Artificial neural network
Ildar Nurgaliev
 
Distilling Free-Form Natural Laws from Experimental Data
Distilling Free-Form Natural Laws from Experimental DataDistilling Free-Form Natural Laws from Experimental Data
Distilling Free-Form Natural Laws from Experimental Data
swissnex San Francisco
 
A Mixed Binary-Real NSGA II Algorithm Ensuring Both Accuracy and Interpretabi...
A Mixed Binary-Real NSGA II Algorithm Ensuring Both Accuracy and Interpretabi...A Mixed Binary-Real NSGA II Algorithm Ensuring Both Accuracy and Interpretabi...
A Mixed Binary-Real NSGA II Algorithm Ensuring Both Accuracy and Interpretabi...
IJECEIAES
 

Viewers also liked (20)

03 ds and algorithm session_04
03 ds and algorithm session_0403 ds and algorithm session_04
03 ds and algorithm session_04
Niit Care
 
Ds 1
Ds 1Ds 1
Ds 1
Niit Care
 
01 ds and algorithm session_01
01 ds and algorithm session_0101 ds and algorithm session_01
01 ds and algorithm session_01
Niit Care
 
Chapter 15
Chapter 15Chapter 15
Chapter 15
Bangabandhu Sheikh Mujibur Rahman Science and Technology University
 
Operations on linked list
Operations on linked listOperations on linked list
Operations on linked list
Sumathi Kv
 
04 ds and algorithm session_05
04 ds and algorithm session_0504 ds and algorithm session_05
04 ds and algorithm session_05
Niit Care
 
Lec6 mod linked list
Lec6 mod linked listLec6 mod linked list
Lec6 mod linked list
Ibrahim El-Torbany
 
07 ds and algorithm session_10
07 ds and algorithm session_1007 ds and algorithm session_10
07 ds and algorithm session_10
Niit Care
 
Chap 13(dynamic memory allocation)
Chap 13(dynamic memory allocation)Chap 13(dynamic memory allocation)
Chap 13(dynamic memory allocation)
Bangabandhu Sheikh Mujibur Rahman Science and Technology University
 
02 ds and algorithm session_02
02 ds and algorithm session_0202 ds and algorithm session_02
02 ds and algorithm session_02
Niit Care
 
Linked Lists
Linked ListsLinked Lists
Linked Lists
Hafiz Umair
 
Applications of data structures
Applications of data structuresApplications of data structures
Applications of data structures
Wipro
 
Sparse Matrix and Polynomial
Sparse Matrix and PolynomialSparse Matrix and Polynomial
Sparse Matrix and Polynomial
Aroosa Rajput
 
Multiplication of two 3 d sparse matrices using 1d arrays and linked lists
Multiplication of two 3 d sparse matrices using 1d arrays and linked listsMultiplication of two 3 d sparse matrices using 1d arrays and linked lists
Multiplication of two 3 d sparse matrices using 1d arrays and linked lists
Dr Sandeep Kumar Poonia
 
Sparse matrices
Sparse matricesSparse matrices
Sparse matrices
Zain Zafar
 
Data Structure (Dynamic Array and Linked List)
Data Structure (Dynamic Array and Linked List)Data Structure (Dynamic Array and Linked List)
Data Structure (Dynamic Array and Linked List)
Adam Mukharil Bachtiar
 
linked list
linked list linked list
linked list
Narendra Chauhan
 
Linked list
Linked listLinked list
Linked list
Trupti Agrawal
 
Linked list
Linked listLinked list
Linked list
akshat360
 
Data structure and its types
Data structure and its typesData structure and its types
Data structure and its types
Navtar Sidhu Brar
 
03 ds and algorithm session_04
03 ds and algorithm session_0403 ds and algorithm session_04
03 ds and algorithm session_04
Niit Care
 
Ds 1
Ds 1Ds 1
Ds 1
Niit Care
 
01 ds and algorithm session_01
01 ds and algorithm session_0101 ds and algorithm session_01
01 ds and algorithm session_01
Niit Care
 
Chapter 15
Chapter 15Chapter 15
Chapter 15
Bangabandhu Sheikh Mujibur Rahman Science and Technology University
 
Operations on linked list
Operations on linked listOperations on linked list
Operations on linked list
Sumathi Kv
 
04 ds and algorithm session_05
04 ds and algorithm session_0504 ds and algorithm session_05
04 ds and algorithm session_05
Niit Care
 
Lec6 mod linked list
Lec6 mod linked listLec6 mod linked list
Lec6 mod linked list
Ibrahim El-Torbany
 
07 ds and algorithm session_10
07 ds and algorithm session_1007 ds and algorithm session_10
07 ds and algorithm session_10
Niit Care
 
Chap 13(dynamic memory allocation)
Chap 13(dynamic memory allocation)Chap 13(dynamic memory allocation)
Chap 13(dynamic memory allocation)
Bangabandhu Sheikh Mujibur Rahman Science and Technology University
 
02 ds and algorithm session_02
02 ds and algorithm session_0202 ds and algorithm session_02
02 ds and algorithm session_02
Niit Care
 
Linked Lists
Linked ListsLinked Lists
Linked Lists
Hafiz Umair
 
Applications of data structures
Applications of data structuresApplications of data structures
Applications of data structures
Wipro
 
Sparse Matrix and Polynomial
Sparse Matrix and PolynomialSparse Matrix and Polynomial
Sparse Matrix and Polynomial
Aroosa Rajput
 
Multiplication of two 3 d sparse matrices using 1d arrays and linked lists
Multiplication of two 3 d sparse matrices using 1d arrays and linked listsMultiplication of two 3 d sparse matrices using 1d arrays and linked lists
Multiplication of two 3 d sparse matrices using 1d arrays and linked lists
Dr Sandeep Kumar Poonia
 
Sparse matrices
Sparse matricesSparse matrices
Sparse matrices
Zain Zafar
 
Data Structure (Dynamic Array and Linked List)
Data Structure (Dynamic Array and Linked List)Data Structure (Dynamic Array and Linked List)
Data Structure (Dynamic Array and Linked List)
Adam Mukharil Bachtiar
 
linked list
linked list linked list
linked list
Narendra Chauhan
 
Linked list
Linked listLinked list
Linked list
Trupti Agrawal
 
Linked list
Linked listLinked list
Linked list
akshat360
 
Data structure and its types
Data structure and its typesData structure and its types
Data structure and its types
Navtar Sidhu Brar
 
Ad

Similar to 05 ds and algorithm session_07 (13)

Presentation overview of neural & kernel based clustering
Presentation overview of neural & kernel based clustering Presentation overview of neural & kernel based clustering
Presentation overview of neural & kernel based clustering
Shubham Vijay Vargiy
 
Architecture_L5 (3).pdf wwwwwwwwwwwwwwwwwwwwwwwwwww
Architecture_L5 (3).pdf wwwwwwwwwwwwwwwwwwwwwwwwwwwArchitecture_L5 (3).pdf wwwwwwwwwwwwwwwwwwwwwwwwwww
Architecture_L5 (3).pdf wwwwwwwwwwwwwwwwwwwwwwwwwww
shivenpatel42
 
Dynamic memory allocation
Dynamic memory allocationDynamic memory allocation
Dynamic memory allocation
MI RAKIB
 
06 linked list
06 linked list06 linked list
06 linked list
Rajan Gautam
 
memory allocation.pptx
memory allocation.pptxmemory allocation.pptx
memory allocation.pptx
SHRISTEERAI1
 
memory allocation by Novodita
memory allocation by Novoditamemory allocation by Novodita
memory allocation by Novodita
SHRISTEERAI1
 
Deep Learning for Text (Text Mining) LSTM
Deep Learning for Text (Text Mining) LSTMDeep Learning for Text (Text Mining) LSTM
Deep Learning for Text (Text Mining) LSTM
m0972220819
 
Lecture 3.3.1 Dynamic Memory Allocation and Functions.pptx
Lecture 3.3.1 Dynamic Memory Allocation and Functions.pptxLecture 3.3.1 Dynamic Memory Allocation and Functions.pptx
Lecture 3.3.1 Dynamic Memory Allocation and Functions.pptx
roykaustav382
 
Advanced Non-Relational Schemas For Big Data
Advanced Non-Relational Schemas For Big DataAdvanced Non-Relational Schemas For Big Data
Advanced Non-Relational Schemas For Big Data
Victor Smirnov
 
CLanguage_ClassPPT_3110003_unit 9Material.ppt
CLanguage_ClassPPT_3110003_unit 9Material.pptCLanguage_ClassPPT_3110003_unit 9Material.ppt
CLanguage_ClassPPT_3110003_unit 9Material.ppt
NikeshaPatel1
 
Chapter 8 1 Digital Design and Computer Architecture, 2n.docx
Chapter 8 1 Digital Design and Computer Architecture, 2n.docxChapter 8 1 Digital Design and Computer Architecture, 2n.docx
Chapter 8 1 Digital Design and Computer Architecture, 2n.docx
christinemaritza
 
«Дизайн продвинутых нереляционных схем для Big Data»
«Дизайн продвинутых нереляционных схем для Big Data»«Дизайн продвинутых нереляционных схем для Big Data»
«Дизайн продвинутых нереляционных схем для Big Data»
Olga Lavrentieva
 
hierarchical memory technology.pptx
hierarchical memory technology.pptxhierarchical memory technology.pptx
hierarchical memory technology.pptx
2105986
 
Presentation overview of neural & kernel based clustering
Presentation overview of neural & kernel based clustering Presentation overview of neural & kernel based clustering
Presentation overview of neural & kernel based clustering
Shubham Vijay Vargiy
 
Architecture_L5 (3).pdf wwwwwwwwwwwwwwwwwwwwwwwwwww
Architecture_L5 (3).pdf wwwwwwwwwwwwwwwwwwwwwwwwwwwArchitecture_L5 (3).pdf wwwwwwwwwwwwwwwwwwwwwwwwwww
Architecture_L5 (3).pdf wwwwwwwwwwwwwwwwwwwwwwwwwww
shivenpatel42
 
Dynamic memory allocation
Dynamic memory allocationDynamic memory allocation
Dynamic memory allocation
MI RAKIB
 
06 linked list
06 linked list06 linked list
06 linked list
Rajan Gautam
 
memory allocation.pptx
memory allocation.pptxmemory allocation.pptx
memory allocation.pptx
SHRISTEERAI1
 
memory allocation by Novodita
memory allocation by Novoditamemory allocation by Novodita
memory allocation by Novodita
SHRISTEERAI1
 
Deep Learning for Text (Text Mining) LSTM
Deep Learning for Text (Text Mining) LSTMDeep Learning for Text (Text Mining) LSTM
Deep Learning for Text (Text Mining) LSTM
m0972220819
 
Lecture 3.3.1 Dynamic Memory Allocation and Functions.pptx
Lecture 3.3.1 Dynamic Memory Allocation and Functions.pptxLecture 3.3.1 Dynamic Memory Allocation and Functions.pptx
Lecture 3.3.1 Dynamic Memory Allocation and Functions.pptx
roykaustav382
 
Advanced Non-Relational Schemas For Big Data
Advanced Non-Relational Schemas For Big DataAdvanced Non-Relational Schemas For Big Data
Advanced Non-Relational Schemas For Big Data
Victor Smirnov
 
CLanguage_ClassPPT_3110003_unit 9Material.ppt
CLanguage_ClassPPT_3110003_unit 9Material.pptCLanguage_ClassPPT_3110003_unit 9Material.ppt
CLanguage_ClassPPT_3110003_unit 9Material.ppt
NikeshaPatel1
 
Chapter 8 1 Digital Design and Computer Architecture, 2n.docx
Chapter 8 1 Digital Design and Computer Architecture, 2n.docxChapter 8 1 Digital Design and Computer Architecture, 2n.docx
Chapter 8 1 Digital Design and Computer Architecture, 2n.docx
christinemaritza
 
«Дизайн продвинутых нереляционных схем для Big Data»
«Дизайн продвинутых нереляционных схем для Big Data»«Дизайн продвинутых нереляционных схем для Big Data»
«Дизайн продвинутых нереляционных схем для Big Data»
Olga Lavrentieva
 
hierarchical memory technology.pptx
hierarchical memory technology.pptxhierarchical memory technology.pptx
hierarchical memory technology.pptx
2105986
 
Ad

More from Niit Care (20)

Ajs 1 b
Ajs 1 bAjs 1 b
Ajs 1 b
Niit Care
 
Ajs 4 b
Ajs 4 bAjs 4 b
Ajs 4 b
Niit Care
 
Ajs 4 a
Ajs 4 aAjs 4 a
Ajs 4 a
Niit Care
 
Ajs 4 c
Ajs 4 cAjs 4 c
Ajs 4 c
Niit Care
 
Ajs 3 b
Ajs 3 bAjs 3 b
Ajs 3 b
Niit Care
 
Ajs 3 a
Ajs 3 aAjs 3 a
Ajs 3 a
Niit Care
 
Ajs 3 c
Ajs 3 cAjs 3 c
Ajs 3 c
Niit Care
 
Ajs 2 b
Ajs 2 bAjs 2 b
Ajs 2 b
Niit Care
 
Ajs 2 a
Ajs 2 aAjs 2 a
Ajs 2 a
Niit Care
 
Ajs 2 c
Ajs 2 cAjs 2 c
Ajs 2 c
Niit Care
 
Ajs 1 a
Ajs 1 aAjs 1 a
Ajs 1 a
Niit Care
 
Ajs 1 c
Ajs 1 cAjs 1 c
Ajs 1 c
Niit Care
 
Dacj 4 2-c
Dacj 4 2-cDacj 4 2-c
Dacj 4 2-c
Niit Care
 
Dacj 4 2-b
Dacj 4 2-bDacj 4 2-b
Dacj 4 2-b
Niit Care
 
Dacj 4 2-a
Dacj 4 2-aDacj 4 2-a
Dacj 4 2-a
Niit Care
 
Dacj 4 1-c
Dacj 4 1-cDacj 4 1-c
Dacj 4 1-c
Niit Care
 
Dacj 4 1-b
Dacj 4 1-bDacj 4 1-b
Dacj 4 1-b
Niit Care
 
Dacj 4 1-a
Dacj 4 1-aDacj 4 1-a
Dacj 4 1-a
Niit Care
 
Dacj 1-2 b
Dacj 1-2 bDacj 1-2 b
Dacj 1-2 b
Niit Care
 
Dacj 1-3 c
Dacj 1-3 cDacj 1-3 c
Dacj 1-3 c
Niit Care
 
Ajs 1 b
Ajs 1 bAjs 1 b
Ajs 1 b
Niit Care
 
Ajs 4 b
Ajs 4 bAjs 4 b
Ajs 4 b
Niit Care
 
Ajs 4 a
Ajs 4 aAjs 4 a
Ajs 4 a
Niit Care
 
Ajs 4 c
Ajs 4 cAjs 4 c
Ajs 4 c
Niit Care
 
Ajs 3 b
Ajs 3 bAjs 3 b
Ajs 3 b
Niit Care
 
Ajs 3 a
Ajs 3 aAjs 3 a
Ajs 3 a
Niit Care
 
Ajs 3 c
Ajs 3 cAjs 3 c
Ajs 3 c
Niit Care
 
Ajs 2 b
Ajs 2 bAjs 2 b
Ajs 2 b
Niit Care
 
Ajs 2 a
Ajs 2 aAjs 2 a
Ajs 2 a
Niit Care
 
Ajs 2 c
Ajs 2 cAjs 2 c
Ajs 2 c
Niit Care
 
Ajs 1 a
Ajs 1 aAjs 1 a
Ajs 1 a
Niit Care
 
Ajs 1 c
Ajs 1 cAjs 1 c
Ajs 1 c
Niit Care
 
Dacj 4 2-c
Dacj 4 2-cDacj 4 2-c
Dacj 4 2-c
Niit Care
 
Dacj 4 2-b
Dacj 4 2-bDacj 4 2-b
Dacj 4 2-b
Niit Care
 
Dacj 4 2-a
Dacj 4 2-aDacj 4 2-a
Dacj 4 2-a
Niit Care
 
Dacj 4 1-c
Dacj 4 1-cDacj 4 1-c
Dacj 4 1-c
Niit Care
 
Dacj 4 1-b
Dacj 4 1-bDacj 4 1-b
Dacj 4 1-b
Niit Care
 
Dacj 4 1-a
Dacj 4 1-aDacj 4 1-a
Dacj 4 1-a
Niit Care
 
Dacj 1-2 b
Dacj 1-2 bDacj 1-2 b
Dacj 1-2 b
Niit Care
 
Dacj 1-3 c
Dacj 1-3 cDacj 1-3 c
Dacj 1-3 c
Niit Care
 

Recently uploaded (20)

AI x Accessibility UXPA by Stew Smith and Olivier Vroom
AI x Accessibility UXPA by Stew Smith and Olivier VroomAI x Accessibility UXPA by Stew Smith and Olivier Vroom
AI x Accessibility UXPA by Stew Smith and Olivier Vroom
UXPA Boston
 
Harmonizing Multi-Agent Intelligence | Open Data Science Conference | Gary Ar...
Harmonizing Multi-Agent Intelligence | Open Data Science Conference | Gary Ar...Harmonizing Multi-Agent Intelligence | Open Data Science Conference | Gary Ar...
Harmonizing Multi-Agent Intelligence | Open Data Science Conference | Gary Ar...
Gary Arora
 
Dark Dynamism: drones, dark factories and deurbanization
Dark Dynamism: drones, dark factories and deurbanizationDark Dynamism: drones, dark factories and deurbanization
Dark Dynamism: drones, dark factories and deurbanization
Jakub Šimek
 
ACE Aarhus - Team'25 wrap-up presentation
ACE Aarhus - Team'25 wrap-up presentationACE Aarhus - Team'25 wrap-up presentation
ACE Aarhus - Team'25 wrap-up presentation
DanielEriksen5
 
MEMS IC Substrate Technologies Guide 2025.pptx
MEMS IC Substrate Technologies Guide 2025.pptxMEMS IC Substrate Technologies Guide 2025.pptx
MEMS IC Substrate Technologies Guide 2025.pptx
IC substrate Shawn Wang
 
DNF 2.0 Implementations Challenges in Nepal
DNF 2.0 Implementations Challenges in NepalDNF 2.0 Implementations Challenges in Nepal
DNF 2.0 Implementations Challenges in Nepal
ICT Frame Magazine Pvt. Ltd.
 
machines-for-woodworking-shops-en-compressed.pdf
machines-for-woodworking-shops-en-compressed.pdfmachines-for-woodworking-shops-en-compressed.pdf
machines-for-woodworking-shops-en-compressed.pdf
AmirStern2
 
fennec fox optimization algorithm for optimal solution
fennec fox optimization algorithm for optimal solutionfennec fox optimization algorithm for optimal solution
fennec fox optimization algorithm for optimal solution
shallal2
 
DevOpsDays SLC - Platform Engineers are Product Managers.pptx
DevOpsDays SLC - Platform Engineers are Product Managers.pptxDevOpsDays SLC - Platform Engineers are Product Managers.pptx
DevOpsDays SLC - Platform Engineers are Product Managers.pptx
Justin Reock
 
Unlocking Generative AI in your Web Apps
Unlocking Generative AI in your Web AppsUnlocking Generative AI in your Web Apps
Unlocking Generative AI in your Web Apps
Maximiliano Firtman
 
AI-proof your career by Olivier Vroom and David WIlliamson
AI-proof your career by Olivier Vroom and David WIlliamsonAI-proof your career by Olivier Vroom and David WIlliamson
AI-proof your career by Olivier Vroom and David WIlliamson
UXPA Boston
 
Crazy Incentives and How They Kill Security. How Do You Turn the Wheel?
Crazy Incentives and How They Kill Security. How Do You Turn the Wheel?Crazy Incentives and How They Kill Security. How Do You Turn the Wheel?
Crazy Incentives and How They Kill Security. How Do You Turn the Wheel?
Christian Folini
 
Cybersecurity Tools and Technologies - Microsoft Certificate
Cybersecurity Tools and Technologies - Microsoft CertificateCybersecurity Tools and Technologies - Microsoft Certificate
Cybersecurity Tools and Technologies - Microsoft Certificate
VICTOR MAESTRE RAMIREZ
 
Top-AI-Based-Tools-for-Game-Developers (1).pptx
Top-AI-Based-Tools-for-Game-Developers (1).pptxTop-AI-Based-Tools-for-Game-Developers (1).pptx
Top-AI-Based-Tools-for-Game-Developers (1).pptx
BR Softech
 
RTP Over QUIC: An Interesting Opportunity Or Wasted Time?
RTP Over QUIC: An Interesting Opportunity Or Wasted Time?RTP Over QUIC: An Interesting Opportunity Or Wasted Time?
RTP Over QUIC: An Interesting Opportunity Or Wasted Time?
Lorenzo Miniero
 
MULTI-STAKEHOLDER CONSULTATION PROGRAM On Implementation of DNF 2.0 and Way F...
MULTI-STAKEHOLDER CONSULTATION PROGRAM On Implementation of DNF 2.0 and Way F...MULTI-STAKEHOLDER CONSULTATION PROGRAM On Implementation of DNF 2.0 and Way F...
MULTI-STAKEHOLDER CONSULTATION PROGRAM On Implementation of DNF 2.0 and Way F...
ICT Frame Magazine Pvt. Ltd.
 
ICDCC 2025: Securing Agentic AI - Eryk Budi Pratama.pdf
ICDCC 2025: Securing Agentic AI - Eryk Budi Pratama.pdfICDCC 2025: Securing Agentic AI - Eryk Budi Pratama.pdf
ICDCC 2025: Securing Agentic AI - Eryk Budi Pratama.pdf
Eryk Budi Pratama
 
Slack like a pro: strategies for 10x engineering teams
Slack like a pro: strategies for 10x engineering teamsSlack like a pro: strategies for 10x engineering teams
Slack like a pro: strategies for 10x engineering teams
Nacho Cougil
 
Build With AI - In Person Session Slides.pdf
Build With AI - In Person Session Slides.pdfBuild With AI - In Person Session Slides.pdf
Build With AI - In Person Session Slides.pdf
Google Developer Group - Harare
 
IT484 Cyber Forensics_Information Technology
IT484 Cyber Forensics_Information TechnologyIT484 Cyber Forensics_Information Technology
IT484 Cyber Forensics_Information Technology
SHEHABALYAMANI
 
AI x Accessibility UXPA by Stew Smith and Olivier Vroom
AI x Accessibility UXPA by Stew Smith and Olivier VroomAI x Accessibility UXPA by Stew Smith and Olivier Vroom
AI x Accessibility UXPA by Stew Smith and Olivier Vroom
UXPA Boston
 
Harmonizing Multi-Agent Intelligence | Open Data Science Conference | Gary Ar...
Harmonizing Multi-Agent Intelligence | Open Data Science Conference | Gary Ar...Harmonizing Multi-Agent Intelligence | Open Data Science Conference | Gary Ar...
Harmonizing Multi-Agent Intelligence | Open Data Science Conference | Gary Ar...
Gary Arora
 
Dark Dynamism: drones, dark factories and deurbanization
Dark Dynamism: drones, dark factories and deurbanizationDark Dynamism: drones, dark factories and deurbanization
Dark Dynamism: drones, dark factories and deurbanization
Jakub Šimek
 
ACE Aarhus - Team'25 wrap-up presentation
ACE Aarhus - Team'25 wrap-up presentationACE Aarhus - Team'25 wrap-up presentation
ACE Aarhus - Team'25 wrap-up presentation
DanielEriksen5
 
MEMS IC Substrate Technologies Guide 2025.pptx
MEMS IC Substrate Technologies Guide 2025.pptxMEMS IC Substrate Technologies Guide 2025.pptx
MEMS IC Substrate Technologies Guide 2025.pptx
IC substrate Shawn Wang
 
DNF 2.0 Implementations Challenges in Nepal
DNF 2.0 Implementations Challenges in NepalDNF 2.0 Implementations Challenges in Nepal
DNF 2.0 Implementations Challenges in Nepal
ICT Frame Magazine Pvt. Ltd.
 
machines-for-woodworking-shops-en-compressed.pdf
machines-for-woodworking-shops-en-compressed.pdfmachines-for-woodworking-shops-en-compressed.pdf
machines-for-woodworking-shops-en-compressed.pdf
AmirStern2
 
fennec fox optimization algorithm for optimal solution
fennec fox optimization algorithm for optimal solutionfennec fox optimization algorithm for optimal solution
fennec fox optimization algorithm for optimal solution
shallal2
 
DevOpsDays SLC - Platform Engineers are Product Managers.pptx
DevOpsDays SLC - Platform Engineers are Product Managers.pptxDevOpsDays SLC - Platform Engineers are Product Managers.pptx
DevOpsDays SLC - Platform Engineers are Product Managers.pptx
Justin Reock
 
Unlocking Generative AI in your Web Apps
Unlocking Generative AI in your Web AppsUnlocking Generative AI in your Web Apps
Unlocking Generative AI in your Web Apps
Maximiliano Firtman
 
AI-proof your career by Olivier Vroom and David WIlliamson
AI-proof your career by Olivier Vroom and David WIlliamsonAI-proof your career by Olivier Vroom and David WIlliamson
AI-proof your career by Olivier Vroom and David WIlliamson
UXPA Boston
 
Crazy Incentives and How They Kill Security. How Do You Turn the Wheel?
Crazy Incentives and How They Kill Security. How Do You Turn the Wheel?Crazy Incentives and How They Kill Security. How Do You Turn the Wheel?
Crazy Incentives and How They Kill Security. How Do You Turn the Wheel?
Christian Folini
 
Cybersecurity Tools and Technologies - Microsoft Certificate
Cybersecurity Tools and Technologies - Microsoft CertificateCybersecurity Tools and Technologies - Microsoft Certificate
Cybersecurity Tools and Technologies - Microsoft Certificate
VICTOR MAESTRE RAMIREZ
 
Top-AI-Based-Tools-for-Game-Developers (1).pptx
Top-AI-Based-Tools-for-Game-Developers (1).pptxTop-AI-Based-Tools-for-Game-Developers (1).pptx
Top-AI-Based-Tools-for-Game-Developers (1).pptx
BR Softech
 
RTP Over QUIC: An Interesting Opportunity Or Wasted Time?
RTP Over QUIC: An Interesting Opportunity Or Wasted Time?RTP Over QUIC: An Interesting Opportunity Or Wasted Time?
RTP Over QUIC: An Interesting Opportunity Or Wasted Time?
Lorenzo Miniero
 
MULTI-STAKEHOLDER CONSULTATION PROGRAM On Implementation of DNF 2.0 and Way F...
MULTI-STAKEHOLDER CONSULTATION PROGRAM On Implementation of DNF 2.0 and Way F...MULTI-STAKEHOLDER CONSULTATION PROGRAM On Implementation of DNF 2.0 and Way F...
MULTI-STAKEHOLDER CONSULTATION PROGRAM On Implementation of DNF 2.0 and Way F...
ICT Frame Magazine Pvt. Ltd.
 
ICDCC 2025: Securing Agentic AI - Eryk Budi Pratama.pdf
ICDCC 2025: Securing Agentic AI - Eryk Budi Pratama.pdfICDCC 2025: Securing Agentic AI - Eryk Budi Pratama.pdf
ICDCC 2025: Securing Agentic AI - Eryk Budi Pratama.pdf
Eryk Budi Pratama
 
Slack like a pro: strategies for 10x engineering teams
Slack like a pro: strategies for 10x engineering teamsSlack like a pro: strategies for 10x engineering teams
Slack like a pro: strategies for 10x engineering teams
Nacho Cougil
 
Build With AI - In Person Session Slides.pdf
Build With AI - In Person Session Slides.pdfBuild With AI - In Person Session Slides.pdf
Build With AI - In Person Session Slides.pdf
Google Developer Group - Harare
 
IT484 Cyber Forensics_Information Technology
IT484 Cyber Forensics_Information TechnologyIT484 Cyber Forensics_Information Technology
IT484 Cyber Forensics_Information Technology
SHEHABALYAMANI
 

05 ds and algorithm session_07

  • 1. Data Structures and Algorithms Objectives In this session, you will learn to: Identify the features of linked lists Implement a singly-linked list Ver. 1.0 Session 7
  • 2. Data Structures and Algorithms Linked List Suppose you have to write an algorithm to generate and store all prime numbers between 1 and 10,00,000 and display them. How will you solve this problem? Ver. 1.0 Session 7
  • 3. Data Structures and Algorithms Linked List (Contd.) Consider the following algorithm, which uses an array to solve this problem: 1. Set I = 0 2. Repeat step 3 varying N from 2 to 1000000 3. If N is a prime number a. Set A[I] = N // If N is prime store it in an array b. I = I + 1 • Repeat step 5 varying J from 0 to I-1 • Display A[J] // Display the prime numbers // stored in the array Ver. 1.0 Session 7
  • 4. Data Structures and Algorithms Linked List (Contd.) What is the problem in this algorithm? The number of prime numbers between 1 and 10,00,000 is not known. Since you are using an array to store the prime numbers, you need to declare an array of arbitrarily large size to store the prime numbers. Disadvantages of this approach, suppose you declare an array of size N: If the number of prime numbers between 1 and 10,00,000 is more than N then all the prime numbers cannot be stored. If the number of prime numbers is much less than N, a lot of memory space is wasted. Ver. 1.0 Session 7
  • 5. Data Structures and Algorithms Linked List (Contd.) • Thus, you cannot use an array to store a set of elements if you do not know the total number of elements in advance. • How do you solve this problem? By having some way in which you can allocate memory as and when it is required. Ver. 1.0 Session 7
  • 6. Data Structures and Algorithms Dynamic Memory Allocation • If you knowdeclare an array, a contiguous block ofarray you When you the address of the first element in the memory can calculate the address of any other elements as shown: is allocated. Let Address of theyou declare an array of size 10 to store first us suppose first element + (size of the element × index of the element) 10 prime numbers. 0 1000 1 1002 2 1004 One contiguous block of 3 1006 4 1008 memory allocated for 5 1010 the array to store 10 6 1012 7 1014 elements. 8 1016 9 1018 Memory representation Ver. 1.0 Session 7
  • 7. Data Structures and Algorithms Dynamic Memory Allocation (Contd.) When memory is allocated dynamically, a block of memory is assigned arbitrarily from any location in the memory. Therefore, unlike arrays, these blocks may not be contiguous and may be spread randomly in the memory. 0 1000 1 1002 2 1004 One contiguous block of 3 1006 4 1008 memory allocated for 5 1010 the array to store 10 6 1012 7 1014 elements. 8 1016 9 1018 Memory representation Ver. 1.0 Session 7
  • 8. Data Structures and Algorithms Dynamic Memory Allocation (Contd.) Let us see how this happens by allocating memory dynamically for the prime numbers. Allocate memory for 2 1002 2 Memory allocated for 2 Memory representation Ver. 1.0 Session 7
  • 9. Data Structures and Algorithms Dynamic Memory Allocation (Contd.) Let us see how this happens. Allocate memory for 3 1002 2 Memory allocated for 3 1036 3 Memory representation Ver. 1.0 Session 7
  • 10. Data Structures and Algorithms Dynamic Memory Allocation (Contd.) Let us see how this happens. Allocate memory for 5 1002 2 Memory allocated for 5 1008 5 1036 3 Memory representation Ver. 1.0 Session 7
  • 11. Data Structures and Algorithms Dynamic Memory Allocation (Contd.) Let us see how this happens. Allocate memory for 7 1002 2 Memory allocated for 7 1008 5 1020 7 1036 3 Memory representation Ver. 1.0 Session 7
  • 12. Data Structures and Algorithms Dynamic Memory Allocation (Contd.) Let us see how this happens. Allocate memory for 11 1002 2 Memory allocated for 11 1008 5 1020 7 1030 11 1036 3 Memory representation Ver. 1.0 Session 7
  • 13. Data Structures and Algorithms Dynamic Memory Allocation (Contd.) To access know the address of the know its address. Now, if youany element, you need to first element, you cannot calculate the address of the rest of the elements. This is because, all the elements are spread at random locations in the memory. 1002 2 1008 5 1020 7 1030 11 1036 3 Memory representation Ver. 1.0 Session 7
  • 14. Data Structures and Algorithms Dynamic Memory Allocation (Contd.) Therefore, it would be good if every allocated block of memory contains the address of the next block in sequence. This gives the list a linked structure where each block is linked to the next block in sequence. 1002 2 1036 1008 5 1020 1020 7 1030 1030 11 1036 3 1008 Memory representation Ver. 1.0 Session 7
  • 15. Data Structures and Algorithms Dynamic Memory Allocation (Contd.) An example of a a variable, START, that stores this concept You can declare data structure that implements the address is the first list. of a linked block. You can now begin at START and move through the list by following the links. START 2 1036 1002 1008 5 1020 1020 7 1030 1030 11 1036 3 1008 Memory representation Ver. 1.0 Session 7
  • 16. Data Structures and Algorithms Defining Linked Lists Linked list: Is a dynamic data structure. Allows memory to be allocated as and when it is required. Consists of a chain of elements, in which each element is referred to as a node. Ver. 1.0 Session 7
  • 17. Data Structures and Algorithms Defining Linked Lists (Contd.) A node is the basic building block of a linked list. A node consists of two parts: – Data: Refers to the information held by the node – Link: Holds the address of the next node in the list Data Link Node Ver. 1.0 Session 7
  • 18. Data Structures and Algorithms Defining Linked Lists (Contd.) The last node in a linked list does not point to any other All the nodes in a linked list are present at arbitrary memory node. Therefore, it points to NULL. locations. Therefore, every node in a linked list has link field that stores the address of the next node in sequence. NULL 10 Data 3352 10 Data 5689 10 Data 1012 10 Data 2403 3352 5689 1012 Ver. 1.0 Session 7
  • 19. Data Structures and Algorithms Defining Linked Lists (Contd.) To keep track of the first node, declare a variable/pointer, START, which always points to the first node. When the list is empty, START contains null. NULL START 10 Data 3352 10 Data 5689 10 Data 1012 10 Data 2403 3352 5689 1012 Ver. 1.0 Session 7
  • 20. Data Structures and Algorithms Implementing a Singly-Linked List Let us solve the given problem of storing prime numbers using a linked list. 1. Repeat step 2 varying N from 2 to 1000000. 2. If N is a prime number, insert it in the linked list: a. Allocate memory for a new node. b. Store the prime number in the new node. c. Attach the new node in the linked list. 3. Display the prime numbers stored in the linked list. Ver. 1.0 Session 7
  • 21. Data Structures and Algorithms Inserting a Node in a Singly-Linked List • Consider the following linked list that stores prime numbers. START 2 3 5 7 • When a new prime number is generated, it should be inserted at the end of the list. • Initially, when the list is empty, START contains NULL. Ver. 1.0 Session 7
  • 22. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. Consider the given algorithm to 3. Assign value to the data field of the new node. insert a node in a linked list. 5. If START is NULL, then: a. Make START point to the new node. b. Go to step 6. 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the following steps: a. Mark the first node as currentNode. b. Repeat step c until the successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 23. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. START = that the list is initially Consider NULL 3. Assign value to the data field of the new node. empty. Insert a prime number 2. 5. If START is NULL, then: a. Make START point to the new node. b. Go to step 6. 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the following steps: a. Mark the first node as currentNode. b. Repeat step c until the successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 24. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. START = NULL • Assign value to the data field of the new node. Insert a prime number 2. • If START is NULL, then: a. Make START point to the new node. b. Go to step 6. 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the following steps: a. Mark the first node as currentNode. b. Repeat step c until the successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 25. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. START = NULL • Assign value to the data field of the new node. • If START is NULL, then: a. Make START point to the new node. b. Go to step 6. 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 following steps: a. Mark the first node as currentNode. b. Repeat step c until the successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 26. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. START = NULL • Assign value to the data field of the new node. • If START is NULL, then: a. Make START point to the new node. b. Go to step 6. 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 following steps: a. Mark the first node as currentNode. b. Repeat step c until the successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 27. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. START = NULL 3. Assign value to the data field of the new node. 5. If START is NULL, then: • Make START point to the new node. • Go to step 6. START 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 following steps: a. Mark the first node as currentNode. b. Repeat step c until the successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 28. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then: • Make START point to the new node. • Go to step 6. START • Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 following steps: a. Mark the first node as currentNode. b. Repeat step c until the successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 29. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then: a. Make START point to the new node. b. Go to step 6. START 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 following steps: a. Mark the first node as currentNode. b. Repeat step c until the successor of currentNode Insertion complete becomes NULL. c. Make currentNode point to the next node in sequence. • Make the next field of currentNode point to the new node. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 30. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. Insert a prime number 3. 3. Assign value to the data field of the new node. 5. If START is NULL, then: a. Make START point to the new node. b. Go to step 6. START 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 following steps: a. Mark the first node as currentNode. b. Repeat step c until the successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 31. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. • Insert a prime number 3. • Assign value to the data field of the new node. • If START is NULL, then: a. Make START point to the new node. b. Go to step 6. START 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 following steps: a. Mark the first node as currentNode. b. Repeat step c until the successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 32. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. • Assign value to the data field of the new node. • If START is NULL, then: a. Make START point to the new node. b. Go to step 6. START 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 3 10 following steps: a. Mark the first node as currentNode. b. Repeat step c until the successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 33. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. • Assign value to the data field of the new node. • If START is NULL, then: a. Make START point to the new node. b. Go to step 6. START 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 3 10 following steps: a. Mark the first node as currentNode. b. Repeat step c until the successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 34. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then: a. Make START point to the new node. b. Go to step 6. START • Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 3 10 following steps: a. Mark the first node as currentNode. b. Repeat step c until the successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 35. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then: a. Make START point to the new node. b. Go to step 6. START 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 3 10 following steps: • Mark the first node as currentNode. • Repeat step c until the currentNode successor of currentNode becomes NULL. • Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 36. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then: a. Make START point to the new node. b. Go to step 6. START 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 3 10 following steps: • Mark the first node as currentNode. • Repeat step c until the currentNode successor of currentNode becomes NULL. • Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 37. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then: a. Make START point to the new node. b. Go to step 6. START 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 3 10 following steps: a. Mark the first node as currentNode. b. Repeat step c until the currentNode successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. • Make the next field of currentNode point to the new node. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 38. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then: a. Make START point to the new node. b. Go to step 6. START 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 3 10 following steps: a. Mark the first node as currentNode. b. Repeat step c until the currentNode successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. Insertion complete • Make the next field of currentNode point to the new node. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 39. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. • Insert a prime number 5. 3. Assign value to the data field of the new node. 5. If START is NULL, then: a. Make START point to the new node. b. Go to step 6. START 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 3 10 following steps: a. Mark the first node as currentNode. b. Repeat step c until the currentNode successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 40. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. Insert a prime number 5. • Assign value to the data field of the new node. • If START is NULL, then: a. Make START point to the new node. b. Go to step 6. START 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 3 10 following steps: a. Mark the first node as currentNode. b. Repeat step c until the successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 41. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. • Assign value to the data field of the new node. • If START is NULL, then: a. Make START point to the new node. b. Go to step 6. START 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 3 10 5 10 following steps: a. Mark the first node as currentNode. b. Repeat step c until the successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 42. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. • Assign value to the data field of the new node. • If START is NULL, then: a. Make START point to the new node. b. Go to step 6. START 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 3 10 5 10 following steps: a. Mark the first node as currentNode. b. Repeat step c until the successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 43. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then: a. Make START point to the new node. b. Go to step 6. START • Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 3 10 5 10 following steps: a. Mark the first node as currentNode. b. Repeat step c until the successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 44. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then: a. Make START point to the new node. b. Go to step 6. START 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 3 10 5 10 following steps: • Mark the first node as currentNode. • Repeat step c until the currentNode successor of currentNode becomes NULL. • Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 45. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then: a. Make START point to the new node. b. Go to step 6. START 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 3 10 5 10 following steps: • Mark the first node as currentNode. • Repeat step c until the currentNode successor of currentNode becomes NULL. • Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 46. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then: a. Make START point to the new node. b. Go to step 6. START 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 3 10 5 10 following steps: • Mark the first node as currentNode. • Repeat step c until the currentNodecurrentNode successor of currentNode becomes NULL. • Make currentNode point to the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 47. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then: a. Make START point to the new node. b. Go to step 6. START 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 3 10 5 10 following steps: a. Mark the first node as currentNode. b. Repeat step c until the currentNode successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. • Make the next field of currentNode point to the new node. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 48. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then: a. Make START point to the new node. b. Go to step 6. START 7. Locate the last node in the list, and mark it as currentNode. To locate the last node in the list, execute the 2 10 3 10 5 10 following steps: a. Mark the first node as currentNode. b. Repeat step c until the currentNode successor of currentNode becomes NULL. c. Make currentNode point to the next node in sequence. Insertion complete • Make the next field of currentNode point to the new node. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 49. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. What is thea better approach is to Therefore, problem with this 3. Assign value to the data field of the new node. algorithm?variable, LAST, which declare a 5. If START is NULL, then: will Consider a address of the last store the list of 10000 numbers. a. Make START point to the node in the a number at the end of To insert list. new node. b. Go to step 6. the list, you first need to locate the Hence, you need to maintain two 7. Locate the last node in the list, and variables, STARTlist. LAST, to last node in the and mark it as currentNode. To locate To reach the last node, you have keep track of the first and last the last node in the list, execute the following steps: to start from the first node and nodes in the list respectively. a. Mark the first node as visit all the preceding nodes currentNode. If the list is empty, START node. before you reach the last and b. Repeat step c until the successor of currentNode LAST point to NULL. becomes NULL. This approach is very time c. Make currentNode point to consuming for lengthy lists. the next node in sequence. 8. Make the next field of currentNode point to the new node. 10. Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 50. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. Refer to the given algorithm to 3. Assign value to the data field of the new node. insert a node at the end of the 5. If START is NULL, then (If the list is linked list. empty): a. Make START point to the new node. b. Make LAST point to the new node. c. Go to step 6. • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 51. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. START = NULL Consider that the list is initially 3. Assign value to the data field of the new node. empty. NULL LAST = 5. If START is NULL, then (If the list is Insert a prime number 2. empty): a. Make START point to the new node. b. Make LAST point to the new node. c. Go to step 6. • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 52. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. START = NULL • Assign value to the data field of the new node. LAST = NULL • If START is NULL, then (If the list is Insert a prime number 2. empty): a. Make START point to the new node. b. Make LAST point to the new node. c. Go to step 6. • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 53. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. START = NULL • Assign value to the data field of the new node. LAST = NULL • If START is NULL, then (If the list is empty): a. Make START point to the new node. b. Make LAST point to the new node. c. Go to step 6. 2 10 • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 54. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. START = NULL • Assign value to the data field of the new node. LAST = NULL • If START is NULL, then (If the list is empty): a. Make START point to the new node. b. Make LAST point to the new node. c. Go to step 6. 2 10 • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 55. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. START = NULL 3. Assign value to the data field of the new node. LAST = NULL 5. If START is NULL, then (If the list is empty): • Make START point to the new node. START • Make LAST point to the new node. • Go to step 6. 2 10 • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 56. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. LAST = NULL 5. If START is NULL, then (If the list is empty): • Make START point to the new node. START LAST • Make LAST point to the new node. • Go to step 6. 2 10 • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 57. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then (If the list is empty): • Make START point to the new node. START LAST • Make LAST point to the new node. • Go to step 6. 2 10 • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 58. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then (If the list is empty): a. Make START point to the new node. START LAST b. Make LAST point to the new node. c. Go to step 6. 2 10 • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node Insertion complete point to NULL. Ver. 1.0 Session 7
  • 59. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. Insert a prime number 3. 3. Assign value to the data field of the new node. 5. If START is NULL, then (If the list is empty): a. Make START point to the new node. START LAST b. Make LAST point to the new node. c. Go to step 6. 2 10 • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 60. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. Insert a prime number 3. • Assign value to the data field of the new node. • If START is NULL, then (If the list is empty): a. Make START point to the new node. START LAST b. Make LAST point to the new node. c. Go to step 6. 2 10 • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 61. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. • Assign value to the data field of the new node. • If START is NULL, then (If the list is empty): a. Make START point to the new node. START LAST b. Make LAST point to the new node. c. Go to step 6. 2 10 3 10 • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 62. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. • Assign value to the data field of the new node. • If START is NULL, then (If the list is empty): a. Make START point to the new node. START LAST b. Make LAST point to the new node. c. Go to step 6. 2 10 3 10 • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 63. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then (If the list is empty): a. Make START point to the new node. START LAST b. Make LAST point to the new node. c. Go to step 6. 2 10 3 10 • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 64. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then (If the list is empty): a. Make START point to the new node. START LAST LAST b. Make LAST point to the new node. c. Go to step 6. 2 10 3 10 • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 65. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then (If the list is empty): a. Make START point to the new node. START LAST b. Make LAST point to the new node. c. Go to step 6. 2 10 3 10 • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node Insertion complete point to NULL. Ver. 1.0 Session 7
  • 66. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. Insert a prime number 5. 3. Assign value to the data field of the new node. 5. If START is NULL, then (If the list is empty): a. Make START point to the new node. START LAST b. Make LAST point to the new node. c. Go to step 6. 2 10 3 10 • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 67. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. Insert a prime number 5. • Assign value to the data field of the new node. • If START is NULL, then (If the list is empty): a. Make START point to the new node. START LAST b. Make LAST point to the new node. c. Go to step 6. 2 10 3 10 • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 68. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. • Assign value to the data field of the new node. • If START is NULL, then (If the list is empty): a. Make START point to the new node. START LAST b. Make LAST point to the new node. c. Go to step 6. 2 10 3 10 5 10 • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 69. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. • Assign value to the data field of the new node. • If START is NULL, then (If the list is empty): a. Make START point to the new node. START LAST b. Make LAST point to the new node. c. Go to step 6. 2 10 3 10 5 10 • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 70. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then (If the list is empty): a. Make START point to the new node. START LAST b. Make LAST point to the new node. c. Go to step 6. 2 10 3 10 5 10 • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 71. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then (If the list is empty): a. Make START point to the new node. START LAST LAST b. Make LAST point to the new node. c. Go to step 6. 2 10 3 10 5 10 • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node point to NULL. Ver. 1.0 Session 7
  • 72. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. 3. Assign value to the data field of the new node. 5. If START is NULL, then (If the list is empty): a. Make START point to the new node. START LAST b. Make LAST point to the new node. c. Go to step 6. 2 10 3 10 5 10 • Make the next field of LAST point to the new node. • Mark the new node as LAST. • Make the next field of the new node Insertion complete point to NULL. Ver. 1.0 Session 7
  • 73. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) Now consider another problem. Suppose you have to store the marks of 20 students in the ascending order. How will you solve this problem? Ver. 1.0 Session 7
  • 74. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) Consider the following algorithm, which uses an array to solve this problem. 1. Set N = 0 // Number of marks entered 2. Repeat until N = 20 a. Accept marks. b. Locate position I where the marks must be inserted. c. For J = N – 1 down to I Move A[J] to A[J+1] // Move elements to make // place for the new element d. Set A[I] = marks e. N = N + 1 Ver. 1.0 Session 7
  • 75. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 Let us perform some insert 2. Repeat until N = 20 • Accept marks. operations in the array by placing the • Locate position I where elements at their appropriate the marks must be inserted positions to get a sorted list. • For J = N-1 down to I Move A[J] to A[J+1] d. Set A[I] = marks e. N=N+1 0 1 2 3 4… …19 Ver. 1.0 Session 7
  • 76. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Set N = 0 Let us perform some insert operations • Repeat until N = 20 • Accept marks in the array by placing the elements at • Locate position I where their appropriate positions to get a the marks must be inserted sorted list. • For J = N-1 down to I Move A[J] to A[J+1] d. Set A[I] = marks e. N=N+1 10 0 1 2 3 4… …19 N=0 Ver. 1.0 Session 7
  • 77. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Set N = 0 • Repeat until N = 20 a. Accept marks b. Locate position I where the marks must be inserted c. For J = N-1 down to I Move A[J] to A[J+1] d. Set A[I] = marks e. N=N+1 10 0 1 2 3 4… …19 N=0 Ver. 1.0 Session 7
  • 78. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 10 • Accept marks • Locate position I where the marks must be inserted • For J = N-1 down to I Move A[J] to A[J+1] d. Set A[I] = marks e. N=N+1 10 0 1 2 3 4… …19 N=0 Ver. 1.0 Session 7
  • 79. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 10 • Accept marks • Locate position I where I=0 the marks must be inserted • For J = N-1 down to I Move A[J] to A[J+1] I d. Set A[I] = marks e. N=N+1 10 0 1 2 3 4… …19 N=0 Ver. 1.0 Session 7
  • 80. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 10 • Accept marks • Locate position I where I=0 the marks must be inserted • For J = N-1 down to I Move A[J] to A[J+1] I d. Set A[I] = marks e. N=N+1 10 0 1 2 3 4… …19 N=0 Ver. 1.0 Session 7
  • 81. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 10 • Accept marks • Locate position I where I=0 the marks must be inserted • For J = N-1 down to I Move A[J] to A[J+1] I • Set A[I] = marks • N=N+1 10 10 0 1 2 3 4… …19 N=0 Ver. 1.0 Session 7
  • 82. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 • Accept marks • Locate position I where I=0 the marks must be inserted • For J = N-1 down to I Move A[J] to A[J+1] I • Set A[I] = marks • N=N+1 10 10 0 1 2 3 4… …19 N=0 Ver. 1.0 Session 7
  • 83. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 • Accept marks • Locate position I where I=0 the marks must be inserted • For J = N-1 down to I Move A[J] to A[J+1] I • Set A[I] = marks • N=N+1 10 10 0 1 2 3 4… …19 N=1 Ver. 1.0 Session 7
  • 84. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 20 • Accept marks • Locate position I where I=0 the marks must be inserted • For J = N-1 down to I Move A[J] to A[J+1] I d. Set A[I] = marks e. N=N+1 10 10 0 1 2 3 4… …19 N=1 Ver. 1.0 Session 7
  • 85. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 20 • Accept marks • Locate position I where 0 I=1 the marks must be inserted • For J = N-1 down to I Move A[J] to A[J+1] I I d. Set A[I] = marks e. N=N+1 10 10 0 1 2 3 4… …19 N=1 Ver. 1.0 Session 7
  • 86. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 20 • Accept marks • Locate position I where I=1 the marks must be inserted • For J = N-1 down to I Move A[J] to A[J+1] I d. Set A[I] = marks e. N=N+1 10 10 0 1 2 3 4… …19 N=1 Ver. 1.0 Session 7
  • 87. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 20 • Accept marks • Locate position I where I=1 the marks must be inserted • For J = N-1 down to I Move A[J] to A[J+1] I • Set A[I] = marks • N=N+1 10 20 10 0 1 2 3 4… …19 N=1 Ver. 1.0 Session 7
  • 88. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 • Accept marks • Locate position I where I=1 the marks must be inserted • For J = N-1 down to I Move A[J] to A[J+1] I • Set A[I] = marks • N=N+1 10 20 10 0 1 2 3 4… …19 N=1 Ver. 1.0 Session 7
  • 89. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 • Accept marks • Locate position I where I=1 the marks must be inserted • For J = N-1 down to I Move A[J] to A[J+1] I • Set A[I] = marks • N=N+1 10 20 10 0 1 2 3 4… …19 N=2 Ver. 1.0 Session 7
  • 90. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 17 • Accept marks • Locate position I where I=1 the marks must be inserted • For J = N-1 down to I Move A[J] to A[J+1] I d. Set A[I] = marks e. N=N+1 10 20 10 0 1 2 3 4… …19 N=2 Ver. 1.0 Session 7
  • 91. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 17 • Accept marks • Locate position I where I=1 the marks must be inserted • For J = N-1 down to I I Move A[J] to A[J+1] d. Set A[I] = marks e. N=N+1 10 20 10 0 1 2 3 4… …19 N=2 Ver. 1.0 Session 7
  • 92. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 17 • Accept marks • Locate position I where I=1 the marks must be inserted J=1 • For J = N-1 down to I I Move A[J] to A[J+1] d. Set A[I] = marks e. N=N+1 10 20 10 0 1 2 3 4… …19 N=2 Ver. 1.0 Session 7
  • 93. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 17 • Accept marks • Locate position I where I=1 the marks must be inserted J=1 • For J = N-1 down to I I Move A[J] to A[J+1] d. Set A[I] = marks e. N=N+1 10 20 10 0 1 2 3 4… …19 N=2 Ver. 1.0 Session 7
  • 94. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 17 a. Accept marks b. Locate position I where I=1 the marks must be inserted J=1 c. For J = N-1 down to I I Move A[J] to A[J+1] d. Set A[I] = marks e. N=N+1 10 20 10 20 0 1 2 3 4… …19 N=2 Ver. 1.0 Session 7
  • 95. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 17 a. Accept marks b. Locate position I where I=1 the marks must be inserted J=1 c. For J = N-1 down to I I Move A[J] to A[J+1] • Set A[I] = marks • N=N+1 10 17 10 20 0 1 2 3 4… …19 N=2 Ver. 1.0 Session 7
  • 96. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 a. Accept marks b. Locate position I where I=1 the marks must be inserted c. For J = N-1 down to I I Move A[J] to A[J+1] • Set A[I] = marks • N=N+1 10 17 10 20 0 1 2 3 4… …19 N=3 Ver. 1.0 Session 7
  • 97. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 15 • Accept marks • Locate position I where the marks must be inserted • For J = N-1 down to I Move A[J] to A[J+1] d. Set A[I] = marks e. N=N+1 10 17 10 20 0 1 2 3 4… …19 N=3 Ver. 1.0 Session 7
  • 98. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 15 • Accept marks • Locate position I where I=1 the marks must be inserted • For J = N-1 down to I I Move A[J] to A[J+1] d. Set A[I] = marks e. N=N+1 10 17 10 20 0 1 2 3 4… …19 N=3 Ver. 1.0 Session 7
  • 99. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 15 • Accept marks • Locate position I where I=1 the marks must be inserted J=2 • For J = N-1 down to I I Move A[J] to A[J+1] d. Set A[I] = marks e. N=N+1 10 17 10 20 0 1 2 3 4… …19 N=3 Ver. 1.0 Session 7
  • 100. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 15 a. Accept marks b. Locate position I where I=1 the marks must be inserted J=2 c. For J = N-1 down to I I Move A[J] to A[J+1] d. Set A[I] = marks e. N=N+1 10 17 10 20 0 1 2 3 4… …19 N=3 Ver. 1.0 Session 7
  • 101. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 15 a. Accept marks b. Locate position I where I=1 the marks must be inserted J=2 c. For J = N-1 down to I I Move A[J] to A[J+1] d. Set A[I] = marks e. N=N+1 10 17 10 20 20 0 1 2 3 4… …19 N=3 Ver. 1.0 Session 7
  • 102. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 15 • Accept marks • Locate position I where I=1 the marks must be inserted J=1 • For J = N-1 down to I I Move A[J] to A[J+1] d. Set A[I] = marks e. N=N+1 10 17 10 20 0 1 2 3 4… …19 N=3 Ver. 1.0 Session 7
  • 103. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 15 a. Accept marks b. Locate position I where I=1 the marks must be inserted J=1 c. For J = N-1 down to I I Move A[J] to A[J+1] d. Set A[I] = marks e. N=N+1 10 17 10 20 0 1 2 3 4… …19 N=3 Ver. 1.0 Session 7
  • 104. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 15 a. Accept marks b. Locate position I where I=1 the marks must be inserted J=1 c. For J = N-1 down to I I Move A[J] to A[J+1] d. Set A[I] = marks e. N=N+1 10 17 10 17 20 0 1 2 3 4… …19 N=3 Ver. 1.0 Session 7
  • 105. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 marks = 15 a. Accept marks b. Locate position I where I=1 the marks must be inserted J=1 c. For J = N-1 down to I I Move A[J] to A[J+1] • Set A[I] = marks • N=N+1 10 15 10 17 20 0 1 2 3 4… …19 N=3 Ver. 1.0 Session 7
  • 106. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Set N = 0 2. Repeat until N = 20 a. Accept marks b. Locate position I where I=1 the marks must be inserted J=1 c. For J = N-1 down to I I Move A[J] to A[J+1] • Set A[I] = marks • N=N+1 10 15 10 17 20 0 1 2 3 4… …19 N=4 Ver. 1.0 Session 7
  • 107. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) What the preceding example we conclude that insertion and From is the problem in this algorithm? deletion at any element at any position other thanan arrayof the To insert an position other than the end of the end is complex and inefficient. overhead of shifting all succeeding list, there is an additional How can you overcome forward. elements one position this limitation? By using a data structure that does not requireother than the Similarly, to delete an element at any position shifting of data elements after you need to shift the operation. elements one end of the list, every insert / delete succeeding position backwards. A linked list offers this flexibility. When the list is very large, this would be very time consuming. Ver. 1.0 Session 7
  • 108. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) Consider a linked list that stores the marks of students in an ascending order. Insert marks (17). 17 should be inserted after 15. 20 1002 10 1011 START 25 1020 15 2496 10 2496 15 1002 20 1020 25 NULL Memory representation Ver. 1.0 Session 7
  • 109. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) Allocate memory for 17. 20 1002 10 1011 Memory allocated for 17 17 1008 17 START 25 1020 15 2496 10 2496 15 1002 20 1020 25 NULL 10 10 10 10 Memory representation Ver. 1.0 Session 7
  • 110. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) In the given list, node 15 contains the address of node 20. To add node 17 after node 15, you need to update the address field of node 15 so that it now contains the address of node 17. 20 1002 10 1011 Memory allocated for 17 17 1008 17 START 25 1020 15 2496 10 2496 15 1002 20 1020 25 NULL 10 10 10 10 Memory representation Ver. 1.0 Session 7
  • 111. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) Update the address field of node 15 to store the address of node 17. 20 1002 10 1011 17 1008 17 START 25 1020 17 15 2496 10 2496 15 1002 20 1020 25 NULL 10 10 10 10 Memory representation Ver. 1.0 Session 7
  • 112. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) Update the address field of node 15 to store the address of node 17. 20 1002 10 1011 17 1008 START 25 1020 17 15 2496 10 2496 1008 15 1002 20 1020 25 NULL 10 10 10 10 Updating the address field Memory representation Ver. 1.0 Session 7
  • 113. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) Store the address of node 20 in the address field of node 17 to make a complete list. 20 1002 10 1011 Node Inserted 17 1008 START 25 1020 17 1002 15 2496 10 2496 15 1008 20 1020 10 25 NULL 10 10 Address updated Memory representation Ver. 1.0 Session 7
  • 114. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) Now, let us solve the given problem using a linked list. Suppose the linked list currently contains the following elements. START 10 15 17 20 The linked list needs to be created in the ascending order of values. Therefore, the position of a new node in the list will be determined by the value contained in the new node. Ver. 1.0 Session 7
  • 115. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) Write an algorithm to locate the position of the new node to be inserted in a linked list, where the nodes need to be stored in the increasing order of the values contained in them. Ver. 1.0 Session 7
  • 116. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Make current point to the first node. Algorithm for locating the position 2. Make previous point to NULL. of a new node in the linked list. 3. Repeat step 4 and step 5 until current.info becomes greater than the After executing this algorithm the newnode.info or current becomes equal to NULL. variables/pointers previous and 4. Make previous point to current. current will be placed on the 5. Make current point to the next node in nodes between which the new sequence. node is to be inserted. Ver. 1.0 Session 7
  • 117. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Make current point to the first node. Insert 16 in the given list. 2. Make previous point to NULL. 3. Repeat step 4 and step 5 until current.info becomes greater than the newnode.info or current becomes equal to NULL. 4. Make previous point to current. 5. Make current point to the next node in START sequence. 10 15 17 20 Ver. 1.0 Session 7
  • 118. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Make current point to the first node. Insert 16 in the given list. • Make previous point to NULL. • Repeat step 4 and step 5 until current.info becomes greater than the newnode.info or current becomes equal to NULL. • Make previous point to current. • Make current point to the next node in START sequence. 10 10 15 17 20 current Ver. 1.0 Session 7
  • 119. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Make current point to the first node. • Make previous point to NULL. • Repeat step 4 and step 5 until current.info becomes greater than the newnode.info or current becomes equal to NULL. • Make previous point to current. • Make current point to the next node in START sequence. 10 10 15 17 20 current previous = NULL Ver. 1.0 Session 7
  • 120. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Make current point to the first node. • Make previous point to NULL. • Repeat step 4 and step 5 until current.info becomes greater than the newnode.info or current becomes equal to NULL. • Make previous point to current. • Make current point to the next node in START sequence. 10 10 15 17 20 current previous = NULL Ver. 1.0 Session 7
  • 121. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Make current point to the first node. • Make previous point to NULL. • Repeat step 4 and step 5 until current.info becomes greater than the newnode.info or current becomes equal to NULL. • Make previous point to current. • Make current point to the next node in START sequence. 10 10 15 17 20 previous current previous = NULL Ver. 1.0 Session 7
  • 122. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Make current point to the first node. • Make previous point to NULL. • Repeat step 4 and step 5 until current.info becomes greater than the newnode.info or current becomes equal to NULL. • Make previous point to current. • Make current point to the next node in START sequence. 10 10 15 17 20 previous current current Ver. 1.0 Session 7
  • 123. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Make current point to the first node. • Make previous point to NULL. • Repeat step 4 and step 5 until current.info becomes greater than the newnode.info or current becomes equal to NULL. • Make previous point to current. • Make current point to the next node in START sequence. 10 10 15 17 20 previous current Ver. 1.0 Session 7
  • 124. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Make current point to the first node. • Make previous point to NULL. • Repeat step 4 and step 5 until current.info becomes greater than the newnode.info or current becomes equal to NULL. • Make previous point to current. • Make current point to the next node in START sequence. 10 10 15 17 20 previous previous current Ver. 1.0 Session 7
  • 125. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Make current point to the first node. • Make previous point to NULL. • Repeat step 4 and step 5 until current.info becomes greater than the newnode.info or current becomes equal to NULL. • Make previous point to current. • Make current point to the next node in START sequence. 10 10 15 17 20 previous current current Ver. 1.0 Session 7
  • 126. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Make current point to the first node. • Make previous point to NULL. • Repeat step 4 and step 5 until current.info becomes greater than the newnode.info or current becomes equal to NULL. • Make previous point to current. • Make current point to the next node in START sequence. 10 10 15 17 20 previous current Node located Ver. 1.0 Session 7
  • 127. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) Once the position of the new node has been determined, the new node can be inserted in the linked list. A new node can be inserted at any of the following positions in the list: Beginning of the list End of the list Between two nodes in the list Ver. 1.0 Session 7
  • 128. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) Write an algorithm to insert a node in the beginning of a linked list. Ver. 1.0 Session 7
  • 129. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Allocate memory for the new node. Algorithm to insert a node in the 3. Assign value to the data field of beginning of a linked list the new node. 5. Make the next field of the new node point to the first node in the list. 7. Make START, point to the new START node. 10 15 17 20 Ver. 1.0 Session 7
  • 130. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. Insert 7 • Assign value to the data field of the new node. newnode • Make the next field of the new node point to the first node in the list. • Make START, point to the new START node. 10 10 15 17 20 Ver. 1.0 Session 7
  • 131. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. Insert 7 • Assign value to the data field of the new node. newnode • Make the next field of the new node point to the first node in the list. • Make START, point to the new 7 START node. 10 10 15 17 20 Ver. 1.0 Session 7
  • 132. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. • Assign value to the data field of the new node. newnode • Make the next field of the new node point to the first node in the list. • Make START, point to the new 7 START node. 10 10 15 17 20 newnode. next = START Ver. 1.0 Session 7
  • 133. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) • Allocate memory for the new node. • Assign value to the data field of the new node. newnode • Make the next field of the new node point to the first node in the list. • Make START, point to the new 7 START node. 10 10 15 17 20 Insertion complete newnode. next = START START = newnode Ver. 1.0 Session 7
  • 134. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) Write an algorithm to insert a node between two nodes in a linked list. Ver. 1.0 Session 7
  • 135. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Identify the nodes between which the new node is to be inserted. Mark them Insert 16 Algorithm to insert a node between as previous and current. To locate previous and current, execute the two nodes in a linked list. following steps: a. Make current point to the first node. START b. Make previous point to NULL. c. Repeat step d and step e until current.info becomes greater than newnode.info or current 10 15 17 20 becomes equal to NULL. d. Make previous point to current. e. Make current point to the next node in sequence. 3. Allocate memory for the new node. 5. Assign value to the data field of the new node. 7. Make the next field of the new node point to current. 9. Make the next field of previous point to the new node. Ver. 1.0 Session 7
  • 136. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Identify the nodes between which the new node is to be inserted. Mark them Insert 16 as previous and current. To locate previous and current, execute the following steps: a. Make current point to the first node. START b. Make previous point to NULL. c. Repeat step d and step e until current.info becomes greater than newnode.info or current 10 10 15 17 20 becomes equal to NULL. d. Make previous point to current. e. Make current point to the next node in sequence. 3. Allocate memory for the new node. 5. Assign value to the data field of the new node. 7. Make the next field of the new node point to current. 9. Make the next field of previous point to the new node. Ver. 1.0 Session 7
  • 137. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Identify the nodes between which the new node is to be inserted. Mark them Insert 16 as previous and current. To locate previous and current, execute the following steps: • Make current point to the first node. START • Make previous point to NULL. • Repeat step d and step e until current.info becomes greater than newnode.info or current 10 10 15 17 20 becomes equal to NULL. • Make previous point to current. • Make current point to the next node in sequence. current 3. Allocate memory for the new node. 5. Assign value to the data field of the new node. 7. Make the next field of the new node point to current. 9. Make the next field of previous point to the new node. Ver. 1.0 Session 7
  • 138. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Identify the nodes between which the new node is to be inserted. Mark them Insert 16 as previous and current. To locate previous and current, execute the following steps: • Make current point to the first node. START • Make previous point to NULL. • Repeat step d and step e until current.info becomes greater than newnode.info or current 10 10 15 17 20 becomes equal to NULL. • Make previous point to current. • Make current point to the next node in sequence. current 3. Allocate memory for the new node. previous = NULL 5. Assign value to the data field of the new node. 7. Make the next field of the new node point to current. 9. Make the next field of previous point to the new node. Ver. 1.0 Session 7
  • 139. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Identify the nodes between which the new node is to be inserted. Mark them Insert 16 as previous and current. To locate previous and current, execute the following steps: • Make current point to the first node. START • Make previous point to NULL. • Repeat step d and step e until current.info becomes greater than newnode.info or current 10 10 15 17 20 becomes equal to NULL. • Make previous point to current. • Make current point to the next node in sequence. current 3. Allocate memory for the new node. previous = NULL 5. Assign value to the data field of the new node. 7. Make the next field of the new node point to current. 9. Make the next field of previous point to the new node. Ver. 1.0 Session 7
  • 140. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Identify the nodes between which the new node is to be inserted. Mark them Insert 16 as previous and current. To locate previous and current, execute the following steps: • Make current point to the first node. START • Make previous point to NULL. • Repeat step d and step e until current.info becomes greater than newnode.info or current 10 10 15 17 20 becomes equal to NULL. • Make previous point to current. • Make current point to the next node in sequence. previous current 3. Allocate memory for the new node. previous = NULL 5. Assign value to the data field of the new node. 7. Make the next field of the new node point to current. 9. Make the next field of previous point to the new node. Ver. 1.0 Session 7
  • 141. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Identify the nodes between which the new node is to be inserted. Mark them Insert 16 as previous and current. To locate previous and current, execute the following steps: • Make current point to the first node. START • Make previous point to NULL. • Repeat step d and step e until current.info becomes greater than newnode.info or current 10 10 15 17 20 becomes equal to NULL. • Make previous point to current. • Make current point to the next node in sequence. previous current current 3. Allocate memory for the new node. 5. Assign value to the data field of the new node. 7. Make the next field of the new node point to current. 9. Make the next field of previous point to the new node. Ver. 1.0 Session 7
  • 142. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Identify the nodes between which the new node is to be inserted. Mark them Insert 16 as previous and current. To locate previous and current, execute the following steps: • Make current point to the first node. START • Make previous point to NULL. • Repeat step d and step e until current.info becomes greater than newnode.info or current 10 10 15 17 20 becomes equal to NULL. • Make previous point to current. • Make current point to the next node in sequence. previous current 3. Allocate memory for the new node. 5. Assign value to the data field of the new node. 7. Make the next field of the new node point to current. 9. Make the next field of previous point to the new node. Ver. 1.0 Session 7
  • 143. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Identify the nodes between which the new node is to be inserted. Mark them Insert 16 as previous and current. To locate previous and current, execute the following steps: • Make current point to the first node. START • Make previous point to NULL. • Repeat step d and step e until current.info becomes greater than newnode.info or current 10 10 15 17 20 becomes equal to NULL. • Make previous point to current. • Make current point to the next node in sequence. previous previous current 3. Allocate memory for the new node. 5. Assign value to the data field of the new node. 7. Make the next field of the new node point to current. 9. Make the next field of previous point to the new node. Ver. 1.0 Session 7
  • 144. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Identify the nodes between which the new node is to be inserted. Mark them Insert 16 as previous and current. To locate previous and current, execute the following steps: • Make current point to the first node. START • Make previous point to NULL. • Repeat step d and step e until current.info becomes greater than newnode.info or current 10 10 15 17 20 becomes equal to NULL. • Make previous point to current. • Make current point to the next node in sequence. previous currentcurrent 3. Allocate memory for the new node. 5. Assign value to the data field of the new node. 7. Make the next field of the new node point to current. 9. Make the next field of previous point to the new node. Ver. 1.0 Session 7
  • 145. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Identify the nodes between which the new node is to be inserted. Mark them Insert 16 as previous and current. To locate previous and current, execute the following steps: • Make current point to the first node. START • Make previous point to NULL. • Repeat step d and step e until current.info becomes greater than newnode.info or current 10 10 15 17 20 becomes equal to NULL. • Make previous point to current. • Make current point to the next node in sequence. previous current 3. Allocate memory for the new node. Nodes located 5. Assign value to the data field of the new node. 7. Make the next field of the new node point to current. 9. Make the next field of previous point to the new node. Ver. 1.0 Session 7
  • 146. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Identify the nodes between which the newnode new node is to be inserted. Mark them as previous and current. To locate previous and current, execute the following steps: a. Make current point to the first node. START b. Make previous point to NULL. c. Repeat step d and step e until current.info becomes greater than newnode.info or current 10 10 15 17 20 becomes equal to NULL. d. Make previous point to current. e. Make current point to the next node in sequence. previous current • Allocate memory for the new node. Nodes located • Assign value to the data field of the new node. • Make the next field of the new node point to current. • Make the next field of previous point to the new node. Ver. 1.0 Session 7
  • 147. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Identify the nodes between which the newnode new node is to be inserted. Mark them as previous and current. To locate previous and current, execute the following steps: a. Make current point to the first 16 node. START b. Make previous point to NULL. c. Repeat step d and step e until current.info becomes greater than newnode.info or current 10 10 15 17 20 becomes equal to NULL. d. Make previous point to current. e. Make current point to the next node in sequence. previous current • Allocate memory for the new node. • Assign value to the data field of the new node. • Make the next field of the new node point to current. • Make the next field of previous point to the new node. Ver. 1.0 Session 7
  • 148. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Identify the nodes between which the newnode new node is to be inserted. Mark them as previous and current. To locate previous and current, execute the following steps: a. Make current point to the first 16 node. START b. Make previous point to NULL. c. Repeat step d and step e until current.info becomes greater than newnode.info or current 10 10 15 17 20 becomes equal to NULL. d. Make previous point to current. e. Make current point to the next node in sequence. previous current • Allocate memory for the new node. • Assign value to the data field of the new node. newnode.next = current • Make the next field of the new node point to current. • Make the next field of previous point to the new node. Ver. 1.0 Session 7
  • 149. Data Structures and Algorithms Inserting a Node in a Singly-Linked List (Contd.) 1. Identify the nodes between which the newnode new node is to be inserted. Mark them as previous and current. To locate previous and current, execute the following steps: a. Make current point to the first 16 node. START b. Make previous point to NULL. c. Repeat step d and step e until current.info becomes greater than newnode.info or current 10 10 15 17 20 becomes equal to NULL. d. Make previous point to current. e. Make current point to the next node in sequence. previous current • Allocate memory for the new node. • Assign value to the data field of the new node. newnode.next = current • Make the next field of the new node point to current. previous.next = newnode • Make the next field of previous point to the new node. Insertion complete Ver. 1.0 Session 7
  • 150. Data Structures and Algorithms Traversing a Singly-Linked List 1. Make currentNode point to the first node in the list. Algorithm for traversing a linked singly-linked list. Write an algorithm to traverse a list. 3. Repeat step 3 and 4 until currentNode becomes NULL. 5. Display the information contained in the node marked as currentNode. START 7. Make currentNode point to the next node in sequence. 2 3 5 7 Ver. 1.0 Session 7
  • 151. Data Structures and Algorithms Traversing a Singly-Linked List (Contd.) • Make currentNode point to the first node in the list. Refer to the algorithm to display the • Repeat step 3 and 4 until elements in the linked list. currentNode becomes NULL. • Display the information contained in the node marked as currentNode. START • Make currentNode point to the next node in sequence. 2 10 3 10 5 10 7 10 currentNode Ver. 1.0 Session 7
  • 152. Data Structures and Algorithms Traversing a Singly-Linked List (Contd.) • Make currentNode point to the first node in the list. • Repeat step 3 and 4 until currentNode becomes NULL. • Display the information contained in the node marked as currentNode. START • Make currentNode point to the next node in sequence. 2 10 3 10 5 10 7 10 currentNode Ver. 1.0 Session 7
  • 153. Data Structures and Algorithms Traversing a Singly-Linked List (Contd.) • Make currentNode point to the first node in the list. • Repeat step 3 and 4 until currentNode becomes NULL. • Display the information contained in the node marked as currentNode. START • Make currentNode point to the next node in sequence. 2 10 3 10 5 10 7 10 currentNode 2 Ver. 1.0 Session 7
  • 154. Data Structures and Algorithms Traversing a Singly-Linked List (Contd.) • Make currentNode point to the first node in the list. • Repeat step 3 and 4 until currentNode becomes NULL. • Display the information contained in the node marked as currentNode. START • Make currentNode point to the next node in sequence. 2 10 3 10 5 10 7 10 currentNode currentNode 2 Ver. 1.0 Session 7
  • 155. Data Structures and Algorithms Traversing a Singly-Linked List (Contd.) • Make currentNode point to the first node in the list. • Repeat step 3 and 4 until currentNode becomes NULL. • Display the information contained in the node marked as currentNode. START • Make currentNode point to the next node in sequence. 2 10 3 10 5 10 7 10 currentNode 2 Ver. 1.0 Session 7
  • 156. Data Structures and Algorithms Traversing a Singly-Linked List (Contd.) • Make currentNode point to the first node in the list. • Repeat step 3 and 4 until currentNode becomes NULL. • Display the information contained in the node marked as currentNode. START • Make currentNode point to the next node in sequence. 2 10 3 10 5 10 7 10 currentNode 2 3 Ver. 1.0 Session 7
  • 157. Data Structures and Algorithms Traversing a Singly-Linked List (Contd.) • Make currentNode point to the first node in the list. • Repeat step 3 and 4 until currentNode becomes NULL. • Display the information contained in the node marked as currentNode. START • Make currentNode point to the next node in sequence. 2 10 3 10 5 10 7 10 currentNode currentNode 2 3 Ver. 1.0 Session 7
  • 158. Data Structures and Algorithms Traversing a Singly-Linked List (Contd.) • Make currentNode point to the first node in the list. • Repeat step 3 and 4 until currentNode becomes NULL. • Display the information contained in the node marked as currentNode. START • Make currentNode point to the next node in sequence. 2 10 3 10 5 10 7 10 currentNode 2 3 Ver. 1.0 Session 7
  • 159. Data Structures and Algorithms Traversing a Singly-Linked List (Contd.) • Make currentNode point to the first node in the list. • Repeat step 3 and 4 until currentNode becomes NULL. • Display the information contained in the node marked as currentNode. START • Make currentNode point to the next node in sequence. 2 10 3 10 5 10 7 10 currentNode 2 3 5 Ver. 1.0 Session 7
  • 160. Data Structures and Algorithms Traversing a Singly-Linked List (Contd.) • Make currentNode point to the first node in the list. • Repeat step 3 and 4 until currentNode becomes NULL. • Display the information contained in the node marked as currentNode. START • Make currentNode point to the next node in sequence. 2 10 3 10 5 10 7 10 currentNode currentNode 2 3 5 Ver. 1.0 Session 7
  • 161. Data Structures and Algorithms Traversing a Singly-Linked List (Contd.) • Make currentNode point to the first node in the list. • Repeat step 3 and 4 until currentNode becomes NULL. • Display the information contained in the node marked as currentNode. START • Make currentNode point to the next node in sequence. 2 10 3 10 5 10 7 10 currentNode 2 3 5 Ver. 1.0 Session 7
  • 162. Data Structures and Algorithms Traversing a Singly-Linked List (Contd.) • Make currentNode point to the first node in the list. • Repeat step 3 and 4 until currentNode becomes NULL. • Display the information contained in the node marked as currentNode. START • Make currentNode point to the next node in sequence. 2 10 3 10 5 10 7 10 currentNode 2 3 5 7 Ver. 1.0 Session 7
  • 163. Data Structures and Algorithms Traversing a Singly-Linked List (Contd.) • Make currentNode point to the first node in the list. • Repeat step 3 and 4 until currentNode becomes NULL. • Display the information contained in the node marked as currentNode. START • Make currentNode point to the next node in sequence. 2 10 3 10 5 10 7 10 currentNode currentNode = NULL 2 3 5 7 Ver. 1.0 Session 7
  • 164. Data Structures and Algorithms Traversing a Singly-Linked List (Contd.) • Make currentNode point to the first node in the list. • Repeat step 3 and 4 until currentNode becomes NULL. • Display the information contained in the node marked as currentNode. START • Make currentNode point to the next node in sequence. 2 10 3 10 5 10 7 10 currentNode = NULL 2 3 5 7 Traversal complete Ver. 1.0 Session 7
  • 165. Data Structures and Algorithms Deleting a Node from a Singly-Linked List Delete operation in a linked list refers to the process of removing a specified node from the list. You can delete a node from the following places in a linked list: Beginning of the list Between two nodes in the list End of the list Ver. 1.0 Session 7
  • 166. Data Structures and Algorithms Deleting a Node From the Beginning of the List Write an algorithm to delete the first node in a linked list. Ver. 1.0 Session 7
  • 167. Data Structures and Algorithms Deleting a Node From the Beginning of the List (Contd.) 1. Mark the first node in the list Algorithm to delete a node from the as current. beginning of a linked list. 3. Make START point to the next node in its sequence. START 5. Release the memory for the node marked as current. 10 15 17 20 Ver. 1.0 Session 7
  • 168. Data Structures and Algorithms Deleting a Node From the Beginning of a Linked List (Contd.) • Mark the first node in the list as current. • Make START point to the next node in its sequence. START • Release the memory for the node marked as current. 10 10 15 17 20 current current = START Ver. 1.0 Session 7
  • 169. Data Structures and Algorithms Deleting a Node From the Beginning of a Linked List (Contd.) • Mark the first node in the list as current. • Make START point to the next node in its sequence. START START • Release the memory for the node marked as current. 10 10 15 17 20 current current = START START = START. next Ver. 1.0 Session 7
  • 170. Data Structures and Algorithms Deleting a Node From the Beginning of a Linked List (Contd.) • Mark the first node in the list as current. • Make START point to the next node in its sequence. START • Release the memory for the node marked as current. 10 15 17 20 current Memory released current = START START = START. next Delete operation complete Ver. 1.0 Session 7
  • 171. Data Structures and Algorithms Deleting a Node Between two Nodes in the List Write an algorithm to delete a node between two nodes in a linked list. Ver. 1.0 Session 7
  • 172. Data Structures and Algorithms Deleting a Node Between two Nodes in the List (Contd.) 1. Locate the node to be deleted. Mark the node to be deleted as current and its Algorithm to delete a node Delete 17 predecessor as previous. To locate between two nodes in the list. current and previous, execute the following steps: a. Set previous = START b. Set current = START START c. Repeat step d and e until either the node is found or current becomes NULL. d. Make previous point to 10 15 17 20 current . e. Make current point to the next node in sequence. 3. Make the next field of previous point to the successor of current. 5. Release the memory for the node marked as current. Ver. 1.0 Session 7
  • 173. Data Structures and Algorithms Deleting a Node Between two Nodes in the List (Contd.) 1. Locate the node to be deleted. Mark the node to be deleted as current and its Delete 17 predecessor as previous. To locate current and previous, execute the following steps: a. Set previous = START b. Set current = START START c. Repeat step d and e until either the node is found or current becomes NULL. d. Make previous point to 10 10 15 17 20 current. e. Make current point to the next node in sequence. 3. Make the next field of previous point to the successor of current. 5. Release the memory for the node marked as current. Ver. 1.0 Session 7
  • 174. Data Structures and Algorithms Deleting a Node Between two Nodes in the List (Contd.) • Locate the node to be deleted. Mark the node to be deleted as current and its Delete 17 predecessor as previous. To locate current and previous, execute the following steps: • Set previous = START • Set current = START START • Repeat step d and e until either the node is found or current becomes NULL. • Make previous point to 10 10 15 17 20 • current. Make current point to the next node in sequence. 3. Make the next field of previous point to previous the successor of current. 5. Release the memory for the node marked as current. Ver. 1.0 Session 7
  • 175. Data Structures and Algorithms Deleting a Node Between two Nodes in the List (Contd.) 1. Locate the node to be deleted. Mark the node to be deleted as current and its Delete 17 predecessor as previous. To locate current and previous, execute the following steps: • Set previous = START • Set current = START START • Repeat step d and e until either the node is found or current becomes NULL. • Make previous point to 10 10 15 17 20 • current. Make current point to the next node in sequence. 3. Make the next field of previous point to previous current the successor of current. 5. Release the memory for the node marked as current. Ver. 1.0 Session 7
  • 176. Data Structures and Algorithms Deleting a Node Between two Nodes in the List (Contd.) 1. Locate the node to be deleted. Mark the node to be deleted as current and its Delete 17 predecessor as previous. To locate current and previous, execute the following steps: • Set previous = START • Set current = START START • Repeat step d and e until either the node is found or current becomes NULL. • Make previous point to 10 10 15 17 20 • current. Make current point to the next node in sequence. 3. Make the next field of previous point to previous current the successor of current. 5. Release the memory for the node marked as current. Ver. 1.0 Session 7
  • 177. Data Structures and Algorithms Deleting a Node Between two Nodes in the List (Contd.) 1. Locate the node to be deleted. Mark the node to be deleted as current and its Delete 17 predecessor as previous. To locate current and previous, execute the following steps: • Set previous = START • Set current = START START • Repeat step d and e until either the node is found or current becomes NULL. • Make previous point to 10 10 15 17 20 • current. Make current point to the next node in sequence. 3. Make the next field of previous point to previous current the successor of current. 5. Release the memory for the node marked as current. Ver. 1.0 Session 7
  • 178. Data Structures and Algorithms Deleting a Node Between two Nodes in the List (Contd.) 1. Locate the node to be deleted. Mark the node to be deleted as current and its Delete 17 predecessor as previous. To locate current and previous, execute the following steps: • Set previous = START • Set current = START START • Repeat step d and e until either the node is found or current becomes NULL. • Make previous point to 10 10 15 17 20 • current. Make current point to the next node in sequence. • Make the next field of previous point to previous current current the successor of current. • Release the memory for the node marked as current. Ver. 1.0 Session 7
  • 179. Data Structures and Algorithms Deleting a Node Between two Nodes in the List (Contd.) 1. Locate the node to be deleted. Mark the node to be deleted as current and its Delete 17 predecessor as previous. To locate current and previous, execute the following steps: • Set previous = START • Set current = START START • Repeat step d and e until either the node is found or current becomes NULL. • Make previous point to 10 10 15 17 20 • current. Make current point to the next node in sequence. 3. Make the next field of previous point to previous current the successor of current. 5. Release the memory for the node marked as current. Ver. 1.0 Session 7
  • 180. Data Structures and Algorithms Deleting a Node Between two Nodes in the List (Contd.) 1. Locate the node to be deleted. Mark the node to be deleted as current and its Delete 17 predecessor as previous. To locate current and previous, execute the following steps: • Set previous = START • Set current = START START • Repeat step d and e until either the node is found or current becomes NULL. • Make previous point to 10 10 15 17 20 • current. Make current point to the next node in sequence. 3. Make the next field of previous point to previous previous current the successor of current. 5. Release the memory for the node marked as current. Ver. 1.0 Session 7
  • 181. Data Structures and Algorithms Deleting a Node Between two Nodes in the List (Contd.) 1. Locate the node to be deleted. Mark the node to be deleted as current and its Delete 17 predecessor as previous. To locate current and previous, execute the following steps: • Set previous = START • Set current = START START • Repeat step d and e until either the node is found or current becomes NULL. • Make previous point to 10 10 15 17 20 • current. Make current point to the next node in sequence. • Make the next field of previous point to previous current current the successor of current. • Release the memory for the node marked as current. Ver. 1.0 Session 7
  • 182. Data Structures and Algorithms Deleting a Node Between two Nodes in the List (Contd.) 1. Locate the node to be deleted. Mark the node to be deleted as current and its Delete 17 predecessor as previous. To locate current and previous, execute the following steps: • Set previous = START • Set current = START START • Repeat step d and e until either the node is found or current becomes NULL. • Make previous point to 10 10 15 17 20 • current. Make current point to the next node in sequence. 3. Make the next field of previous point to previous current the successor of current. 5. Release the memory for the node marked as current. Ver. 1.0 Session 7
  • 183. Data Structures and Algorithms Deleting a Node Between two Nodes in the List (Contd.) 1. Locate the node to be deleted. Mark the node to be deleted as current and its Delete 17 predecessor as previous. To locate current and previous, execute the following steps: a. Set previous = START b. Set current = START START c. Repeat step d and e until either the node is found or current becomes NULL. d. Make previous point to 10 10 15 17 20 current. e. Make current point to the next node in sequence. • Make the next field of previous point to previous current the successor of current. • Release the memory for the node marked as current. previous.next = current.next Ver. 1.0 Session 7
  • 184. Data Structures and Algorithms Deleting a Node Between two Nodes in the List (Contd.) 1. Locate the node to be deleted. Mark the node to be deleted as current and its Delete 17 predecessor as previous. To locate current and previous, execute the following steps: Delete operation complete a. Set previous = START b. Set current = START START c. Repeat step d and e until either the node is found or current becomes NULL. d. Make previous point to 10 10 15 17 20 current. e. Make current point to the next node in sequence. • Make the next field of previous point to previous current the successor of current. • Release the memory for the node marked as current. previous.next = current.next Ver. 1.0 Session 7
  • 185. Data Structures and Algorithms Group Discussion Problem Statement – Discuss the advantages and disadvantages of linked lists. Ver. 1.0 Session 7
  • 186. Data Structures and Algorithms Group Discussion (Contd.) Problem Statement Discuss the differences between arrays and linked lists. Ver. 1.0 Session 7
  • 187. Data Structures and Algorithms Just a minute Linked lists allow _________ access to elements. Answer: sequential Ver. 1.0 Session 7
  • 188. Data Structures and Algorithms Representing a Singly-Linked List A Linked list is represented in a program by defining two classes: – Node class: This class contains the data members of varying data types, which represent data to be stored in a linked list. It also contains the reference of the class type (Node) to hold the reference of the next node in sequence. // Code in C#: class Node { public int data; public Node next; // Variable containing // the address of the // next node in // sequence } Ver. 1.0 Session 7
  • 189. Data Structures and Algorithms Representing a Singly-Linked List (Contd.) // Code in C++ class Node { public: int data; Node *next; // Pointer to the // next node in // sequence }; Ver. 1.0 Session 7
  • 190. Data Structures and Algorithms Representing a Singly-Linked List (Contd.) List class: This class consists of a set of operations implemented on a linked list. These operations are insertion, deletion, search, and traversal. It also contains the declaration of a variable/pointer, START that always points to the first node in the list. // Code in C#: class Node { public int data; public Node next; // Variable containing // the address of the // next node in // sequence } Ver. 1.0 Session 7
  • 191. Data Structures and Algorithms Representing a Singly-Linked List (Contd.) // Code in C#: class List { private Node START; List() { START = NULL; } public void addNode(int element){} public bool search(int element, ref Node previous, ref Node current) {} public bool delNode(int element) {} public void traverse() {} } Ver. 1.0 Session 7
  • 192. Data Structures and Algorithms Representing a Singly-Linked List (Contd.) // Code in C#: class List { Node * START; public: List() { START = NULL; } void addNode(int element); bool search(int element, Node *previous, Node *current); bool delNode(int element); void traverse(); }; Ver. 1.0 Session 7
  • 193. Data Structures and Algorithms Activity: Implementing a Singly-Linked List Problem Statement: Write a program to implement insert, search, delete, and traverse operations on a singly-linked list that stores the records of the students in a class. Each record holds the following information: – Roll number of the student – Name of the student Ver. 1.0 Session 7
  • 194. Data Structures and Algorithms Summary In this session, you learned that: In a singly-linked list, each node contains: – The information – The address of the next node in the list – Singly-linked list can be traversed only in a single direction. – Insertion and deletion in a linked list is fast as compared to arrays. However, accessing elements is faster in arrays as compared to linked lists. Ver. 1.0 Session 7

Editor's Notes

  • #20: The students might misinterpret START as a separate node in the list. To avoid any such confusion, faculty should make it clear that START is just a variable (and not a node) that stores the address of the first node in the list. For example, in the graphics shown in the current slide, START contains 2403, which the address of the first node of the list.
  • #22: Tell the students that in C++, you need to declare a pointer variable to store the address of an object. However, in C#, you do not need to use a pointer to store the address of a variable. This is because in C#, reference variables can be used to store the address of an object. The name of these reference variables implicitly store the address of an object. Tell the students that in C++, you need to declare a pointer variable to store the address of an object. However, in C#, you do not need to use a pointer to store the address of a variable. This is because in C#, reference variables can be used to store the address of an object. The name of these reference variables implicitly store the address of an object.
  • #23: Before explaining the algorithm for any of the operations on a linked list, ask the students write the algorithm first.
  • #108: Various programming languages, such as Java, offer dynamic arrays where you can increase the size of the array if required. However, these arrays are actually not dynamic. This is because whenever the size of the array needs to be increased, the runtime creates a new array with more space and copies the elements into the new array.
  • #127: Tell the students that after search operation, if current = NULL, then it means that the new node will be inserted at the end of the list. Similarly, if previous = NULL, then the new node will be inserted in the beginning of the list.
  • #168: Explain the difference between the delete operation in a linked list in C# and C++.
  • #171: Explain the difference between the delete operation in a linked list in C# and C++. While explaining the “Release memory” step in the given algorithm, explain that in C# you do not need to explicitly release the memory. This is done automatically by garbage collector. Ask the student: Will the same algorithm work when the node to be deleted is the only node in the list? Explain that in that case when you execute the statement “Make START point to the next node in its sequence”, the next part of the node marked as START will be NULL. Therefore, START will be made to point to NULL to indicate that the list is empty.
  • #186: Tell the students that till this point, they have learnt about singly-linked list in which every node holds the address of the next node in sequence
  • #194: In this activity, you need to write a program to implement insert, search, delete, and traverse operations on a singly-linked list that stores the records of the students in a class. Each record holds the following information: Roll number of the student Name of the student You can use a data file provided to you, instead of typing the complete code. The data file that stores the complete program is stored at the given location: TIRM  Datafiles for Faculty  Chapter 05  Activities  SinglyLinkedList_CSharp.txt TIRM  Datafiles for Faculty  Chapter 05  Activities  SinglyLinkedList_C++.txt Also explain the program to students.
  翻译：