Is the heap a linked list?
We have introduced the linked list data structure in the previous post and discussed various types of linked lists. We have also covered the applications of linked list data structure and its pros and cons concerning arrays. This post will discuss various linked list implementation techniques in detail and construct a singly linked list in the C programming language. Show Lets start by discussing the structure of a linked list node. Each node of a linked list contains a single data element and a pointer to the next node in the list.
Memory allocation of Linked List nodesThe nodes that will make up the lists body are allocated in the heap memory. We can allocate dynamic memory in C using the malloc() or calloc() function. malloc() takes a single argument (the amount of memory to allocate in bytes). In contrast, calloc() needs two arguments (the total number of variables to allocate in memory and the size in bytes of a single variable). malloc() does not initialize the memory allocated, while calloc() guarantees that all bytes of the allocated memory block have been initialized to 0. To deallocate the allocated memory, we can use free().
Constructing Linked ListThis section covers various methods to construct a linked list. 1. Naive methodA naive solution is to construct individual linked list nodes first and rearrange their pointers later to build the list.
DownloadRun Code 2. Single LineThe above code can be rewritten in a single line by passing the next node as an argument to the newNode() function:
DownloadRun Code 3. Generic MethodThe above-discussed methods will become a pain if the total number of nodes required is huge in the linked list. We can construct a linked list easily using iteration if the keys are given in the form of an array or any other data structure (using its iterator). Following is the implementation of the idea:
DownloadRun Code 4. Standard SolutionThe standard function adds a single node to the head end of any list. This function is called push() since we are adding the link to the head end, making a list look a bit like a stack. Alternately, it could be called InsertAtFront(). Consider the following snippet:
DownloadRun Code
Correct push() code:
DownloadRun Code 5. Make head pointer globalThis approach is not recommended as global variables are usually considered bad practice precisely because of their non-locality: a global variable can potentially be modified from anywhere (unless they reside in protected memory or are otherwise, rendered read-only), and any part of the program may depend on it. Therefore, a global variable has unlimited potential for creating mutual dependencies, and adding mutual dependencies increases complexity. Global variables also make it challenging to integrate modules because others may use the same global names unless names are reserved by agreement or by naming convention.
DownloadRun Code 6. Return head from the push() function
DownloadRun Code
(Hint Locate the last node in the list, and then changing its .next field from NULL to point to the new node, or maintain a tail pointer along with a head pointer to perform insertion in constant time.)
|