What do you mean by linked list? Discus the advantage of linked list over array. Write an algorithm to insert and delete an item in the singly linked list.
Answer: – A linked list is a linear data structure which can store data in a sequence. Linked list data structure allocate memory dynamically which increase. Or decrease at any time. A linked list data structure can be defined as a collection of nodes. Each node has two parts such as information and pointer to next node.
Information part may consist of one or more than one fields. In other word a linked list consists of series of structure, which are not necessary contiguous. Each structure contains one or more than one contiguous information fields and a pointer to a structure containing its successor. The last node of the list contains NULL or ‘\0’ to the pointer field. The pointer contains the address of the location where next information is stored. A linked list also contains a list pointer variable called start, which contains the address of the first node in the list hence, there is an arrow drown from start to the first node in the linked list. If there is no node in the list, the list is called NULL list or empty list structure of singly linked is: –
To create a linked list, follow the following steps: –
- Declare the structure that defines the list eateries.
- Declare the variables start and *node.
- Assign start next=NULL an empty list
- Find each list entry
- Find end of the list so that node->next is NULL
- Allocate memory for the new entry by assigning it to node->next
- Assign the member values to node
- Assign node->next the value NULL to indicate the end of the list.
The linked list data structure allocates memory dynamically whereas arrays allocate memory statically and so that in linked list, memory is required at run time but in array memory is required at compile time. This memory allocation of linked list over array is major advantage and so that in linked list data structure, memory allocation is flexible means when we insert node into linked list, memory increased and when we delete node, memory space decreased according by. This facility is not available in array and so that before using of array to store data in memory allocation, size of memory must be specified. And in the case, if number of data is more than specified size, memory ignores that data and if less data stored in memory, remaining spaces are unused.
In the linked list data structure, insertion of node is possible of any position. In the given algorithm, we can insert node at the beginning of linked list.
Step 1: [Check for free space] If new1=NULL output “OVER FLOW” and EXITE Step 2: [Allocate free space] New1=Create new node Step 3: [Read value of information part of a new node] Info[New1]=value. Step 4: [Link address part of the currently created node with the address of start] Next[New1]=start Step 5: [New assign address of newly created node to the start] Start=new1 Step 6: Exit
Similarly insertion, deletion is also possible from beginning, from end or from any other position In the linked list. Here we delete first node using an algorithm.
Step 1: [Initialization] Node=start Next [Position to the first node in the list] Previous=Assign address of start Step 2: [Perform deletion operation] If node=NULL Output=”UNDERFLOW” and exit Else [Delete first node] Next [Previous]=Next[node] [Move pointer to next node in the list] Free the space associated with node. Step 3: Exit