Data Structures and Algorithms - Old Questions

2. State relative merits and demerits of contiguous list and Linked list. Explain the steps involved in inserting and deleting a node in singly linked list.

Merits of Contiguous List / array

• It is used to represent multiple data items of same type by using only single name.

• It can be used to implement other data structures like linked lists, stacks, queues, trees, graphs etc.

• 2D arrays are used to represent matrices.

• Implementation of list using array is easier as compared other implementation.

Demerits of Contiguous List / array

• The size of the array is fixed. Most often this size is specified at compile time. This makes the programmers to allocate arrays, which seems "large enough" than required.

• Inserting new elements at the front is potentially expensive because existing elements need to be shifted over to make room.

• Deleting an element from an array is not possible. Linked lists have their own strengths and weaknesses, but they happen to be strong where arrays are weak.

• Generally array's allocates the memory for all its elements in one block whereas linked lists use an entirely different strategy. Linked lists allocate memory for each element separately and only when necessary.

Merits of Linked List

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.

Demerits of Linked List

1. They use more memory than arrays because of the storage used by their pointers.

2. Difficulties arise in linked lists when it comes to reverse traversing. For instance, singly linked lists are cumbersome to navigate backwards and while doubly linked lists are somewhat easier to read, memory is wasted in allocating space for a back-pointer.

3. Nodes in a linked list must be read in order from the beginning as linked lists are inherently sequential access.

4. Nodes are stored in-contiguously, greatly increasing the time required to access individual elements within the list, especially with a CPU cache.

Singly linked list is a sequence of elements in which every element has link to its next element in the sequence. For e.g. the following example is a singly linked list that contains three elements 12, 99, & 37.

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

Steps involved in deleting the first node of singly linked list:

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

1. If(head==NULL) then

        print “Void deletion” and exit

2. Store the address of first node in a temporary variable temp.

        temp=head;

3. Set head to next of head.

        head=head->next;

4. Free the memory reserved by temp variable.

        free(temp);

5. End

Steps involved in deleting the last node of singly linked list:

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

1. If(head==NULL) then //if list is empty

        print “Void deletion” and exit

2. else if(head->next==NULL) then //if list has only one node

        Set temp=head;

        print deleted item as,

        printf(“%d” ,head->info);

        head=NULL;

        free(temp);

3. else

        set temp=head;

        while(temp->next->next!=NULL)

            set temp=temp->next;

        End of while

        free(temp->next);

Set temp->next=NULL;

4. End