LINKED LIST

 LINKED LIST

The major drawback of an array is that the number of elements must be known in advance. Hence an alternative approach was required. This give rise to the concept called linked list

   

Linked list is a dynamic data structure in which elements (called nodes) form a sequential list.

• A node contains two fields i.e. data stored at that particular address and the pointer which contains the address of the next node in the memory. 
• The last node of the list contains pointer to the null.

Array contains following limitations:

1. The size of array must be known in advance before using it in the program. 

2. Increasing size of the array is a time taking process. It is almost impossible to expand the

size of the array at run time. 

3. All the elements in the array need to be contiguously stored in the memory. Inserting any

element in the array needs shifting of all its predecessors.

 Using linked list is useful because, 

1. It allocates the memory dynamically. All the nodes of linked list are non-contiguously stored in the memory and linked together with the help of pointers. 

2. Sizing is no longer a problem since we do not need to define its size at the time of

declaration. List grows as per the program's demand and limited to the available memory

space.

Differences between the array and linked list :

Dynamic memory allocation functions, you must include the header file stdlib.h.

malloc()

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.

The general syntax of malloc() is

ptr =(cast-type*)malloc(byte-size);

calloc():

calloc() function is another function that reserves memory at the run time. It is normally used to request multiple blocks of storage each of the same size and then sets all bytes to zero. calloc() stands for contiguous memory allocation and is primarily used to allocate memory for arrays.

The syntax of calloc() can be given as:

ptr=(cast-type*) calloc(n,elem-size);

free():

The free() is used to release the block of memory.

The general syntax of the free()function is,

free(ptr);

where ptr is a pointer that has been created by using malloc() or calloc(). When memory is deallocated using free(), it is returned back to the free list within the heap.

realloc():

At times the memory allocated by using calloc() or malloc() might be insufficient or in excess.

In both the situations we can always use realloc() to change the memory size already allocated by calloc() and malloc(). This process is called reallocation of memory. 

The general syntax for realloc() can be given as,

ptr = realloc(ptr,newsize);

The following are the types of linked list: 

1. Singly linked list 

2. Doubly linked list 

3. Circular linked list

Singly Linked list:

The singly linked list is a data structure that contains two parts, i.e., one is the data part, and the other one is the address part, which contains the address of the next or the successor node. The address part in a node is also known as a pointer. The pointer that holds the address of the initial node is known as a head pointer.

In this list, only forward traversal is possible; we cannot traverse in the backward direction as it has only one link in the list.

 Representation of the node in a singly linked list

struct node 

{

int data;

struct node *next; 

}

a node containing two members, the first one is data of integer type, and the other one is the pointer (next) of the node type.

Doubly linked list:

Doubly linked list contains two pointers We can define the doubly linked list as a linear data structure with three parts: the data part and the other two address part (pointer to its previous node, and a pointer to the next node.) .

As we can observe in the above figure, the node in a doubly-linked list has two address parts. one part stores the address of the next while the other part of the node stores the previous node's address. The initial node in the doubly linked list has the NULL value in the address part, which provides the address of the previous node.

Representation of the node in a doubly linked list:

struct node

{

int data;

struct node *next;

struct node *prev; 

}

a node with three members, one is data of integer type, and the other two are the pointers, i.e., next and prev of the node type. The next pointer variable holds the address of the next node, and the prev pointer holds the address of the previous node.

Circular linked list:

Circular linked list is a list in which the last node connects to the first node, so the link part of the last node holds the first node's address. The circular linked list has no starting and ending node. We can traverse in any direction, i.e., either backward or forward.

Representation of the node in a circular linked list

struct node 

{

int data;

struct node *next; 

}