Presentation 15

DATA STRUCTURE AND ALGORITHMS PRESENTED BY SARTHAK AND HARSH.

WHAT IS LINKEDLIST • A linked list can be defined as the linear collection of elements where each element is stored in a ed in a node and the linear order between elements is given by the means of pointers instead of sequential memory locations. In linked list or one-way list, each node is divided into two parts. The first part of the node contain the element itself and the second part which is termed as next field or pointer field contains the address of the next node in the list.

HERE YOU CAN SEE IMAGE OF LINKEDLIST • In This Image You Can See Data And Address Of Another Node Is Stored Is Stroed In Continous Chain This Is One Example Of Linkedlist.

TYPES OF LINKEDLIST There Are Different Types Of Linkedlist They Are Explained As Follows.

SINGLY LINKEDLIST A singly linked list is a fundamental data structure, it consists of nodes where each node contains a data field and a reference to the next node in the linked list. The next of the last node is null, indicating the end of the list. Linked Lists support efficient insertion and deletion operations..

ALGORITHM/CODE OF SINGLY LINKEDLIST.

DOUBLY LINKEDLIST A doubly linked list is a more complex data structure than a singly linked list, but it offers several advantages. The main advantage of a doubly linked list is that it allows for efficient traversal of the list in both directions. This is because each node in the list contains a pointer to the previous node and a pointer to the next node. This allows for quick and easy insertion and deletion of nodes from the list, as well as efficient traversal of the list in both directions..

ALGORITHM/CODE • In This Example This Code Is Given To Verify Or See How Doubly Linkedlist Work's.

CIRCULAR LINKEDLIST A circular linked list is a data structure where the last node points back to the first node, forming a closed loop. Structure: All nodes are connected in a circle, enabling continuous traversal without encountering NULL. Difference from Regular Linked List: In a regular linked list, the last node points to NULL, whereas in a circular linked list, it points to the first node. Uses: Ideal for tasks like scheduling and managing playlists, where smooth and repeated..

1.CIRCULAR SINGLY LINKEDLIST In Circular Singly Linked List, each node has just one pointer called the "next" pointer. The next pointer of the last node points back to the first node and this results in forming a circle. In this type of Linked list, we can only move through the list in one direction..

2. CIRCULAR DOUBLY LINKEDLIST In circular doubly linked list, each node has two pointers prev and next, similar to doubly linked list. The prev pointer points to the previous node and the next points to the next node. Here, in addition to the last node storing the address of the first node, the first node will also store the address of the last node..

ALGORITHM /CODE.

ADVANTAGES OF LINKEDLIST Advantage of Circular Linked List Efficient Traversal No Null Pointers / References Useful for Repetitive Tasks Insertion at Beginning or End is O(1) Uniform Traversal Efficient Memory Utilization Disadvantage of Circular Linked List Complex Implementation Infinite Loop Risk Harder to Debug Deletion Complexity Memory Overhead (for Doubly Circular LL) Not Cache Friendly.

OPERATIONS IN LINKEDLIST INSERTION Insertion in a linked list involves adding a new node at a specified position in the list. There are several types of insertion based on the position where the new node is to be added: At the front of the linked list Before a given node. After a given node. At a specific position. At the end of the linked list..

1.INSERT A NODE AT THE BEGINNING OF LINKEDLIST To insert a new node at the front, we create a new node and point its next reference to the current head of the linked list. Then, we update the head to be this new node. This operation is efficient because it only requires adjusting a few pointers. ALGORITHM Make the first node of Linked List linked to the new node Remove the head from the original first node of Linked List Make the new node as the Head of the Linked List..

2.INSERT A NODE AFTER A GIVEN NODE IN LINKEDLIST If we want to insert a new node after a specific node, we first locate that node. Once we find it, we set the new node's next reference to point to the node that follows the given node. Then, we update the given node's next to point to the new node. This requires traversing the list to find the specified node. ALGORITHM Initialize a pointer curr to traverse the list starting from head. Loop through the list to find the node with data equal to key. If not found then return from function. Create a new node, say new_node initialized with the given data. Make the next pointer of new_node as next of given node. Update the next pointer of given node point to the new_node..

3.INSERT A NODE BEFORE A GIVEN NODE IN LINKEDLIST If we want to insert a new node before a given node, we first locate that node while keeping the track of previous node also. Once we find it, we set the previous node's next reference the new node. Then, we update the node's next reference to point to the given node. ALGORITHM Traverse the linked list while keeping track of the previous node until given node is reached. Once node is found, allocate memory for a new node and set according to given data . Point the next pointer of the new node to node given node. Point the next pointer of the previous node to the new node. If given key is the head, update the head to point to the new node..

4.INSERT A NODE AT THE SPECFIC LOCATION IN LINKEDLIST 1 To insert a new node at a specific position, we need to traverse the list to position - 1. If the position is valid, we adjust the pointers similarly such that the next pointer of the new node points to the next of current nod and next pointer of current node points to the new node. 2 ALGORITHM 3 Traverse the Linked list upto position-1 nodes. 4 Once all the position-1 nodes are traversed, allocate memory and the given data to the new node. 5 Point the next pointer of the new node to the next of current node. 6 Point the next pointer of current node to the new node..

5.INSERT A NODE AT THE END IN LINKEDLIST Inserting at the end involves traversing the entire list until we reach the last node. We then set the last node's next reference to point to the new node, making the new node the last element in the list. ALGORITHM Go to the last node of the Linked List Change the next pointer of last node from NULL to the new node Make the next pointer of new node as NULL to show the end of Linked List To read more about inserting at the end Refer, Insert Node at the End of a Linked List.

THANK YOU THAT'S IT FOR TODAY'S EPISODE WE WILL MEET AGAIN.