LINKED LIST.pptx

A linked list is a fundamental data structure in computer science and is used to organize a collection of elements, such as data, in a linear, non-contiguous manner. Unlike arrays, where elements are stored in contiguous memory locations, linked lists consist of nodes, and each node contains both data and a reference (or link) to the next node in the sequence. Linked lists provide dynamic memory allocation, which allows them to easily grow or shrink as needed.

1. Data Structure & Algorithm Unit 2: Queue and Linked List by: Dr. Shweta Saraswat

2. Contents Part B : Linked Lists: Introduction , single linked list, representation of a linked list in memory, Different Operations on a Single linked list, Reversing a single linked list, Advantages and disadvantages of single linked list, circular linked list, double linked list and Header linked list.

3. What is Linked List A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers as shown in the below image : In simple words, Each element of the Linked List is called a Node. A Linked List is formed by connecting multiple nodes.

4. A node consists of two parts, Data: It is the actual raw information that you want to maintain. It can be a video object, a number, a character, etc . Pointer to another node: It stores the link of the adjacent node.

5. Introduction 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.

6. Why linked list data structure needed? Here are a few advantages of a linked list that is listed below, it will help you understand why it is necessary to know . 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.

7. How would have you maintained the huge collection of images? The first thing that would have crossed your mind is maintaining an array of all images, but what if the number of images is ever increasing? Soon you’ll realize that arrays are not suited for this job, they don’t go very well with dynamic size data. We need something better, we need a data structure that can store a collection of objects just like an array, but whose size can be manipulated in real-time. This is where the Linked List comes in.

8. Types of linked lists :  There are mainly three types of linked lists: Single-linked list Double linked list Circular linked list Header linked list

9. 1. Singly-linked list Traversal of items can be done in the forward direction only due to the linking of every node to its next node.

10. 2. Doubly linked list Traversal of items can be done in both forward and backward directions as every node contains an additional  prev  pointer that points to the previous node.

11. 3. Circular linked lists A circular linked list is a type of linked list in which the first and the last nodes are also connected to each other to form a circle, there is no NULL at the end. 

12. 4. Header Linked list Header Linked List  is a modified version of Singly Linked List. In Header linked list, we have a special node, the  Header Node  present at the beginning of the linked list. The Header Node is an extra node at the front of the list storing meaningful information about the list. Such a node is not similar in structure to the other nodes in the list. It does not represent any items of the list like other nodes rather than the information present in the Header node is global for all nodes such as  Count of Nodes in a List ,  Maximum  among all Items,  Minimum  value among all Items etc. This gives useful information about the Linked list.

13. Single Linked List

14. Definition A singly linked list is a special type of  linked list  in which each node has only one link that points to the next node in the linked list .

15. Characteristics of a Singly Linked List: Each node holds a single value and a reference to the next node in the list. The list has a head, which is a reference to the first node in the list, and a tail, which is a reference to the last node in the list. The nodes are not stored in a contiguous block of memory, but instead, each node holds the address of the next node in the list. Accessing elements in a singly linked list requires traversing the list from the head to the desired node, as there is no direct access to a specific node in memory.

16. Application of Singly Linked Lists: Memory management:  Singly linked lists can be used to implement memory pools, in which memory is allocated and deallocated as needed. Database indexing : Singly linked lists can be used to implement linked lists in databases, allowing for fast insertion and deletion operations. Representing polynomials and sparse matrices:  Singly linked lists can be used to efficiently represent polynomials and sparse matrices, where most elements are zero. Operating systems:  Singly linked lists are used in operating systems for tasks such as scheduling processes and managing system resources.

17. Advantages of Singly Linked Lists: Dynamic memory allocation : Singly linked lists allow for dynamic memory allocation, meaning that the size of the list can change at runtime as elements are added or removed. Cache friendliness:  Singly linked lists can be cache-friendly as nodes can be stored in separate cache lines, reducing cache misses and improving performance. Space-efficient:  Singly linked lists are space-efficient, as they only need to store a reference to the next node in each element, rather than a large block of contiguous memory.

18. Disadvantages of Singly Linked Lists: Poor random access performance : Accessing an element in a singly linked list requires traversing the list from the head to the desired node, making it slow for random access operations compared to arrays. Increased memory overhead:  Singly linked lists require additional memory for storing the pointers to the next node in each element, resulting in increased memory overhead compared to arrays. Vulnerability to data loss:  Singly linked lists are vulnerable to data loss if a node’s next pointer is lost or corrupted, as there is no way to traverse the list and access other elements. Not suitable for parallel processing:  Singly linked lists are not suitable for parallel processing, as updating a node requires exclusive access to its next pointer, which cannot be easily done in a parallel environment. Backward traversing not possible:  In singly linked list does not support backward traversing. 

19. representation of a linked list in memory

20. Representation of a Linked List in Memory There are two ways to represent a linked list in memory: 1. Static representation using array 2. Dynamic representation using free pool of storage

21. Static representation In static representation of a single linked list, two arrays are maintained: one array for data and the other for links. The static representation of the linked list in Figure 5.2 is shown in Figure 5.3.

22. Static representation Two parallel arrays of equal size are allocated which should be sufficient to store the entire linked list. Nevertheless this contradicts the idea of the linked list (that is non-contagious location of elements). But in some programming languages, for example, ALGOL, FORTRAN, BASIC, etc. such a representation is the only representation to manage a linked list.

23. Dynamic representation The efficient way of representing a linked list is using the free pool of storage . In this method, there is a  memory bank  (which is nothing but a collection of free memory spaces) and a  memory manager  (a program, in fact). During the creation of a linked list, whenever a node is required the request is placed to the memory manager; the memory manager will then search the memory bank for the block requested and, if found, grants the desired block to the caller . Again, there is also another program called the  garbage collector ;   it plays whenever a node is no more in use; it returns the unused node to the memory bank . It may be noted that memory bank is basically a list of memory spaces which is available to a programmer. Such a memory management is known as  dynamic  memory management. The dynamic representation of linked list uses the dynamic memory management policy.

24. Dynamic representation The mechanism of dynamic representation of single linked list is illustrated in Figures  . A list of available memory spaces is there whose pointer is stored in AVAIL. For a request of a node, the list AVAIL is searched for the block of right size. If AVAIL is null or if the block of desired size is not found, the memory manager will return a message accordingly. Suppose the block is found and let it be XY. Then the memory manager will return the pointer of XY to the caller in a temporary buffer, say NEW. The newly availed node XY then can be inserted at any position in the linked list by changing the pointers of the concerned nodes . In Figure 3.4(a), the node XY is inserted at the end and change of pointers is shown by the dotted arrows. Figure 3.4(b) explains the mechanism of how a node can be returned from a linked list to the memory bank.

25. Dynamic representation Figure 5.4(a)   Allocation of a node from memory bank to a linked list. Figure 5.4(b)   Returning a node from a linked list to memory bank.

26. Different Operations on a Single linked list

27. Linked List operations There are various linked list operations that allow us to perform different actions on linked lists . Here's a list of basic linked list operations: Traversal  - access each element of the linked list Insertion  - adds a new element to the linked list Deletion  - removes the existing elements Search  - find a node in the linked list Sort  - sort the nodes of the linked list

28. 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. Make the new node point to HEAD. Make the HEAD point to the new node.

29. Insertion after some Node Insertion of a new node after some node in a singly linked list is carried out in the following manner, Reach the desired node after which the new node is to be inserted. Make the new node point to the next element of the current node. Make the current node point to the new node. Inserting a new node after some node is an O(N) operation.

30. Insertion at the end Insertion of a new node at the end of a singly linked list  is performed in the following way, Traverse the list from start and reach the last node. Make the last node point to the new node. 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.

31. 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, Make the HEAD point to its next element.

32. 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.

33. 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.

34. 3. Traverse (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.

35. 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.

36. 5. Sort We will use a simple sorting algorithm, Bubble Sort, to sort the elements of a linked list in ascending order.

37. Reversing a single linked list

38. reverse the linked list Given a pointer to the head node of a linked list, the task is to reverse the linked list. We need to reverse the list by changing the links between nodes . Examples :  Input : Head of following linked list  1->2->3->4->NULL  Output : Linked list should be changed to,  4->3->2->1->NULL Input : Head of following linked list  1->2->3->4->5->NULL  Output : Linked list should be changed to,  5->4->3->2->1->NULL

39. Reverse a linked list by Iterative Method: The idea is to use three pointers  curr ,  prev ,  and  next  to keep track of nodes to update reverse links .

40. Reverse a linked list by Iterative Method:

41. Reverse a linked list by Iterative Method Follow the steps below to solve the problem: Initialize three pointers  prev  as NULL,  curr  as  head , and  next  as NULL. Iterate through the linked list. In a loop, do the following: Before changing the  next  of  curr , store the  next  node  next = curr -> next Now update the  next  pointer of  curr  to the  prev   curr -> next = prev   Update  prev  as  curr  and  curr  as  next   prev = curr   curr = next

42. Comparison

43. Thank you