Basic CS-Data Structures [3i Infotech Placement]: Sample Questions 31 - 32 of 52

Glide to success with Doorsteptutor material for competitive exams : get questions, notes, tests, video lectures and more- for all subjects of your exam.

Question 31

Data Structures
Edit

Describe in Detail

Essay▾

How does a doubly-linked list differ from a singly linked one?

Explanation

Linked List vs Doubly-Linked List
Difference between Singly and Doubly Linked List
Singly Linked ListDoubly Linked List
  • Allow one way travel- can access successor
  • Allows two way travel using two pointers next and previous
  • Uses less memory per node
  • Uses more memory per node than singly linked list
  • Complexity of insertion and deletion at known position is O (n)
  • Complexity of Insertion and Deletion at known position is O (1) .
  • There is a allowing delete from a singly-linked list in O (1) , but the list must be circular
  • Used in places where singly-linked lists would not work but they require slightly more “housekeeping” , and are slightly less efficient on insertions as the result
  • Each node contains at least two parts:
    1. Info
    2. link
  • Each node contains at least three parts:
  1. Info
  2. Link to next node
  3. Link to previous node.

Question 32

Data Structures
Edit

Describe in Detail

Essay▾

Describe the features of a linked list. When would you can one?

Explanation

The Linked List

Features of a linked list:

  • Dynamic data structure- grows and shrinks during run time.
  • Insertion and deletion operation are easier.
  • Efficient memory utilization- array can have holes depending on max size vs. average size
  • Faster access time.
  • Linear data structures like stacks, queues can easily be implemented using link list.

Developed by: