Linked List vs Array Notes | Study Programming and Data Structures - Computer Science Engineering (CSE)

Document Description: Linked List vs Array for Computer Science Engineering (CSE) 2022 is part of Programming and Data Structures preparation. The notes and questions for Linked List vs Array have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about Linked List vs Array covers topics like and Linked List vs Array Example, for Computer Science Engineering (CSE) 2022 Exam. Find important definitions, questions, notes, meanings, examples, exercises and tests below for Linked List vs Array.

Introduction of Linked List vs Array in English is available as part of our Programming and Data Structures for Computer Science Engineering (CSE) & Linked List vs Array in Hindi for Programming and Data Structures course. Download more important topics related with notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free. Computer Science Engineering (CSE): Linked List vs Array Notes | Study Programming and Data Structures - Computer Science Engineering (CSE)
1 Crore+ students have signed up on EduRev. Have you?

Arrays store elements in contiguous memory locations, resulting in easily calculable addresses for the elements stored and this allows a faster access to an element at a specific index. Linked lists are less rigid in their storage structure and elements are usually not stored in contiguous locations, hence they need to be stored with additional tags giving a reference to the next element. This difference in the data storage scheme decides which data structure would be more suitable for a given situation. 

Data storage scheme of an arrayData storage scheme of an array

Data storage scheme of a linked listData storage scheme of a linked list

Major differences are listed below:

  • Size: Since data can only be stored in contiguous blocks of memory in an array, its size cannot be altered at runtime due to risk of overwriting over other data. However in a linked list, each node points to the next one such that data can exist at scattered (non-contiguous) addresses; this allows for a dynamic size which can change at runtime.
  • Memory allocation: For arrays at compile time and at runtime for linked lists. but, dynamically allocated array also allocates memory at runtime.
  • Memory efficiency: For the same number of elements, linked lists use more memory as a reference to the next node is also stored along with the data. However, size flexibility in linked lists may make them use less memory overall; this is useful when there is uncertainty about size or there are large variations in the size of data elements; memory equivalent to the upper limit on the size has to be allocated (even if not all of it is being used) while using arrays, whereas linked lists can increase their sizes step-by-step proportionately to the amount of data.
  • Execution time: Any element in an array can be directly accessed with its index; however in case of a linked list, all the previous elements must be traversed to reach any element. Also, better cache locality in arrays (due to contiguous memory allocation) can significantly improve performance. As a result, some operations (such as modifying a certain element) are faster in arrays, while some other (such as inserting/deleting an element in the data) are faster in linked lists.

Following are the points in favour of Linked Lists:

  1. The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage, and in practical uses, the upper limit is rarely reached.
  2. Inserting a new element in an array of elements is expensive because a room has to be created for the new elements and to create room existing elements have to be shifted.  
    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.

So Linked list provides the following two advantages over arrays:

  1. Dynamic size
  2. Ease of insertion/deletion

Linked lists have following drawbacks: 

  1. Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do a binary search with linked lists. 
  2. Extra memory space for a pointer is required with each element of the list. 
  3. Arrays have better cache locality that can make a pretty big difference in performance.
The document Linked List vs Array Notes | Study Programming and Data Structures - Computer Science Engineering (CSE) is a part of the Computer Science Engineering (CSE) Course Programming and Data Structures.
All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)

Related Searches

Free

,

pdf

,

Summary

,

Extra Questions

,

mock tests for examination

,

video lectures

,

Important questions

,

ppt

,

Sample Paper

,

Exam

,

Linked List vs Array Notes | Study Programming and Data Structures - Computer Science Engineering (CSE)

,

shortcuts and tricks

,

practice quizzes

,

study material

,

past year papers

,

Objective type Questions

,

Previous Year Questions with Solutions

,

Linked List vs Array Notes | Study Programming and Data Structures - Computer Science Engineering (CSE)

,

Viva Questions

,

Semester Notes

,

Linked List vs Array Notes | Study Programming and Data Structures - Computer Science Engineering (CSE)

,

MCQs

;