Linked List - 1 Lesson Plan PDF

Lesson Plan Linked List-1 Today’s Checklist Limitations of Array Introduction to Linked Lis Implementing Linked Lis Displayin Insert in Linked Lis Limitatio Delete in Linked List Limitations of Arrays Fixed Size: Most arrays have a fixed size, meaning you need to kno...

Lesson Plan Linked List-1 Today’s Checklist Limitations of Array Introduction to Linked Lis Implementing Linked Lis Displayin Insert in Linked Lis Limitatio Delete in Linked List Limitations of Arrays Fixed Size: Most arrays have a fixed size, meaning you need to know the number of elements in advance. This can be a limitation when the size of the data is dynamic and unknown beforehand Contiguous Memory Allocation: Elements in an array are stored in contiguous memory locations. This can lead to fragmentation and might make it difficult to find a large enough block of memory for the array Inefficient Insertions and Deletions: Inserting or deleting elements in the middle of an array requires shifting all subsequent elements, which can be inefficient. The time complexity for these operations is O(n), where n is the number of elements Wastage of Memory: If you allocate more space than needed for an array, you may end up wasting memory. This is particularly problematic when the array size is predetermined to accommodate the worst- case scenario Homogeneous Data Types: Arrays typically store elements of the same data type. This can be limiting when you need to store elements of different types Memory Fragmentation: The contiguous memory allocation can lead to memory fragmentation, making it challenging to allocate a large contiguous block of memory for a new array. Introduction to Linked List It is basically chains of nodes, each node contains information such as data and a pointer to the next node in the chain. In the linked list there is a head pointer, which points to the first element of the linked list, and if the list is empty then it simply points to null or nothing. Java + DSA Why linked list data structure needed? Dynamic Data structure: The size of memory can be allocated or de-allocated at run time based on the operation insertion or deletion Ease of Insertion/Deletion: The insertion and deletion of elements are simpler than arrays since no elements need to be shifted after insertion and deletion, Just the address needed to be updated Efficient Memory Utilization: As we know Linked List is a dynamic data structure the size increases or decreases as per the requirement so this avoids the wastage of memory. Implementation: Various advanced data structures can be implemented using a linked list like a stack, queue, graph, hash maps, etc. Implementing Linked List A linked list can be implemented in various ways, but the basic structure involves nodes, where each node contains data and a reference (or link) to the next node in the sequence. Java + DSA A step-by-step explanation of how to implement a simple singly linked list: Node Class: Create a class for the linked list node with data and a pointer to the next node. public class Node { public int data; public Node next; public Node(int value) { this.data = value; this.next = null; } } LinkedList Class: Create a class to represent the linked list. Include a pointer to the head of the list. public class LinkedList { private Node head; public LinkedList() { this.head = null; } } Add Nodes Implement a method to add nodes to the linked list If the list is empty, create a new node and set it as the head Otherwise, traverse to the end of the list and add a new node. public void addNode(int value) { Node newNode = new Node(value); if (head == null) { head = newNode; } else { Node current = head; while (current.next != null) { current = current.next; } current.next = newNode; } } Java + DSA Displaying: Once, we have created the linked list, we would like to see the elements inside it. Displaying a linked list involves iterating through its nodes and printing their data. This can also be done recursively as shown in the code below. Code: class Node { public int data; public Node next; public Node(int value) { this.data = value; this.next = null; } } public class Main { public static void displayLinkedListIterative(Node head) { while (head != null) { System.out.print(head.data + " "); head = head.next; } System.out.println(); } public static void displayLinkedListRecursive(Node head) { if (head == null) return; System.out.print(head.data + " "); displayLinkedListRecursive(head.next); } public static void main(String[] args) { Node head = new Node(1); head.next = new Node(2); head.next.next = new Node(3); head.next.next.next = new Node(4); System.out.print("Iterative Display: "); displayLinkedListIterative(head); System.out.print("Recursive Display: "); displayLinkedListRecursive(head); System.out.println(); } } Java + DSA Explanation: Iterative Display Initialize a pointer to the head of the linked list Use a while loop to traverse the list Print the data of each node and move the pointer to the next node Repeat until the end of the list is reached. Recursive Display Base case: If the current node is null, return Print the data of the current node Make a recursive call with the next node The recursion unwinds, printing nodes in sequential order Base case ensures termination when the end of the list is reached. Iterative Display: Time Complexity: O(n) - where 'n' is the number of nodes in the linked list. The algorithm iterates through each node once. Space Complexity: O(1) - uses a constant amount of extra space, regardless of the size of the linked list. Recursive Display: Time Complexity: O(n) - where 'n' is the number of nodes in the linked list. Similar to the iterative approach, each node is visited once, but the recursive call stack contributes to the time complexity. Space Complexity: O(n) - due to the recursive call stack. The maximum depth of the recursion is 'n', corresponding to the length of the linked list. MCQ: What will this function do? public void display(Node head) { if (head == null) return; display(head.next); System.out.print(head.data + " "); } Java + DSA A. Print all the elements of the linked list. B. Print all the elements except last one. C. Print alternate nodes of linked list D. Print all the nodes in reverse order Ans: Print all the nodes in reverse order. Explanation The given function is a recursive function that traverses the linked list using a recursive call (display(head- >next)) before printing the value of the current node (cout