UNIT-1_978e5ccaab93ccfb4737c710589ac906.pdf

UNIT-I Data structures: Linear Data Structures and its operations, Non-linear data structures, List using arrays and linked list, Single linked lists - Insertion, Deletion, Search operations, Double linked lists- Insertion, Deletion, Search Oper...

UNIT-I Data structures: Linear Data Structures and its operations, Non-linear data structures, List using arrays and linked list, Single linked lists - Insertion, Deletion, Search operations, Double linked lists- Insertion, Deletion, Search Operations, Circular Linked List - Insertion, Deletion, Search operations. What is Data Structure? A data structure is a specialized format for organizing, processing, retrieving and storing data. (Or) The data structure name indicates itself that organizing the data in memory. There are many ways of organizing the data in the memory as we have already seen one of the data structures, i.e., array in C language. Array is a collection of memory elements in which data is stored sequentially, i.e., one after another. The data structure is not any programming language like C, C++, java, etc. It is a set of algorithms that we can use in any programming language to structure the data in the memory. To structure the data in memory, 'n' number of algorithms were proposed, and all these algorithms are known as Abstract data types. These abstract data types are the set of rules. Types of Data Structures There are two types of data structures: o Primitive data structure o Non-primitive data structure Primitive Data structure The primitive data structures are primitive data types. The int, char, float, double, and pointer are the primitive data structures that can hold a single value. Non-Primitive Data structure The non-primitive data structure is divided into two types: o Linear data structure o Non-linear data structure Linear Data Structure The arrangement of data in a sequential manner is known as a linear data structure. The data structures used for this purpose are Arrays, Linked list, Stacks, and Queues. In these data structures, one element is connected to only one another element in a linear form. When one element is connected to the 'n' number of elements known as a non-linear data structure. The best example is trees and graphs. In this case, the elements are arranged in a random manner. List using arrays and linked list:- A list data structure is a fundamental data structure in computer science that stores a collection of items, elements, or values in a sequential order. Lists are versatile and can be implemented in various programming languages with different features and capabilities. Here are some key points about lists: Sequential Order: Lists maintain the order of elements as they are inserted. This means that elements are indexed and can be accessed by their position in the list. Mutable: In many programming languages, lists are mutable, meaning that elements can be added, removed, or modified after the list is created. Dynamic Size: Lists typically have dynamic sizing, meaning that they can grow or shrink as needed to accommodate new elements or remove existing ones. Homogeneous or Heterogeneous: Depending on the language, lists can contain elements of the same type (homogeneous) or different types (heterogeneous). Random Access: Lists usually support random access to elements, meaning that you can access any element in the list in constant time with its index. Common Operations: Common operations on lists include appending elements, inserting elements at specific positions, removing elements, accessing elements by index, slicing (extracting sublists), and iterating over elements. ARRAYS: Arrays are defined as the collection of similar types of data items stored at contiguous memory locations. It is one of the simplest data structures where each data element can be randomly accessed by using its index number. Memory allocation of an array As stated above, all the data elements of an array are stored at contiguous locations in the main memory. The name of the array represents the base address or the address of the first element in the main memory. Each element of the array is represented by proper indexing. We can define the indexing of an array in the below ways - 1. 0 (zero-based indexing): The first element of the array will be arr. 2. 1 (one-based indexing): The first element of the array will be arr. 3. n (n - based indexing): The first element of the array can reside at any random index number. Java Arrays Arrays are used to store multiple values in a single variable, instead of declaring separate variables for each value. To declare an array, define the variable type with square brackets: String[] cars; We have now declared a variable that holds an array of strings. To insert values to it, you can place the values in a comma-separated list, inside curly braces: String[] cars = {"Volvo", "BMW", "Ford", "Mazda"}; To create an array of integers, you could write: int[] myNum = {10, 20, 30, 40}; Access the Elements of an Array You can access an array element by referring to the index number. This statement accesses the value of the first element in cars: Example: String[] cars = {"Volvo", "BMW", "Ford", "Mazda"}; System.out.println(cars); // Output Volvo Test it Now Linked list: o Linked List can be defined as collection of objects called nodes that are randomly stored in the memory. o A node contains two fields i.e. data stored at that particular address and the pointer which contains the address of the next node in the memory. o The last node of the list contains pointer to the null. Uses of Linked List o The list is not required to be contiguously present in the memory. The node can reside any where in the memory and linked together to make a list. This achieves optimized utilization of space. o list size is limited to the memory size and doesn't need to be declared in advance. o Empty node can not be present in the linked list. o We can store values of primitive types or objects in the singly linked list. Types Of Linked List: Singly Linked List:- A Singly Linked List is a specialized case of a generic linked list. In a singly linked list, each node links to only the next node in the sequence, i.e. if we start traversing from the first node of the list, we can only move in one direction(pun intended). The Node of the singly linked list, apart from the data, stores the address of only the next element, as shown below. The following is the JAVA representation of a node. class Node{ int data; Node next; } For a linked list we maintain a special pointer known s HEAD. This pointer stores the address of the first node of the list. Also, the last node can no longer have the next element. Hence we indicate the end of the linked list by assigning NULL to its next. Operations on Singly Linked List 1. Insertion Insertion in a singly linked list can be performed in the following ways,  Insertion at the start Insertion of a new node at the start of a singly linked list is carried out in the following manner. o Make the new node point to HEAD. o Make the HEAD point to the new node. Inserting a new node at the start is an O(1) operation. void insertAtStart(Node newNode, Node head){  newNode.data = 10; newNode.next = head; head.next = newNode; }  Insertion after some Node Insertion of a new node after some node in a singly linked list is carried out in the following manner, o Reach the desired node after which the new node is to be inserted. o Make the new node point to the next element of the current node. o Make the current node point to the new node. Inserting a new node after some node is an O(N) operation. void insertAfterTargetNode(Node newNode, Node head, int target){ newNode.data = 10; Node temp = head; while(temp.data != target){ temp = temp.next; } newNode.next = temp.next; temp.next = newNode; }  Insertion at the end Insertion of a new node at the end of a singly linked list isperformed in te followin way, o Taverse the list from start and reach the last node. o Make the last node point to the new node. o Make the new node point to null, marking the end of the list. Inserting a new node at the end is an O(N) operation. void insertAtEnd(Node newNode, Node head){ newNode.data = 10; Node temp = head; while(temp.next != null){ temp = temp.next; } temp.next = newNode; newNode.next = null; } 2. Deletion Deletion in a singly linked list can be performed in the following ways,  Deletion at the start The first node of the singly linked list can be deleted as follows, o Make the HEAD point to its next element. Deleting the first node of a singly linked list is an O(1) operation. void deleteAtFirst(Node head){ head = head.next; }  Deletion at the middle The deletion after a specific node can be formed in the following way,  Reach the desired node after which the node is to be deleted.  Make the current node point to the next of next element. Deleting a node after a specific node is an O(N) operation. void deleteAfterTarget(Node head, int target){ Node temp = head; while(temp.data != target){  temp = temp.next; } temp.next= temp.next.next; }  Deletion at last The deletion of the last node is performed in the following manner,  Reach the second last node of th singly linke list.  Make the second last node point null. Deleting the last node is an O(N) operation. void deleteLast(Node head){ Node temp = head; while(temp.next.next != null){ temp = temp.next; } temp.next = null; } 3. Display To display the entire singly linked list, we need to traverse it from first to last. In contrast to arrays, linked list nodes cannot be accessed randomly. Hence to reach the n-th element, we are bound to traverse through all (n-1) elements. Since the entire linked list is traversed, the operation costs us O(N) time complexity. The following JAVA snippet shows how the entire singly linked list can be displayed. void display(Node head){ Node temp = head; while(temp != null){ System.out.println(temp.data); temp = temp.next; } } 4. Search To search an element in the singly linked list, we need to traverse the linked list right from the start. At each node, we perform a lookup to determine if the target has been found, if yes, then we return the target node else we move to the next element. In the worst case, we could end up visiting all the nodes in the list and hence searching an element in the singly linked list cost us O(N) operational time. Node search(Node head, int target){ Node temp = head; while(temp != null && temp.data != target){ temp = temp.next; } return temp; } Doubly Linked List Doubly Linked List is a Data Structure, which is a variation of the Linked List, in which the transversal is possible in both the directions, forward and backward easily as compared to the Singly Linked List, or which is also simply called as a Linked List. Representation of Doubly Linked List in Data Structure If you can recall how the Linked List was represented using 2 parts: Value and the next pointer. The Doubly Linked List has 3 parts: Value, Next pointer, and the Previous pointer. The Previous pointer is the fundamental difference between the Doubly Linked List and the Linked List, which enables one to transverse back also in the Doubly Linked List. As per the above illustration, following are the important points to be considered. Each Doubly Linked List Element contains pointers to next and Previous Elements and the data field. The First Element will have its Previous pointer as Null, to mark the start of the List. The Last Element will have its Next pointer as Null, to mark the end of the List. From the Code Perspective, the Doubly Linked List can be represented as: class Node { Node previous; // Pointer to the Previous Element int value; // Value stored in this element. Node next; // Pointer to the Next Element } Memory representation of a Doubly Linked List in Data Structure A Doubly Linked List is represented using the Linear Arrays in memory where each memory address stores 3 parts: Data Value, Memory address of next Element and Memory Address of the previous Element. This can be picturised as: In the above image, -1 is being used to represent NULL. Here 1000, 1051, 1052 etc represents the addresses in the memory, and we traverse the Doubly Linked List until we find -1 in the Next of the Node. This Memory representation shows that the Values need not be stored contiguously. As shown above, Element A has previous = -1 i.e. NULL, so it is acting as the first Node in the Doubly Linked List. A’s Next points to memory address 1052, where B is stored, so this represents that B is to the next of A. Similarly B’s Next has a memory address of 1059 where C is stored. Similarly D has its Next as -1, meaning its the last Node of this Doubly Linked List. So it forms the DLL like: -1 ← A ⇆ B ⇆ C ⇆ D → -1. Operations on Doubly Linked List Traversing Since the Doubly Linked List has both next and previous pointers, this allows us to transverse in both the directions from the given Node. We can go to the previous node by following the previous pointer, and similarly go to the next nodes by following the next pointers. Transverse from B: And Transverse Back from C: Algorithm: public void transverseForward(Node start) { Node current = start; //Checks whether the list is empty if (start == null) { System.out.println("Node to start from is NULL"); return; } while (current != null) { System.out.println("Node : " + current.value); current = current.next; } } public void transverseBackward(Node start) { Node current = start; //Checks whether the list is empty if (start == null) { System.out.println("Node to start from is NULL"); return; } while (current != null) { System.out.println("Node : " + current.value);  current = current.previous; } } Searching To search in the given doubly linked list, we would basically need to traverse the entire doubly linked list from the first node, and keep moving to next nodes using the next pointer. We can compare each transversed element against the one we are searching for. Please note that this is the same as the Singly Linked List searching algorithm. public void searchNode(int value) { int i = 1; //Node current will point to head Node current = head; //Checks whether the list is empty if (head == null) { System.out.println("List is empty"); return; } // Traversing the List. while (current != null) { //Compare value to be searched with each node in the list if (current.value == value) { System.out.println("Node is present in the list at the position : " + i); return; } current = current.next; i++; } System.out.println("Node is not present in the list"); } Insertion Insertion into the Doubly Linked List is fast and can be done in constant times, as we just need to change the pointers of adjacent elements we are inserting this element between. We will see how this works in the below sections, but one thing to note is that like Linked List, insertions are faster in Doubly Linked List over Arrays, as here we need to shift any elements forward, and hence it takes Constant time to insert. E.g. if Array = {1, 2, 3} and to insert 10 at 1st Index, we need to move 2 and 3 one step forward to make space for 10, to get: {1, 10, 2, 3} But this shifting of rest of the elements is not required if the inserting is to be done inside the doubly linked list. There can be 4 different ways of inserting a new Element inside a Doubly Linked List, and we will see each of these ways in detail below: Insert First A Node can be inserted as the first element in the Doubly Linked List. Earlier Doubly Linked List: A ⇆ B ⇆ Now after we insert X inside this Doubly Linked List: X ⇆ A ⇆ B ⇆ C So as we can see, to insert an element at front, we need to change pointers of A Node. Earlier: Head points to A and A.previous points = NULL. After Insertion: X.previous points to NULL, and X.Next points to Head or to A. Update A.previous = X. Update Head to now point to X. // Adding a node at the front of the list public void insertFront(int newValue) { // Create New Node and put data in it. Node newNode = new Node(newValue); // Update next of the new node as head and previous as NULL. newNode.next = head; // i.e. X.next = A. Head points to A yet. // Since X = first Node, so its prev should point to NULL. newNode.previous = null;  // Change prev of head node to new node // Head points to A, so change A Previous to be X. if (head != null) head.previous = newNode; // Since X and A pointers are altered, we can not point Head to X which is the new start of the DLL. head = newNode; } As we can see, we are only updating the pointers of adjacent Nodes, so it takes Constant time to insert a new Element at the front of the Doubly Linked List. Insert After a Node If we are given a Node(say C) and we want to insert a new Node(say X) after it, then the algorithm would look like: DLL Before ⇒ B ⇆ C ⇆ D ⇆ E After Insert X after C⇒ B ⇆ C ⇆ X ⇆ D ⇆ E So as we can see, we need to change : C.next to now point to X. D.Prev now points to X. And X.prev points to C and X.next points to D.  // Given a node as previousNode, insert a new node after it. public void InsertAfter(Node previousNode, int newValue) { // Check if the given prev_node is NULL if (previousNode == null) { System.out.println("The given previous node cannot be NULL "); return; } // Create New Node and put data in it. Node newNode = new Node(newValue); // Make next of new node as next of previousNode // X --> C.next i.e. X --> D newNode.next = previousNode.next; // Make the next of previousNode as newNode // C --> X previousNode.next = newNode; // Make previousNode as previous of newNode // C next.  last -> next = T.  Circular linked list before insertion And then, Circular linked list after insertion 2) Insertion at the end of the list: To insert a node at the end of the list, follow these steps:  Create a node, say T.  Make T -> next = last -> next;  last -> next = T.  last = T. Before insertion, Circular linked list before insertion of node at the end After insertion, Circular linked list after insertion of node at the end  3) Insertion in between the nodes: To insert a node in between the two nodes, follow these steps:  Create a node, say T.  Search for the node after which T needs to be inserted, say that node is P.  Make T -> next = P -> next;  P -> next = T. Suppose 12 needs to be inserted after the node has the value 10, Circular linked list before insertion After searching and insertion, Circular linked list after insertion Below is a complete program that uses all of the above methods to create a circular singly linked list. // Java program for the above methods public class GFG { static class Node { int data; Node next; }; static Node addToEmpty(Node last, int data) { // This function is only for empty list if (last != null) return last;  // Creating a node dynamically Node temp = new Node(); // Assigning the data. temp.data = data; last = temp; // Creating the link. last.next = last; return last; } static Node addBegin(Node last, int data) { if (last == null) return addToEmpty(last, data); Node temp = new Node(); temp.data = data; temp.next = last.next; last.next = temp; return last; } static Node addEnd(Node last, int data) { if (last == null) return addToEmpty(last, data); Node temp = new Node(); temp.data = data; temp.next = last.next; last.next = temp; last = temp; return last; } static Node addAfter(Node last, int data, int item) { if (last == null) return null; Node temp, p; p = last.next; do { if (p.data == item) { temp = new Node(); temp.data = data;  temp.next = p.next; p.next = temp; if (p == last) last = temp; return last; } p = p.next; } while (p != last.next); System.out.println(item + " not present in the list."); return last; } static void traverse(Node last) { Node p; // If list is empty, return. if (last == null) { System.out.println("List is empty."); return; } // Pointing to first Node of the list. p = last.next; // Traversing the list. do { System.out.print(p.data + " "); p = p.next; } while (p != last.next); } // Driver code public static void main(String[] args) { Node last = null; last = addToEmpty(last, 6); last = addBegin(last, 4); last = addBegin(last, 2); last = addEnd(last, 8); last = addEnd(last, 12); last = addAfter(last, 10, 8); // Function call traverse(last); } }  Output 2 4 6 8 10 12 Deletion in a circular linked list: 1) Delete the node only if it is the only node in the circular linked list:  Free the node’s memory  The last value should be NULL A node always points to another node, so NULL assignment is not necessary. Any node can be set as the starting point. Nodes are traversed quickly from the first to the last. 2) Deletion of the last node:  Locate the node before the last node (let it be temp)  Keep the address of the node next to the last node in temp  Delete the last memory  Put temp at the end 3) Delete any node from the circular linked list: We will be given a node and our task is to delete that node from the circular linked list. Algorithm: Case 1: List is empty.  If the list is empty we will simply return. Case 2:List is not empty  If the list is not empty then we define two pointers curr and prev and initialize the pointer curr with the head node.  Traverse the list using curr to find the node to be deleted and before moving to curr to the next node, every time set prev = curr.  If the node is found, check if it is the only node in the list. If yes, set head = NULL and free(curr).  If the list has more than one node, check if it is the first node of the list. Condition to check this( curr == head). If yes, then move prev until it reaches the last node. After prev reaches the last node, set head = head -> next and prev -> next = head. Delete curr.  If curr is not the first node, we check if it is the last node in the list. Condition to check this is (curr -> next == head).  If curr is the last node. Set prev -> next = head and delete the node curr by free(curr).  If the node to be deleted is neither the first node nor the last node, then set prev -> next = curr -> next and delete curr.  If the node is not present in the list return head and don’t do anything. // Java program to delete a given key from // linked list. import java.util.*; import java.io.*; public class GFG { static class Node { int data; Node next; }; static Node push(Node head_ref, int data) { // Create a new node and make head as next // of it. Node ptr1 = new Node(); ptr1.data = data; ptr1.next = head_ref; if (head_ref != null) { // Find the node before head and update // next of it. Node temp = head_ref; while (temp.next != head_ref) temp = temp.next; temp.next = ptr1; } else ptr1.next = ptr1; head_ref = ptr1; return head_ref; } static void printList(Node head) { Node temp = head; if (head != null) { do { System.out.printf("%d ", temp.data); temp = temp.next; } while (temp != head); } System.out.printf("\n"); } static Node deleteNode(Node head, int key) { if (head == null) return null; // Find the required node Node curr = head, prev = new Node();  while (curr.data != key) { if (curr.next == head) { System.out.printf("\nGiven node is not found" + " in the list!!!"); break; } prev = curr; curr = curr.next; } // Check if node is only node if (curr == head && curr.next == head) { head = null; return head; } // If more than one node, check if // it is first node if (curr == head) { prev = head; while (prev.next != head) prev = prev.next; head = curr.next; prev.next = head; } // check if node is last node else if (curr.next == head) { prev.next = head; } else { prev.next = curr.next; } return head; } public static void main(String args[]) { Node head = null; head = push(head, 2); head = push(head, 5); head = push(head, 7); head = push(head, 8);  head = push(head, 10); System.out.printf("List Before Deletion: "); printList(head); head = deleteNode(head, 7); System.out.printf("List After Deletion: "); printList(head); } } Output List Before Deletion: 10 8 7 5 2 List After Deletion: 10 8 5 2 Advantages of Circular Linked Lists:  Any node can be a starting point. We can traverse the whole list by starting from any point. We just need to stop when the first visited node is visited again.  Useful for implementation of a queue. Unlike this implementation, we don’t need to maintain two pointers for front and rear if we use a circular linked list. We can maintain a pointer to the last inserted node and the front can always be obtained as next of last.  Circular lists are useful in applications to repeatedly go around the list. For example, when multiple applications are running on a PC, it is common for the operating system to put the running applications on a list and then cycle through them, giving each of them a slice of time to execute, and then making them wait while the CPU is given to another application. It is convenient for the operating system to use a circular list so that when it reaches the end of the list it can cycle around to the front of the list.  Circular Doubly Linked Lists are used for the implementation of advanced data structures like the Fibonacci Heap.  Implementing a circular linked list can be relatively easy compared to other more complex data structures like trees or graphs. Disadvantages of circular linked list:  Compared to singly linked lists, circular lists are more complex.  Reversing a circular list is more complicated than singly or doubly reversing a circular list.  It is possible for the code to go into an infinite loop if it is not handled carefully.  It is harder to find the end of the list and control the loop.  Although circular linked lists can be efficient in certain applications, their performance can be slower than other data structures in certain cases, such as when the list needs to be sorted or searched.  Circular linked lists don’t provide direct access to individual nodes  Applications of circular linked lists:  Multiplayer games use this to give each player a chance to play.  A circular linked list can be used to organize multiple running applications on an operating system. These applications are iterated over by the OS.  Circular linked lists can be used in resource allocation problems.  Circular linked lists are commonly used to implement circular buffers,  Circular linked lists can be used in simulation and gaming. Search operation: Given a Circular Linked List CList, and an element K, the task is to check if this element K is present in the Circular Linked list or not. Example: Input: CList = 6->5->4->3->2, K = 3 Output: Found Input: CList = 6->5->4->3->2, K = 1 Output: Not Found Approach: The approach to find an element in Circular Linked List can be visualized as follows: 1. Keep a pointer to the head of the Circular Linked List. This will help us to determine if the Linked List has been traversed already. 2. Now traverse the Linked List one by one and check if the element is present or not. 3. If the element is present, return true. 4. Now if the element is not present and the traversal pointer reaches the head again, it means the element is not present in the CLL. Therefore return false. // Java program to search for an element in a circular // linked list public class Search { class Node { int data; Node next; public Node(int data) { this.data = data; } } // declaring head pointer as null public Node head = null; public Node tempo = null; // function to add new nodes at the end of the list public void addNode(int data) { Node new1 = new Node(data); // If linked list is empty if (head == null) { head = new1; }  else { tempo.next = new1; } tempo = new1; // last node points to first node tempo.next = head; } public void find(int key) { // temp will traverse the circular linked list for // searching element Node temp = head; // counter used to check if the element is found or // not int f = 0; if (head == null) { System.out.println("List is empty"); } else { do { if (temp.data == key) { System.out.println(key + " Found"); f = 1; break; } temp = temp.next; } while (temp != head); if (f == 0) { System.out.println(key + " Not Found"); } } } // Driver code public static void main(String[] args) { Search s = new Search(); // Adds data to the list s.addNode(5); s.addNode(4); s.addNode(3); s.addNode(2); // Search for node 2 in the list  int key = 2; s.find(key); // Search for node 6 in the list key = 6; s.find(key); } } Output 2 Found 6 Not Found