Basic CS-Data Structures [3i Infotech Placement]: Sample Questions 25 - 25 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 25

Data Structures
Edit

Describe in Detail

Essay▾

How to implement linked list with array vs. structure with pointers.

Explanation

Implement linked list with array:

Struct Node

{

int data;

int link;

}

  • Data stores the info and “link” stores the index in the array of next node.

    Linked list have the bellowing complexity:

    • Access: O (1)
    • Append: O (n)
    • Index: O (n)
  • A linked list API implemented in terms of arrays will behave like an array.
  • Linked list or tree of strict arrays can be implemented using ropes or finger trees or lazy sequences.

Limitations:

  • Dead space in the array not used currently- items taking up memory.
  • Hard to track of free entries after a few insertions and deletion- these free entries could be anywhere.
  • Using array will impose an upper limit on the size of the linked list- or using dynamic allocation it would need to copy the entire old array to new larger location for new array.

Implementation of Linked list with pointer:

  • Linked list with pointer overcomes the limitation of array implementation- at the cost of extra space for pointer.
  • The links are stored at different locations allocated dynamically, with the previous link containing the link to next.

    Limitations:

  • With the for loop in insert_node (char, struct ⚹⚹) function and traverse (struct ⚹) function both of which never seem to terminate.

Developed by: