Question: What are the advantages of using linked lists over an array?
0

Mumbai University > Computer Engineering > Sem 3 > Data Structures

Marks: 5M

Years: May 2016

ADD COMMENTlink
modified 4 months ago by gravatar for Sagar Narkar Sagar Narkar1.5k written 2.1 years ago by gravatar for Pooja Joshi Pooja Joshi710
0
  1. Dynamic size As the size of linked list is not fixed so we can add or remove as much elements as required. But in array we have to pre-define the array size which we can’t change later.

  2. Ease of insertion/deletion

    • Inserting a new element in an array of elements is expensive; because room has to be created for the new elements and to create room existing elements have to shift.

    • For example, suppose we maintain a sorted list of IDs in an array id [].

      id [] = [1000, 1010, 1050, 2000, 2040, …..].

    • And if we want to insert a new ID 1005, then to maintain the sorted order, we have to move all the elements after 1000 (excluding 1000).

    • Deletion is also expensive with arrays until unless some special techniques are used. For example, to delete 1010 in id [], everything after 1010 has to be moved.

ADD COMMENTlink
written 2.1 years ago by gravatar for Pooja Joshi Pooja Joshi710
0

Advantages of Linked List

Dynamic Data Structure

Linked list is a dynamic data structure so it can grow and shrink at runtime by allocating and deallocating memeory. So there is no need to give initial size of linked list.

Insertion and Deletion

Insertion and deletion of nodes are really easier. Unlike array here we don’t have to shift elements after insertion or deletion of an element. In linked list we just have to update the address present in next pointer of a node.

No Memory Wastage

As size of linked list can increase or decrease at run time so there is no memory wastage. In case of array there is lot of memory wastage, like if we declare an array of size 10 and store only 6 elements in it then space of 4 elements are wasted. There is no such problem in linked list as memory is allocated only when required.

Implementation

Data structures such as stack and queues can be easily implemented using linked list.

ADD COMMENTlink
modified 4 months ago  • written 4 months ago by gravatar for Sagar Narkar Sagar Narkar1.5k
Please log in to add an answer.