Linked List Notes PDF

# 3. Linked List ### 3.1 Memory allocation - Memory allocation is a process by which computer programs or services are assigned with physical or virtual memory space. - The memory allocation is done either before or at the time of program execution. ### Types - **Static memory allocation** -...

# 3. Linked List ### 3.1 Memory allocation - Memory allocation is a process by which computer programs or services are assigned with physical or virtual memory space. - The memory allocation is done either before or at the time of program execution. ### Types - **Static memory allocation** - Static memory is allocated for declared variables by the compiler. - Memory is allocated during compile time. - **Dynamic memory allocation** - Memory allocation is done at the time of execution. - It is more efficient. ### Difference between static & dynamic memory allocation | Static memory Allocation | Dynamic memory allocation | | -------------------------- | --------------------------- | | Static memory allocation is done before program execution. | Dynamic memory allocation is done during program execution. | | In static memory allocation, variables get allocated permanently, till the program executes or function call finishes. | The memory is controlled by the programmer. It gets allocated whenever malloc() is executed. | | It uses stack for managing static allocation of memory. | It uses heap of memory for managing dynamic allocation of memory. | | It is less efficient. | It is more efficient. | | There is no memory reusability. | There is memory reusability. Memory can be freed when not required. | | Once the memory is allocated, the memory size can not change. | When memory is allocated, the memory size can be changed. | | We cannot reuse the unused memory. | This allows reusing the memory. | | In this memory allocation scheme, execution is faster than dynamic memory allocation. | In this memory allocation scheme, execution is slower than static memory allocation. | | Memory is allocated at compile time. | Memory is allocated at run time. | | In this allocated memory remains from start to end of program. | In this allocated memory can be released at any time during the program. | | Example: Static memory allocation is generally used for arrays. | Example: Dynamic memory allocation is used for linked list. | ## Limitations of array - Size of the array is defined at the time of programming. - Insertion & deletion is time consuming. - Requires contiguous memory. ## Advantages of linked list - Linked list is a dynamic data structure, they can grow & shrink during the execution of the program. - Efficient memory utilization. Memory is not pre-allocated. Memory is allocated as per the need. - Insertion & deletion are easier & efficient. ## Linked List - Linked list consists of a series of structures. - They are not required to be stored in adjacent memory locations. - Each structure consists of a data field & address field. - Address filed consists of the address of its successor. | Data | Address | | ----- | -------- | - A variable of the above structure type is conventionally known as "Node". - Node A: `21` - Node B: `21` - Node C: `21` - Data: `11, 12, 13` - Node A stores the data `21` & the address of the next node B - Node B stores the data `21` & the address of the next node C - Node C contains the data `21`, and its address field is grounded (NULL pointer) indicating it does not have a next node. - Node A: `5` - Node B: `10` - Node C: `15` - Memory Address: `500, 1000, 2000` - Structures in C can be used to define node: ```C struct node { int data; struct node *next; }; ``` ## Basic Terminologies in Linked List - **Node** - Nodes are the basic element in a linked list, and each node is made up of two parts: data & pointer. - Contains data of the node. - Contains address of the next node. - **Address** - It consists of the pointers & addresses that are used to link the elements. - **Pointer** - Pointer is a reference to the next node in a sequence. - Pointer in each node points to subsequent nodes, creating a chain of nodes. - The last node in a linked list has a pointer that typically points to null (indicating the end of the list). - **Data field** - This field stores the actual data or value of the node. It can hold any type of data. - **Next pointer** - It is an attribute of a node that points to the next node in the sequence. - This pointer allows us to traverse a Linked List. - **Null pointer** - Null pointer in a linked list is a pointer that does not point to any node. - It is used to indicate the end of a list. - The last node in the list has the next pointer set to null, signifying that there are no more nodes to traverse. - **Empty list** - An empty list means a linked list that contains no nodes. - It is typically represented by setting the head pointer to null: `head = null;` ## Types of List - **Singly Linked List** - This type of Linked List links each node to the next node in a sequential linear manner (forward). - We can move in the forward direction only. - **Example:** Used to store a list of tasks that need to be completed. The head node represents the first task to be completed, and the tail node represents the last task to be completed. - **Doubly Linked List** - This type of Linked List uses two pointers: next & previous. - We access the previous nodes as well as the subsequent nodes. - Each node holds the addresses of the next & previous nodes. - **Example:** It is a bi-directional linked list, so you can traverse in both directions (forward & backward). It requires an extra pointer, which is the previous pointer. - **Circular Linked List** - A circular linked List can be made circular by storing the address of the first node in the next field of the last node. - **Example:** It is useful where data needs to be processed in a continuous loop, such as in real-time applications. ## Insertion into Linked List - Insertion into a linked list requires obtaining a new node and then changing the value of two pointers. - The dashed line represents the old pointer. ## Deletion from Linked List - The `x3` node is deleted. - The next field of node `x2` is changed to point to `x4`. - Node containing `x3` is freed using the library function `free()`. ## Operations on Singly Linked List ### Creating a Singly Linked List - To create a linked list, create the nodes one by one and add them to the end of the list. - Nodes can be created using a structure, pointers, and dynamic memory allocation (function `malloc`). ```C struct node { int data; struct node *next; }; struct node *temp; temp = (struct node *) malloc(sizeof(struct node)); temp->data = n; temp->next = NULL; ``` ### Inserting an element in a Linked List - **Insertion** is a process to add a new element in a linked list. - The new element is inserted either at the **first**, **middle**, or **last** position. - **Inserting a node at the beginning:** ```C void insertbeg(int n) { temp = (struct node *) malloc(sizeof(struct node)); temp->data = n; temp->next = start; start = temp; } ``` - **Inserting a node at the end:** ```C void create(int n) { temp = (struct node *) malloc(sizeof(struct node)); temp->data = n; temp->next = NULL; if (start == NULL) { start = temp; } else { curr = start; while (curr->next != NULL) { curr = curr->next; } curr->next = temp; } } ``` ### Display ```C void display() { curr = start; while (curr != NULL) { printf("%d->", curr->data); curr = curr->next; } } ``` ### Inserting a node at the middle (specified position) ```C void insert(int n, int pos) { int cnt = 1; curr = start; while (cnt < pos - 1) { curr = curr->next; cnt++; } temp = malloc(sizeof(struct node)); temp->data = n; temp->next = curr->next; curr->next = temp; } ``` ## Deleting an element from a Singly Linked List - **Deletion** is a process to remove an existing node from the linked list. ```C struct node { int data; struct node *next; }; struct node *head, *temp; // Delete a node from the beginning: void deletebeg() { temp = head; head = head->next; free(temp); } // Delete a node from the end of the list: void delete() { struct node *prev; temp = head; while (temp->next != NULL) { prev = temp; temp = temp->next; } if (temp == head) { head = 0; free(temp); } else { prev->next = 0; free(temp); } } // Delete a node from a specified position; void deletomid(int pos) { int cnt = 1; curr = start; while(cnt < pos) { prev = curr; curr = curr->next; cnt++; } prev->next = curr->next; free(curr); } ``` ## Traversing a Singly Linked List - Traversing a linked list is the process of going through all the nodes of a linked list from one end to the other end. - Traversing a list means visiting each node in the list starting from the first node to the last node. ```C curr = start; while (curr != NULL) { printf("%d->", curr->data); curr = curr->next; } } ``` ## Searching a Node in a Linked List - Searching is the process to search for the first occurrence of a given item in the list. - It returns the address of the node. - The search operation helps to find an element in the linked list ### Algorithm: 1. Start 2. Accept the linked list & the data to search. 3. Set *curr* to *start*. 4. While *curr* is not NULL: - If *curr* data is equal to the element, then write "found element", and exit. - Else, set *curr* to *curr -> next*. 5. Write “not found”. 6. Exit ### Pseudocode ```c curr = start; while (curr != null) { if (curr->data == element) { flag = 1; printf("element found"); break; } curr = curr->next; } if (flag == 0) { printf("Element not found "); } ``` ## Application of Linked List - **Dynamic memory allocation** - **Memory management** - Linked list can be used to manage free memory blocks often seen in memory allocation algorithms. - **Graph implementation** - Adjacency list in graph data structures is implemented using linked lists to efficiently represent sparse graphs. - **Maintaining directory of names** - **Making music playlist** - Linked list data structures are frequently used to build music playlists. - **Implementation of stack & queues** - The data structures such as stacks & queues are implementations of linked lists. - **To perform arithmetic operations on large numbers** - **Garbage collection** - Linked lists are used in garbage collection & linked dictionaries.