Difference between Linked List and Arrays

05 min read

Arrays and Linked Lists are both linear data structures, but both have some advantages and disadvantages over each other. Now let us look at the difference between arrays and linked list.

For example, an array is a datatype which is widely implemented as a default type, in most of the modern programming languages, which are used to store data of similar type. But, there are many cases, like the one where we don't know the quantity of data to be stored, for which some other data structures like Linked Lists can be used.

difference between arrays and linked list

 

Arrays Vs Linked Lists

The following are some of the differences between Arrays and Linked Lists:

ARRAYS

LINKED LISTS

An array is a collection of elements of a similar data type.

Linked List is an ordered collection of elements of the same type in which each element is connected to the next using pointers.

Array elements can be accessed randomly using the array index.

Random accessing is not possible in linked lists. The elements will have to be accessed sequentially.

Data elements are stored in contiguous locations in memory.

New elements can be stored anywhere and a reference is created for the new element using pointers.

Insertion and Deletion operations are costlier since the memory locations are consecutive and fixed. 

Insertion and Deletion operations are fast and easy in a linked list.

Memory is allocated during the compile time (Static memory allocation).

Memory is allocated during the run-time (Dynamic memory allocation).

Size of the array must be specified at the time of array declaration/initialization.

Size of a Linked list grows/shrinks as and when new elements are inserted/deleted.

 

Advantages of Linked Lists

  • Size of linked lists is not fixed, they can expand and shrink during run time.
  • Insertion and Deletion Operations are fast and easier in Linked Lists.
  • Memory allocation is done during run-time (no need to allocate any fixed memory).
  • Data Structures like Stacks, Queues, and trees can be easily implemented using Linked list.

 

Disadvantages of Linked Lists

  • Memory consumption is more in Linked Lists when compared to arrays. Because each node contains a pointer in linked list and it requires extra memory.
  • Elements cannot be accessed at random in linked lists.
  • Traversing from reverse is not possible in singly linked lists.

 

Applications of Linked Lists

  • Linked Lists can be used to implement Stacks, Queues and Trees.
  • Linked Lists can be also used to implement Graphs. (Adjacency list representation of Graph).
  • Linked Lists can be used to Implement Hash Tables - Each Bucket of the hash table can be a linked list (Open chain hashing).
POST A NEW COMMENT
     
  • Input (stdin)

    Output (stdout)


    Input (stdin)

    Your Output (stdout)

    Expected Output

    Compiler Message

    Input (stdin)

    2    3

    Your Output (stdout)

    5

    Expected Output

    5

    Compiler Message

    5

    Error