Interview Questions on Linked Lists in Data Structures Set 1

Linked Lists interview questions for beginners. Answers to all of them have been provided. This is subjective type short answers question and answer set no. 1 in this series.

Last Reviewed and Updated on August 18, 2019
Posted by Parveen(Hoven),
Aptitude Trainer and Software Developer

Advertisement

Interview and Exam Questions and Answers

This set contains a list of commonly asked questions. They are short interview questions aimed at freshers interview, campus placement drives, and also for job interviews. You can use these to have a quick grasp and brush-up of your fundamentals. These questions can be viewed on a mobile phone also because this website is built on responsive web design.

How singly-linked list is represented in a program?

A linked list is represented in a program by defining two classes:

a) Node class: A node is the basic building block in a linked list.The Node class represents a node in a linked list

b) List class: This class consists of a set of operations implemented on a linked list. These operations are insertion, deletion, search, and traversal.

What do you mean by linked list?

Linked lists are flexible data structure that provide a convenient way to store data. In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference to the next node in the sequence; more complex variants add additional links. This structure allows for efficient insertion or removal of elements from any position in the sequence.

Advertisement

Write an algorithm for traversing a doubly-linked list.

It enables to traverse a list in forward as well as backward direction.

The algorithm for traversing it in forward directions as follows:
  1. Mark the first node in the list as currentNode.
  2. Repeat steps 3 and 4 until currentNode becomes NULL.
  3. Display the information contained in the node marked as currentNode.
  4. Make currentNode point to the next node in sequence.

The algorithm for traversing it in backward directions as follows:
  1. Mark the last node in the list as currentNode.
  2. Repeat steps 3 and 4 until currentNode becomes NULL.
  3. Display the information contained in the node marked as currentNode.
  4. Make currentNode point to the node preceding it .

What is the difference between a singly linked list and circular linked list?

In a singly linked list, the last node points to Null. However, in a circular linked list, the last node point to the first node of the the list, forming the circular structure.

What operations are implemented in a linked list?

Various operations implemented on a linked list are insert, delete, traverse and search.

What do you mean by linked list?

Linked lists are flexible data structure that provide a convenient way to store data. In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference to the next node in the sequence; more complex variants add additional links. This structure allows for efficient insertion or removal of elements from any position in the sequence.

How a circular-linked list is traversed and also write algorithm.

For traversing a circular linked-list, we need a variable/pointer to track currentNode, which initially points to the first node in the list.

The algorithm for traversing a circular linked list is as follows:
  1. Make currentNode point to the successor of the node marked as LAST, such that currentNode points to the first node in the list.
  2. Repeat step 3 and 4 until currentNode=LAST.
  3. Display the information contained in the node marked as currentNode.
  4. Make currentNode point to the next node in its sequence.
  5. Display the information contained in the node marked as LAST.

Write an algorithm to delete a node between two nodes in the circular-linked list.

The algorithm to delete a node between two nodes in the circular-linked list:

  1. Locate the node to be deleted. Mark the node to deleted as current, and its predecessor as previous. To locate current and previous, execute the following steps:
    1. Make previous point to the successor of LAST
    2. Make current point to the successor of LAST
    3. Repeat steps d and e until either the node is found, or previous=LAST
    4. Make previous point to current
    5. Make current point to the next node in sequence
  2. If previous=LAST:
    1. Display "Node not found"
    2. Go to Step 5
  3. Make the next field of previous point to the successor of current
  4. Release the memory for the node marked as current
  5. Exit

Write algorithm for inserting node between two nodes in Singly-Linked list, if list is not empty .

The algorithm for inserting node between two nodes in the list is as follows:

  1. Identify the nodes between which the new node is to be inserted. Mark them as previous and current. To locate previous and current, execute the following steps:
    1. Make current point to the first node
    2. Make previous point to NULL.
    3. Repeat step d and e until current.info becomes greater than new node.info or current becomes equal to NULL.
    4. Make previous point to current.
    5. Make current point to the next node in sequence.
  2. Allocate memory for the new node.
  3. Assign value to the data field of the new node.
  4. Make the next field of the new node point to current.
  5. Make the next field of previous point to the new node.

Write an algorithm fo deleting a node between two nodes in the doubly-linked list.

The algorithm to delete a node between two nodes in the list is as follows:

  1. Make the node to be deleted as current and its predecessor as previous. To locate previous and current, execute the following steps:
    1. Make previous point to NULL.
    2. Make current point to the first node in the linked list.
    3. Repeat steps d and e until either the node is found or current becomes NULL.
    4. Make previous point to current.
    5. Make current point to the next node in sequence.
  2. Make the next field of previous point to the successor of current
  3. Make the prev field of the successor of current point to previous
  4. Release the memory of the node marked as current.

My C/C++ Videos on Youtube

Here is the complete playlist for video lectures and tutorials for the absolute beginners. The language has been kept simple so that anybody can easily understand them. I have avoided complex jargon in these videos.