Advantages of Linked Lists over Arrays
1. A linked list is a dynamic data structure therefore, the primary advantage of linked lists over arrays is that linked lists can grow or shrink in size during the execution of a program i.e. runtime but arrays is a static data structure therefore, the size remain fixed. In arrays we would need to allocate all the storage in starting.
2. There is no need to specify how many number of nodes required so linked list does not waste memory space. We can allocate and de-allocate memory space at runtime.
3. The most important advantage is that the linked lists provide flexibility is allowing the items to be rearranged efficiently. In linked list it is easier to insert or delete items by rearranging the pointers but in arrays insertion and deletion requires large movement of data.
Disadvantages of Linked Lists over Arrays
1. A linked list will use more memory storage than arrays with the same number of elements is used because each time linked list has more memory for an additional linked field or next pointer field.
2. Arrays elements can be randomly accessed by giving the appropriate index, while linked list elements cannot randomly accessed.
3. Binary search cannot be applied in a linked list.
4. A linked list takes more time in traversing of elements.
Difference between Arrays and Linked Lists
|
S.No.
|
Arrays
|
Linked Lists
|
|
1.
|
Arrays is static data structure means its size can't be increased or decreased on runtime
|
Linked list is dynamic data structure means its size can be modified on runtime
|
|
2.
|
If we are confirm to use n fixed block and it is not going to change in a program, so arrays is better
|
If we are confirm to use n fixed block then linked list use extra space for pointer to next node and it waste 2*n bytes of memory space.
|
|
3.
|
Arrays is simpler to use
|
Linked list is a complex data structure and it is used basically for complex programming
|
|
4.
|
In arrays, insertion and deletion consequences as large amount of data movements
|
In linked list, insertion and deletion doesn't need so much data movements
|
Dynamic Memory Allocation Functions
|
S.No.
|
Function Name
|
Meaning
|
|
1.
|
sizeof()
|
This function gives the size of its arguments in terms of bytes. The arguments can be variable, arrays, structure etc.
|
|
2.
|
malloc()
|
The malloc() function allocates a request size of bytes and returns a pointer to the first byte of the allocated space.
|
|
3.
|
calloc()
|
The calloc() function is used to allocates space for an array of elements, initializes them to zero and then returns a pointer to the memory.
|
|
4.
|
realloc()
|
The realloc() function is used to reallocate space which is defined by the malloc() or calloc() so modifies the size of previously allocated space.
|
|
5.
|
free()
|
The free() function is used for efficient use of memory we can also release the memory space that is not required.
|
Allocating Memory by using malloc() function
A block of memory may be allocated using the malloc() function. The malloc() function reserves a block of memory of specified size and returns a pointer of type void. This means that we can assign it to any type of pointer so for that we have to cast it in any type like int, char, float, double, struct type etc.
Syntax for malloc():
ptr=(datatype *)malloc(specified-size);
Example:
int ptr;
ptr=(int*)malloc(10*sizeof(int));
We may also use malloc() function to allocate memory to the complex data type like structures.
struct *str;
str=(struct node*)malloc(sizeof(struct node));
Note: The malloc() function allocates a block of contiguous bytes. The allocation can fail if the space in the heap is not sufficient to fulfill the request and it returns a NULL. We can check for successful the memory pointer variable. The malloc() function allocates a single block of storage space and have a default value as garbage.