DSA MIDTERM PDF

Data Structures and Algorithms Jenneth R. Mondez  Table of Contents Module 5: Recursion Introduction 60 Learning Outcomes 60 Lesson 1: Definition...

Data Structures and Algorithms Jenneth R. Mondez  Table of Contents Module 5: Recursion Introduction 60 Learning Outcomes 60 Lesson 1: Definition 61 Lesson 2: Types of Recursion 62 Lesson 3: Structure of Recursive Implementations 63 Lesson 4: Simple Recursive Functions 64 Factorial Function 64 Fibonacci Numbers 66 Recursive Binary Search 68 Lesson 5: Common Mistakes in Recursive Implementations 70 Assessment Tasks 70 Summary 71 References 72 Module 6: Linked List Introduction 74 Learning Outcomes 74 Lesson 1: Definition 75 Lesson 2: Singly Linked List 76 Insert 77 Delete 83 Lesson 3: Doubly Linked List 88 Insert 89 Delete 93 Lesson 4: Circular Linked List 96 Assessment Tasks 97 Summary 99 References 99 Module 7: Stacks Introduction 102 Learning Outcomes 102 Lesson 1: Definition 103 Lesson 2: Basic Operations 104 Lesson 3: Java Stack Class 108 Lesson 4: Application of Stacks 117 Assessment Tasks 118 Summary 119 References 120  List of Figures Figure Description 5.1 Fractal patterns in nature 61 5.2 An illustration of Indirect Recursion 63 5.3 Tracing the Recursive Factorial Function 65 5.4 Tracing the Recursive Fibonacci function 68 6.1 Linked list representation 75 6.2 A new node is to be inserted in the list 77 6.3 The pointer field of Node B points to Node C 77 6.4 The pointer field of the left node points to the new node 78 6.5 List after inserting the new node 78 6.6 The target node for deletion is the middle item 83 6.7 The pointer field of the previous (left) node points to the right node of the target 84 6.8 The dotted line indicates that the link of the target node to the right node is removed 84 6.9 The list after deleting the target node 84 6.10 Structure of a doubly linked list 88 6.11 Illustration of a doubly linked list with three (3) nodes 89 6.12 Singly Linked List as Circular 97 6.13 Doubly Linked List as Circular 97 7.1 Stack of Cards and Stack of Plates 103 7.2 Representation of Operations in Stack 104 7.3 Push operations in stack 105 7.4 Stack after performing Pop operations 105 7.5 Empty stack 106 7.6 Stack after the three (3) elements are pushed 107 7.7 Stack after the Pop operation 107 List of Tables Table Description 5.1 Factorials 64 5.2 Fibonacci Numbers 66 7.1 Top Value and its Meaning 108 7.2 Methods in Java Stack Class 109  MODULE 5 RECURSION Introduction A natural way to solve problems which involves repetition structures is through the use of loops. This is also true for accessing a linear list called arrays since its elements are access through its index. Alternatively, the use of loops can be replaced by a process called recursion, an important technique in the study of data structures and algorithms. This is also applicable in a non-linear list where there is no index for each element. Just like a loop, a recursive procedure may call itself n times but at a certain point, it should stop since any algorithm must be finite. In this section, you will be able to learn and analyze the concepts of recursion, its components, how does it works, how to create a recursive procedure and apply it to solve problems in real-life situations. Learning Outcomes At the end of the lesson, the student is expected to: 1. Define recursion; 2. Identify the different types of recursion; 3. Recognize the parts of a recursive function; 4. Familiarize with the common mistakes in a recursive implementations; and 5. Develop solutions using recursion. Lesson 1. Definition According to Hubbard (2007), a recursive function is one that calls itself. This powerful technique produces repetition without using loops (e.g., while loops or for loops). Thus it can produce substantial results from very little code. Recursion allows elegantly simple solutions to difficult problems. But it can also be misused, producing inefficient code. Recursive code is usually produced from recursive algorithms. As stated by Goodrich et al. (2014), recursion is a technique by which a method makes one or more calls to itself during execution, or by which a data structure relies upon smaller instances of the very same type of structure in its representation. There are many examples of recursion in art and nature. For example, fractal patterns are naturally recursive. Figure 5.1 Fractal patterns in nature (www.seekpng.com, n.d.) A physical example of recursion used in art is in the Russian Matryoshka dolls. Each doll is either made of solid wood, or is hollow and contains another Matryoshka doll inside it. In computing, recursion provides an elegant and powerful alternative for performing repetitive tasks. In fact, a few programming languages (e.g., Scheme, Smalltalk) do not explicitly support looping constructs and instead rely directly on recursion to express repetition. Most modern programming languages support functional recursion using the identical mechanism that is used to support traditional forms of method calls. When one invocation of the method makes 61 a recursive call, that invocation is suspended until the recursive call completes (Goodrich et al., 2014). Lesson 2. Types of Recursion As explained by Rout (2020), recursion are mainly of two types depending on whether a function calls itself from within itself or more than one function call one another mutually. The first one is called direct recursion and another one is called indirect recursion. Thus, the two types of recursion are: 1. Direct Recursion The function directly calls itself. These can be further categorized into four types: a. Tail Recursion If a function calls itself and that recursive call is the last statement in the function then it is known as Tail Recursion. After that call the recursive function performs nothing. The function has to process or perform any operation at the time of calling and it does nothing at returning time. b. Head Recursion If a function calls itself and that recursive call is the first statement in the function then it is known as Head Recursion. There is no statement, no operation before the call. The function does not have to process or perform any operation at the time of calling and all operations are done at returning time. c. Tree Recursion To understand Tree Recursion let us first understand Linear Recursion. If a recursive function calls itself for one time then it is known as Linear Recursion. Otherwise if a recursive function calls itself for more than one time then it is known as Tree Recursion. 62  d. Nested Recursion In this recursion, a recursive function will pass the parameter as a recursive call that means “recursion inside recursion”. 2. Indirect Recursion In this recursion, there may be more than one functions and they are calling one another in a circular manner. Figure 5.2 An illustration of Indirect Recursion (Rout, 2020) Lesson 3. Structure of Recursive Implementations (Amarasinghe et al., n.d.) A recursive implementation always has two parts: 1. Base case, which is the simplest, smallest instance of the problem, that cannot be decomposed any further. Base cases often correspond to emptiness – the empty string, the empty list, the empty set, the empty tree, zero, etc. 2. Recursive step, which decomposes a larger instance of the problem into one or more simpler or smaller instances that can be solved by recursive calls, and then recombines the results of those subproblems to produce the solution to the original problem. It is important for the recursive step to transform the problem instance into something smaller, otherwise the recursion may never end. If every recursive step shrinks the problem, 63 and the base case lies at the bottom, then the recursion is guaranteed to be finite. A recursive implementation may have more than one base case, or more than one recursive step. Lesson 4. Simple Recursive Functions (Hubbard, 2007) Example 1. The Factorial Function The factorial function is defined mathematically by, This is a recursive definition because the factorial “recurs” on the right side of the equation. The function is defined in terms of itself. The first 10 values of the factorial function are shown in Table 5.1. Table 5.1 Factorials (Hubbard, 2007) n n! 0 1 1 1 2 2 3 6 4 24 5 120 The first value 0! Is defines as 0! = 1 (for n = 0), the rest of the values are defined as follows: For n = 1, 1! = n! = n(n – 1)! = 1(1 – 1)! = 1(0)! = 1(1) = 1. For n = 2, 2! = n! = n(n – 1)! = 2(2 – 1)! = 2(1)! = 2(1) = 2. For n = 3, 3! = n! = n(n – 1)! = 3(3 – 1)! = 3(2)! = 3(2) = 6. For n = 4, 4! = n! = n(n – 1)! = 4(4 – 1)! = 4(3)! = 4(6) = 24. For n = 5, 5! = n! = n(n – 1)! = 5(5 – 1)! = 5(4)! = 5(24) = 120. Notice how rapidly this function grows. Recursive Implementation of the Factorial Function When a function is defined recursively, its implementation is usually a direct translation of its recursive definition. The two parts of the recursive definition of the factorial function translate directly into two Java statements: 64  class Demo { public static int factorial(int n) { if (n==0) { return 1; // base case } Recursive Function return n*factorial(n-1); // recursive step } public static void main(String[] args) { for (int n=0; n hi) return -1; // base case int i = (lo + hi)/2; if (a[i] == x) return i; else if (a[i] < x) return search(a, i+1, hi, x); //recursive step else return search(a, lo, i-1, x); //recursive step } public static void print(int[] a) { System.out.printf("{%d", a); for (int i = 1; i < a.length; i++) System.out.printf(", %d", a[i]); System.out.println("}"); } public static void main(String[] args) { int[] a = {22, 33, 44, 55, 66, 77, 88, 99}; print(a); System.out.println("search(a, 44): " + search(a, 44)); System.out.println("search(a, 50): " + search(a, 50)); System.out.println("search(a, 77): " + search(a, 77)); System.out.println("search(a, 100): " + search(a, 100)); } } 69 Output: {22, 33, 44, 55, 66, 77, 88, 99} search(a, 44): 2 search(a, 50): -1 search(a, 77): 5 search(a, 100): -1 The search() method returns the index of the target x: search(a, 44) returns 2 because a = 44 and search(a, 77) returns 5 because a = 77. The method returns –1 when the target is not in the array: search(a, 50) and search(a, 100) returns –1 because 50 and 100 are not in the array. Lesson 5. Common Mistakes in Recursive Implementations (Amarasinghe et al., n.d.) The two common ways that a recursive implementation can go wrong are as follows: 1. The base case is missing entirely, or the problem needs more than one base case but not all the base cases are covered. 2. The recursive step does not reduce to a smaller subproblem, so the recursion does not converge. If you encountered a logic error or a run-time error in your code, check the cases mentioned above as these may be the cause why you are having bugs in your code. Assessment Tasks Direction: In a separate sheet of paper, answer the following items. 1. A recursive function has a base case and a recursive step. Using your own words, explain the function of these parts in a recursive implementation. 2. Using the recursive factorial function in Example 1, how many recursive calls will the call factorial(10) generate? 3. Consider the recursive function below and answer the questions that follows. (Malik & Nair, 2012) 70  public static int Mystery (int number) { if (number ==0) return number; else return (number + Mystery (number -1) } a. Identify the base case. b. Identify the recursive step. c. What valid values can be passed as parameters to the method Mystery? d. If Mystery(0) is a valid call, what is its value? If not valid, explain why. e. If Mystery(5) is a valid call, what is its value? If not valid, explain why. f. If Mystery(-3) is a valid call, what is its value? If not valid, explain why. Summary  A recursive function is one that calls itself. It is a technique by which a method makes one or more calls to itself during execution, or by which a data structure relies upon smaller instances of the very same type of structure in its representation.  The two (2) types of recursion are direct and indirect recursion.  In direct recursion, the function directly calls itself and has four (4) categories: tail, head, tree and nested recursion.  In indirect recursion, there may be more than one functions and they are calling one another in a circular manner.  If a function calls itself and that recursive call is the last statement in the function then it is known as tail recursion. 71   If a function calls itself and that recursive call is the first statement in the function then it is known as head recursion.  If a recursive function calls itself for one time then it is known as linear recursion.  If a recursive function calls itself for more than one time then it is known as tree recursion.  Nested recursion means “recursion inside recursion”.  A recursive implementation always has two parts: base case bad recursive step.  Base case is the simplest, smallest instance of the problem that cannot be decomposed any further.  Recursive step decomposes a larger instance of the problem into one or simpler or smaller instances that can be solved by recursive calls, and then recombines the results of those subproblems to produce the solution to the original problem. References Amarasinghe, S., Chlipala, A., Devadas, S., Ernst, M., Go Amarasinghe, S., Chlipala, A., Devadas, S., Ernst, M., Goldman, M., Jackson, D., Guttag, J., Miller, R., Rinard, M., & Solar-Lezama, A. (n.d.). Reading 14: Recursion. Retrieved from web.mit.edu: https://web.mit.edu/6.005/www/fa16/classes/14-recursion/; https://creativecommons.org/licenses/by-sa/4.0/ Goodrich, M. T., Tamassia, R., & Goldwasser, M. H. (2014). Data Structures and Algorithms in Java (Sixth Edition). John Wiley & Sons, Inc. Retrieved from https://www.pdfdrive.com/data-structures-and-algorithms-in-java-d18731618.html Hubbard, J. R. (2007). Data Structures with Java (2nd Edition). McGraw-Hill. Retrieved from https://www.pdfdrive.com/data-structures-with-java-d19408917.html - Data Structures in Java 72 Malik, D. S., & Nair, P. S. (2012). Data Structures in Java. Cengage Learning. Rout, A. R. (2020, April 23). Types of Recursions. Retrieved from www.geeksforgeeks.org: https://www.geeksforgeeks.org/types-of- recursions/#:~:text=Recursion%20are%20mainly%20of%20two,one%20is%20called %20indirect%20recursion. www.seekpng.com. (n.d.). Retrieved from https://www.seekpng.com/ima/u2q8a9u2u2q8i1y3/ 73  MODULE 6 LINKED LIST Introduction You have learned how data can be organized and processed sequentially using arrays. You have performed several operation in arrays such as traversal, search, insert, update and delete. Based from the programs you developed in Module 2, you found out that insertion and deletion in a sorted array would require additional processing time to move the affected elements of the array for it to remain sorted. Furthermore, since array size is fixed after its declaration, addition of elements is only possible if there is still a room for insertion. Similarly, deletion requires shifting the elements for them to remain contiguous in the memory. Thus, there are limitations when using arrays to organize the list. In this section, you will be able to learn a new way of organizing data through a linked list. You will understand how memory can be allocated and deallocated dynamically, performed operations in a linked list such as insertion, deletion, searching and traversals, and find a solution to overcome the limitations of arrays. Learning Outcomes At the end of the lesson, the student is expected to: 1. Define linked list; 2. Recognize the parts of a linked list; 3. Differentiate arrays and linked list; 4. Explain the types of linked list; and 5. Develop solutions using linked list. Lesson 1. Definition A linked list is a collection of components, called nodes. Every node (except the last node) contains the address of the next node. Thus, every node in a linked list has two fields: one to store the relevant information (for example, the data); and one to store the address, called the link, of the next node in the list. The address of the first node in the list is stored in a separate location, called the head or first (Malik & Nair, 2012). Linked List Representation (Data Structure and Algorithms - Linked List, 2020) Linked list can be visualized as a chain of nodes, where every node points to the next node. Figure 6.1 Linked list representation (Data Structure and Algorithms - Linked List, 2020) As per the above illustration, following are the important points to be considered.  Linked List contains a link element called head or first.  Each link carries a data field(s) and a link field called next.  Each link is connected to its next link using its next field.  Last link carries a link as null to mark the end of the list. Example: 75  In the given list, the data field contains integers and the memory addresses are given for discussion purposes only. In the actual application, these memory addresses are allocated by the system. From the list, the following can be inferred: head = 10F tail = 08F head.data = 45 head.next = 03F head.next.data = 32 head.next.next = 08F tail.data = 80 tail.next = null Advantages of Linked Lists (Ahlawat, Introduction to Linked Lists, 2020)  They are a dynamic in nature which allocates the memory when required.  Insertion and deletion operations can be easily implemented.  Stacks and queues can be easily executed.  Linked List reduces the access time. Disadvantages of Linked Lists (Ahlawat, Introduction to Linked Lists, 2020)  The memory is wasted as pointers require extra memory for storage.  No element can be accessed randomly; it has to access each node sequentially.  Reverse Traversing is difficult in linked list. Types of Linked Lists (Ahlawat, Introduction to Linked Lists, 2020) The three (3) different implementations of linked list are: 1. Singly Linked List 2. Doubly Linked List 3. Circular Linked List Lesson 2. Singly Linked List According to Karumanchi (2017), singly linked list is consists of a number of nodes in which each node has a next pointer to the succeeding element. The link of the last node in 76  the list is NULL, which indicates the end of the list. Generally “linked list” means a singly linked list. Insert Operation (Data Structure and Algorithms - Linked List, 2020) Adding a new node in linked list is a more than one step activity. To insert an item in the list, first, create a node using the same structure and find the location where it has to be inserted. Figure 6.2 A new node is to be inserted in the list (Data Structure and Algorithms - Linked List, 2020) If node B (NewNode) will be inserted between A (LeftNode) and C (RightNode), then point B.next to C. In code, the statement is, NewNode.next = RightNode; The result shall be, Figure 6.3 The pointer field of Node B points to Node C (Data Structure and Algorithms - Linked List, 2020) Now, the next node at the left should point to the new node. LeftNode.next = NewNode; 77  Figure 6.4 The pointer field of the left node points to the new node (Data Structure and Algorithms - Linked List, 2020) This will put the new node in the middle of the two. The new list should look like the one shown below. Figure 6.5 List after inserting the new node (Data Structure and Algorithms - Linked List, 2020) Similar steps should be taken if the node is being inserted at the beginning of the list. While inserting it at the end, the second last node of the list should point to the new node and the new node will point to NULL. To summarize, here is the algorithm for inserting a node in the middle of the list (Java Program to insert a new node at the middle of the singly linked list, 2018). 1. Create a class Node which has two attributes: data and next. Next is a pointer to the next node in the list. 2. Create another class InsertMid which has three attributes: head, tail, and size that keep tracks of a number of nodes present in the list. 3. Create addNode() which will add a new node to the list: 3.1 Create a new node. 78  3.2 It first checks, whether the head is equal to null which means the list is empty. 3.3 If the list is empty, both head and tail will point to a newly added node. 3.4 If the list is not empty, the new node will be added to end of the list such that tail's next will point to a newly added node. This new node will become the new tail of the list. addInMid() will add a new node at the middle of the list: 1. It first checks, whether the head is equal to null which means the list is empty. 2. If the list is empty, both head and tail will point to a newly added node. 3. If the list is not empty, then calculate the size of the list and divide it by 2 to get mid- point of the list. 4. Define node current that will iterate through the list until current will point to the mid node. 5. Define another node temp which will point to node next to current. 6. The new node will be inserted after current and before temp such that current will point to the new node and the new node will point to temp. a. display() will display the nodes present in the list: 1. Define a node current which will initially point to the head of the list. 2. Traverse through the list till current points to null. 3. Display each node by making current to point to node next to it in each iteration. 79 public class InsertMid { //Represent a node of the singly linked list class Node{ int data; Node next; public Node(int data) { this.data = data; this.next = null; } } public int size; //Represent the head and tail of the singly linked list public Node head = null; public Node tail = null; //addNode() will add a new node to the list public void addNode(int data) { //Create a new node Node newNode = new Node(data); //Checks if the list is empty if(head == null) { //If list is empty, both head and tail will point to new node head = newNode; tail = newNode; } else { //newNode will be added after tail such that tail's next will point to newNode tail.next = newNode; //newNode will become new tail of the list tail = newNode; } //Size will count the number of nodes present in the list size++; } //This function will add the new node at the middle of the list. public void addInMid(int data){ //Create a new node Node newNode = new Node(data); //Checks if the list is empty if(head == null) { //If list is empty, both head and tail would point to new node head = newNode; tail = newNode; } else { Node temp, current; //Store the mid position of the list int count = (size % 2 == 0) ? (size/2) : ((size+1)/2); //Node temp will point to head temp = head; current = null; 80 Continuation of code: //Traverse through the list till the middle of the list is reached for(int i = 0; i < count; i++) { //Node current will point to temp current = temp; //Node temp will point to node next to it. temp = temp.next; } //current will point to new node current.next = newNode; //new node will point to temp newNode.next = temp; } size++; } //display() will display all the nodes present in the list public void display() { //Node current will point to head Node current = head; if(head == null) { System.out.println("List is empty"); return; } while(current != null) { //Prints each node by incrementing pointer System.out.print(current.data + " "); current = current.next; } System.out.println(); } public static void main(String[] args) { InsertMid sList = new InsertMid(); //Adds data to the list sList.addNode(1); sList.addNode(2); System.out.println("Original list: "); sList.display(); //Inserting node '3' in the middle sList.addInMid(3); System.out.println( "Updated List: "); sList.display(); //Inserting node '4' in the middle sList.addInMid(4); System.out.println("Updated List: "); sList.display(); } } 81 Output: Another way to insert an item in the list is to insert the node in the beginning of the list. The code below illustrate the process of insertion at the start of the list as well as accessing the data from left to right and vice-versa. import java.io.*; public class Node { public int data; public Node previous, next; Node(int data, Node head){ this.data = data; this.next = head; } public static BufferedReader x = new BufferedReader(new InputStreamReader(System.in)); public static void main(String args[])throws Exception{ int data; Node head = null, tail = null; String answer; do{ System.out.println("Enter a number."); data = Integer.parseInt(x.readLine()); if (head==null){ head = new Node(data, head); tail = head; } else{ head.previous = new Node(data, head); head = head.previous; } //left to right System.out.println("\nLeft to Right:"); for (Node q=head; q!=null; q=q.next) System.out.print(q.data + "\t"); //right to left System.out.println("\nRight to Left:"); for (Node q=tail; q!=null; q=q.previous) System.out.print(q.data + "\t"); System.out.print("\nTry again? (y/n) "); answer = x.readLine(); }while (answer.charAt(0) != 'n'); } } 82 Output Delete Operation (Data Structure and Algorithms - Linked List, 2020) To delete a data item in a singly linked list, first, locate the target node to be removed, by using searching algorithms. Figure 6.6 The target node for deletion is the middle item (Data Structure and Algorithms - Linked List, 2020) The left (previous) node of the target node now should point to the next node of the target node. The code shall be, LeftNode.next = TargetNode.next; 83  Figure 6.7 The pointer field of the previous (left) node points to the right node of the target (Data Structure and Algorithms - Linked List, 2020) This will remove the link that was pointing to the target node. Now, using the following code, we will remove what the target node is pointing at. TargetNode.next = NULL; Figure 6.8 The dotted line indicates that the link of the target node to the right node is removed (Data Structure and Algorithms - Linked List, 2020) The deleted node may be kept in the or simply deallocate memory and wipe off the target node completely. The final list shall be: Figure 6.9 The list after deleting the target node (Data Structure and Algorithms - Linked List, 2020) Data item in a linked list may be deleted based from the given position of the data item or the value of the data. 84 Procedure for deleting an item at the given position (Bharadwaj & Rai, 2020). void deleteNode(int position) { // If linked list is empty if (head == null) return; // Store head node Node temp = head; // If head needs to be removed if (position == 0) { head = temp.next; // Change head return; } // Find previous node of the node to be deleted for (int i=0; temp!=null && inext is the node to be deleted // Store pointer to the next of node to be deleted Node next = temp.next.next; temp.next = next; // Unlink the deleted node from list } 85 Procedure for deleting an item based from the search key (Pathak et al., 2020). void deleteNode(int key) { // Store head node Node temp = head, prev = null; // If head node itself holds the key to be deleted if (temp != null && temp.data == key) { head = temp.next; // Changed head return; } // Search for the key to be deleted, keep track of the // previous node as we need to change temp.next while (temp != null && temp.data != key) { prev = temp; temp = temp.next; } // If key was not present in linked list if (temp == null) return; // Unlink the node from linked list prev.next = temp.next; } Below is the sample code combining the insertion and deletion operations (Pathak et al., 2020). class MyLinkedList { Node head; class Node { int data; Node next; Node(int d) { data = d; next = null; } } public void add(int new_data) { Node new_node = new Node(new_data); new_node.next = head; head = new_node; } 86 Continuation of code void deleteNode(int key) { Node temp = head, prev = null; if (temp != null && temp.data == key) { head = temp.next; // Changed head return; } while (temp != null && temp.data != key) { prev = temp; temp = temp.next; } if (temp == null) return; prev.next = temp.next; } public void printList() { Node tnode = head; while (tnode != null) { System.out.print(tnode.data+" "); tnode = tnode.next; } } public static void main(String[] args) { MyLinkedList llist = new MyLinkedList(); llist.add(1); llist.add(3); llist.add(2); System.out.println("\nCreated Linked list is:"); llist.printList(); llist.deleteNode(1); // Delete node with data 1 System.out.println("\nLinked List after Deletion of 1:"); llist.printList(); } } 87 Output: Lesson 3. Doubly Linked List Doubly linked list is a complex type of linked list in which a node contains a pointer to the previous as well as the next node in the sequence. Therefore, in a doubly linked list, a node consists of three parts: node data, pointer to the next node in sequence (next pointer), and pointer to the previous node (previous pointer). A sample node in a doubly linked list is shown below (Doubly linked list, 2018). Figure 6.10 Structure of a doubly linked list (Doubly linked list, 2018) In Figure 6.10, Prev is a pointer field containing the address of the previous node or its predecessor. It contains a NULL value if the node is the head (first node in the list). Just like a singly linked list, Next is a pointer field containing the address of the next node in the list or its successor. It contains a NULL value if the node is the tail (last node in the list). 88 If there are more than one item in the list, the representation shall be (Data Structure - Doubly Linked List, 2020): Figure 6.11 Illustration of a doubly linked list with three (3) nodes (Data Structure - Doubly Linked List, 2020) According to Karumanchi (2017), the advantage of a doubly linked list (also called two- way linked list) is that given a node in the list, navigation in both directions (forward and backward) is possible. A node in a singly linked list cannot be removed unless there is a pointer to its predecessor. But in a doubly linked list, a node can be deleted even if there is no previous node’s address (since each node has a left pointer pointing to the previous node and can move backward). However, the primary disadvantages of doubly linked lists are:  Each node requires an extra pointer, requiring more space.  The insertion or deletion of a node takes a bit longer (more pointer operations). Insertion Operation A. Inserting a node at the beginning of the list (Reaper et al., 2020). // Adding a node at the beginning of the list public void add(int new_data) { Node new_Node = new Node(new_data); new_Node.next = head; new_Node.prev = null; if (head != null) head.prev = new_Node; head = new_Node; } 89 B. Inserting a node after a given node (Reaper et al., 2020). // Given a node as prev_node, insert a new node after the given node public void InsertAfter(Node prev_Node, int new_data) { if (prev_Node == null) { System.out.println("The given previous node cannot be NULL "); return; } Node new_node = new Node(new_data); new_node.next = prev_Node.next; prev_Node.next = new_node; new_node.prev = prev_Node; if (new_node.next != null) new_node.next.prev = new_node; } C. Inserting a node at the end of the list (Reaper et al., 2020). // Add a node at the end of the list void append(int new_data) { Node new_node = new Node(new_data); new_node.next = null; if (head == null) { new_node.prev = null; head = new_node; return; } Node last = head; while (last.next != null) last = last.next; last.next = new_node; new_node.prev = last; } 90 A complete working program to test above functions (Ghosh et al., 2020). public class DLL { Node head; // head of list class Node { int data; Node prev; Node next; // Constructor to create a new node // next and prev is by default initialized as null Node(int d) { data = d; } } // Adding a node at the beginning of the list public void add(int new_data) { Node new_Node = new Node(new_data); new_Node.next = head; new_Node.prev = null; if (head != null) head.prev = new_Node; head = new_Node; } public void InsertAfter(Node prev_Node, int new_data) { if (prev_Node == null) { System.out.println("The given previous node cannot be NULL "); return; } Node new_node = new Node(new_data); new_node.next = prev_Node.next; prev_Node.next = new_node; new_node.prev = prev_Node; if (new_node.next != null) new_node.next.prev = new_node; } // Add a node at the end of the list void append(int new_data) { Node new_node = new Node(new_data); Node last = head; new_node.next = null; if (head == null) { new_node.prev = null; head = new_node; return; } while (last.next != null) last = last.next; last.next = new_node; new_node.prev = last; } 91 Continuation of code // This function prints contents of linked list starting from the given node public void printlist(Node node) { Node last = null; System.out.println("Traversal in forward Direction"); while (node != null) { System.out.print(node.data + " "); last = node; node = node.next; } System.out.println(); System.out.println("Traversal in reverse direction"); while (last != null) { System.out.print(last.data + " "); last = last.prev; } } public static void main(String[] args) { DLL dll = new DLL(); // Insert 6. So linked list becomes 6->NULL dll.append(6); // Insert 7 at the beginning. So linked list becomes 7->6->NULL dll.add(7); // Insert 1 at the beginning. So linked list becomes 1->7->6->NULL dll.add(1); // Insert 4 at the end. So linked list becomes 1->7->6->4->NULL dll.append(4); // Insert 8, after 7. So linked list becomes 1->7->8->6->4->NULL dll.InsertAfter(dll.head.next, 8); System.out.println("The created Doubly Linked List is: "); dll.printlist(dll.head); } } Output: 92 Deletion Operation The deletion of a node in a doubly linked list can be divided into three main categories: 1. Deletion of the first item in the list (head); 2. Deletion in between items; and 3. Deletion of the last item in the list (tail). Let us assume that prev is the variable containing the address of predecessor and next is the variable containing the address of the successor, if the first item in the list will be deleted, the previous address field of its successor is set to null and the value of head is set to the address of its successor. head.next.prev = null; head = head.next; If the data to be deleted is in between two (2) nodes, the next address field of its predecessor is set to the next address field of the node to be deleted (target) and the previous address field of its successor is set to the previous address field of the node to be deleted. target.prev.next = target.next; target.next.prev = target.prev; Deleting the last item in the list requires the previous address field of its predecessor to be null and setting the value of tail to the address of its predecessor. tail.prev.next = null; tail = tail.prev; 93 Java implementation to delete a doubly linked list node at the given position (Singh & Jauhari, 2020). // A node of the doubly linked list class Node { int data; Node next, prev; } class DelDLL { // Function to delete a node in a Doubly Linked List. static Node deleteNode(Node head, Node del) { // base case if (head == null || del == null) return null; // If node to be deleted is head node if (head == del) head = del.next; // Change next only if node to be deleted is NOT the last node if (del.next != null) del.next.prev = del.prev; // Change prev only if node to be deleted is NOT the first node if (del.prev != null) del.prev.next = del.next; del = null; return head; } // Function to delete the node at the given position in the doubly linked list static void deleteNodeAtGivenPos(Node head, int n) { // if list in NULL or invalid position is given if (head == null || n