Data Structures and Algorithms - Old Questions

2. What is linked list? Explain the process of inserting and removing nodes from a linked list.

A linked list is a non-sequential collection of data items (nodes). It is a dynamic data structure. For every data item in a linked list, there is an associated pointer that would give the memory location of the next data item in the linked list. The data items in the linked list are not in consecutive memory locations. They may be anywhere, but the accessing of these data items is easier as each data item contains the address of the next data item.

Each node (data item) consists of two parts:

      • Info: the actual element to be stored in the list. It is also called data field.

      • Link: one or two links that points to next and previous node in the list. It is also called next or pointer field.

info   next                                         

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