Data Structures and Algorithms - Old Questions

8. What are the benefits of using linked list over array? How can you insert a node in a singly linked list?

Linked lists and arrays are similar since they both store collections of data. Array is the most common data structure used to store collections of elements. Arrays are convenient to declare and provide the easy syntax to access any element by its index number. Once the array is set up, access to any element is convenient and fast.

The benefits of  using linked list over array are:

1. Linked lists are dynamic data structures. i.e., they can grow or shrink during the execution of a program.

2. Linked lists have efficient memory utilization. Here, memory is not preallocated. Memory is allocated whenever it is required and it is de-allocated (removed) when it is no longer needed.

3. Insertion and Deletions are easier and efficient. Linked lists provide flexibility in inserting a data item at a specified position and deletion of the data item from the given position.

4. Many complex applications can be easily carried out with linked lists.

5. There is no need to define an initial size for a Linked list.

6. Linked List reduces the access time.

Steps involved in inserting a node at the beginning of singly linked list:

let *head be the pointer to first node in the current list

1. Create a new node using malloc function

        NewNode=(NodeType*)malloc(sizeof(NodeType));

2. Assign data to the info field of new node

        NewNode->info=newItem;

3. Set next of new node to head

        NewNode->next=head;

4. Set the head pointer to the new node

        head=NewNode;

5. End

Steps involved in inserting a node at the end of the singly linked list:

let *head be the pointer to first node in the current list

1. Create a new node using malloc function

        NewNode=(NodeType*)malloc(sizeof(NodeType));

2. Assign data to the info field of new node

        NewNode->info=newItem;

3. Set next of new node to NULL

        NewNode->next=NULL;

4. if (head ==NULL)then

        Set head =NewNode.and exit.

5. Set temp=head;

6 while(temp->next!=NULL)

        temp=temp->next;     //increment temp

7. Set temp->next=NewNode;

8. End