Memory allocation in linked list in data structure
Linked lists are the best and simplest example of a dynamic data structure that uses pointers for its implementation. However, understanding pointers is crucial to understanding how linked lists work, so if you've skipped the pointers tutorial, you should go back and redo it. You must also be familiar with dynamic memory allocation and structures. Show
Essentially, linked lists function as an array that can grow and shrink as needed, from any point in the array. Linked lists have a few advantages over arrays:
However, linked lists also have a few disadvantages:
What is a linked list?A linked list is a set of dynamically allocated nodes, arranged in such a way that each node contains one value and one pointer. The pointer always points to the next member of the list. If the pointer is NULL, then it is the last node in the list. A linked list is held using a local pointer variable which points to the first item of the list. If that pointer is also NULL, then the list is considered to be empty. ------------------------------ ------------------------------ | | | \ | | | | DATA | NEXT |--------------| DATA | NEXT | | | | / | | | ------------------------------ ------------------------------Let's define a linked list node: typedef struct node { int val; struct node * next; } node_t;Notice that we are defining the struct in a recursive manner, which is possible in C. Let's name our node type node_t. Now we can use the nodes. Let's create a local variable which points to the first item of the list (called head). node_t * head = NULL; head = (node_t *) malloc(sizeof(node_t)); if (head == NULL) { return 1; } head->val = 1; head->next = NULL;We've just created the first variable in the list. We must set the value, and the next item to be empty, if we want to finish populating the list. Notice that we should always check if malloc returned a NULL value or not. To add a variable to the end of the list, we can just continue advancing to the next pointer: node_t * head = NULL; head = (node_t *) malloc(sizeof(node_t)); head->val = 1; head->next = (node_t *) malloc(sizeof(node_t)); head->next->val = 2; head->next->next = NULL;This can go on and on, but what we should actually do is advance to the last item of the list, until the next variable will be NULL. Iterating over a listLet's build a function that prints out all the items of a list. To do this, we need to use a current pointer that will keep track of the node we are currently printing. After printing the value of the node, we set the current pointer to the next node, and print again, until we've reached the end of the list (the next node is NULL). void print_list(node_t * head) { node_t * current = head; while (current != NULL) { printf("%d\n", current->val); current = current->next; } }Adding an item to the end of the listTo iterate over all the members of the linked list, we use a pointer called current. We set it to start from the head and then in each step, we advance the pointer to the next item in the list, until we reach the last item. The best use cases for linked lists are stacks and queues, which we will now implement: Adding an item to the beginning of the list (pushing to the list)To add to the beginning of the list, we will need to do the following:
This will effectively create a new head to the list with a new value, and keep the rest of the list linked to it. Since we use a function to do this operation, we want to be able to modify the head variable. To do this, we must pass a pointer to the pointer variable (a double pointer) so we will be able to modify the pointer itself. void push(node_t ** head, int val) { node_t * new_node; new_node = (node_t *) malloc(sizeof(node_t)); new_node->val = val; new_node->next = *head; *head = new_node; }Removing the first item (popping from the list)To pop a variable, we will need to reverse this action:
Here is the code: int pop(node_t ** head) { int retval = -1; node_t * next_node = NULL; if (*head == NULL) { return -1; } next_node = (*head)->next; retval = (*head)->val; free(*head); *head = next_node; return retval; }Removing the last item of the listRemoving the last item from a list is very similar to adding it to the end of the list, but with one big exception - since we have to change one item before the last item, we actually have to look two items ahead and see if the next item is the last one in the list: int remove_last(node_t * head) { int retval = 0; /* if there is only one item in the list, remove it */ if (head->next == NULL) { retval = head->val; free(head); return retval; } /* get to the second to last node in the list */ node_t * current = head; while (current->next->next != NULL) { current = current->next; } /* now current points to the second to last item of the list, so let's remove current->next */ retval = current->next->val; free(current->next); current->next = NULL; return retval; }Removing a specific itemTo remove a specific item from the list, either by its index from the beginning of the list or by its value, we will need to go over all the items, continuously looking ahead to find out if we've reached the node before the item we wish to remove. This is because we need to change the location to where the previous node points to as well. Here is the algorithm:
There are a few edge cases we need to take care of, so make sure you understand the code. int remove_by_index(node_t ** head, int n) { int i = 0; int retval = -1; node_t * current = *head; node_t * temp_node = NULL; if (n == 0) { return pop(head); } for (i = 0; i < n-1; i++) { if (current->next == NULL) { return -1; } current = current->next; } if (current->next == NULL) { return -1; } temp_node = current->next; retval = temp_node->val; current->next = temp_node->next; free(temp_node); return retval; }ExerciseYou must implement the function remove_by_value which receives a double pointer to the head and removes the first item in the list which has the value val.
Linked lists are one of the most important data structures and these are the ones asked most in an interview. In this article, we are going to look into how types of linked lists. Data StructureA data structure is structuring and organizing data in a simple way so that data can be easily manipulated and managed. One example is accessing and inserting data in file systems and databases. The type of data structure to be used depends on various factors, such as the type of data, data access method e.g., serial access or random access, frequency of access, etc. Linked ListA linked list is a type of data structure consisting of nodes. Each node consists of the Value – this is the actual data. This can be an integer, float, string or a custom object such as a structure or a class object Pointer – each node points to the next node within a single linked list object. The final node points to NULL. A linked list is very similar to an array in the sense that it looks like a series of continuous data storage. However, there are some crucial differences between the two and each has its own advantages over the other. Memory AllocationArrayArrays are allocated a series of memory. For eg., if an integer array has 10 elements and the starting address of an array is 100, then the final element will be stored at address 136. Linked ListLinked lists elements may not be stored in contiguous memory. The pointer at each node helps to identify the location of the next node. SizeArrayDue to the contiguous memory allocation, the size of an array must be predetermined. This usually leads to memory wastage as there is an overcompensation to avoid shortage. Linked ListThere is no need to determine the size of a linked list. This not only avoids memory wastage but is very useful when a programmer is unaware of how large the linked list can grow. Insertion/DeletionArrayInserting or deleting an element in an array can be challenging if it is not the last element. Inserting or deleting an element in the middle of an array required moving the elements after that as well. In the worst-case scenario, if an element must be inserted at the beginning of the array then all elements must first be shifted one element to the right and only then can the new element be added. This may seem trivial for small arrays. However, if the array size is very large, this action itself will consume time and resources. Linked ListInserting or deleting an element in the middle does not require modifying other elements. A new node needs to be created and the pointer of the previous element needs to be updated. This simplifies the insertion/deletion process and makes the linked list more suitable for scenarios that are frequently updated. Random AccessArrayWhen the position of the element is known, a read operation can be performed in O(1) time. Linked ListRandom access is not possible in a linked list. Even if the position is known before-hand the linked list must be traversed until that element. This becomes an issue when the size of the linked list is huge and the element to be found is in the last. Cache LocalityArrayArrays have better cache locality since they have contiguous memory locations. Consider an array that is accessed for reading. Once the first element is accessed, the next elements of the array can be cached for future usages, thereby reducing the read time. This saves time and resources Linked ListSince the elements are randomly stored, it is a challenge to cache the linked list.
Table 1: Array vs Linked list Table 1, provides a summary of the differences between array and linked list Types Of Linked ListSingly Linked ListThe singly-linked list is a simple linked list, where each node points to the next node and the final node points to NULL. Figure 2: Single Linked List Below is the code to create a singly linked list and perform insert, delete update and print operations. Doubly Linked ListA doubly linked list is the linked list in which each node points to both the next element and the previous element. Figure 3: Doubly Linked List Note that the first element has its previous pointer to NULL and the last element has its next pointer to NULL. Circular Linked ListA circular linked list can be singly or doubly linked list, depending on whether it has a previous pointer or not. But the last element points back to the first element, thereby, creating a circle. Figure 4: Circular Linked List If you like the article please share and subscribe. This is all for now in types of linked lists. You can also look into this.
Algorithms: Mirror a Binary tree using python |