Are Linked Lists Slow Because They Arent Continuous in Memory

Ever wondered, How data is stored inside the computer's memory? You can't just throw data into the memory without making proper structure for the data.

To provide a organised structure for the data to get stored inside the computer's memory so that we can use and manage the stored data in the most efficient way possible, we use Data Structures.

All programming languages provide fundamental data structures like int, char, float etc. to store the primitive type values. But with the use of user defined data types we can create data structure as required. It is like creating our home with bricks, we can make any type of structure we want.

Here in this article we will see two most commonly used user defined data types: Arrays and Linked List, Difference between Array and Linked List and their implementation.

Array

The simplest type of data structure is Array which is used to store set of similar data in continuous blocks of memory under a common heading or variable name. With its simplicity comes some barriers like it need continuous block of memory and if free memory is not available in contiguous block it becomes inefficient to use arrays.

Array Representation (Source)

Arrays indexing starts with 0, and every element of the array can be accessed using its index. Operation on array is very fast as any element can accessed directly using array indexing. Name of array is the base address of the array and all other elements can be accessed using the base address because the memory allocated to array is consecutive.

Linked List

On the other hand, a simple yet very useful data structure which doesn't need contiguous blocks of memory is Linked List. They are used in situations when there is need to allocate memory dynamically that is during runtime of a program. It can be visualized like a train where we have an Engine (Head) and all the carriages(nodes) are linked to the train engine either directly or indirectly through other carriages.

Linked list Representation (Source)

Linked list is user-defined data type where all the nodes of the list are linked using pointers. To access any node of the list, we must traverse the list linearly unlike array where we can directly access the elements.

Array vs Linked List – Difference between Array and Linked List

Parameters	Array	Linked List
Definition	It is a collection of elements having same data type with a common name.	It is an ordered collection of elements which are connected by links or pointers.
Size	Fixed, once declared cannot be changed.	Variable, can be changed during run-time.
Memory Allocation	Require Contiguous blocks of memory.	Random memory can be allocated.
Access	Direct or randomly accessed, i.e., Specify the array index or subscript.	Sequentially accessed, i.e., Traverse starting from the first node in the list by the pointer.
Insertion and Deletion	Relatively slow, as to insert or delete any element, other elements need to be shifted to occupy the empty space or make space.	Faster, Easier and Efficient as just linking or unlinking of node is required.
Searching	Binary search and Linear search	Linear search
Extra Space	Extra space is not required.	To link nodes of list, pointers are used which require extra Space.
Memory Utilization	Inefficient	Efficient
Types	It can be single dimensional, two dimensional or multi-dimensional.	It can be singly, doubly or circular linked list.

Array Implementation in C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

#include<iostream> using namespace std ; int main ( ) { int arr [ 5 ] ; // declaration an integer array of size 5 arr [ 0 ] = 5 ; // assigning values to the array elements arr [ 1 ] = 4 ; //  notice that array indexing starts from 0 and ends at size-1 arr [ 2 ] = 3 ; arr [ 3 ] = 2 ; arr [ 4 ] = 1 ; for ( int i = 0 ; i < 5 ; i ++ ) cout << arr [ i ] << " " ; // printing array elements return 0 ; }

Output

5 4 3 2 1

Linked List Implementation in C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

#include<iostream> using namespace std ; /* Creating user defined structure for storing data in linked list */ struct Node { int data ; struct Node * next ; // pointer to link nodes of the list } ; struct Node * head = NULL ; // Initially their is no element in list, so head point nowhere /* function to insert and link nodes to the list */ void insert ( int new_data ) { struct Node * new_node = ( struct Node * ) malloc ( sizeof ( struct Node ) ) ; // allocating memory dynamically new_node -> data = new_data ; new_node -> next = head ; head = new_node ; } /* function to display data of the list */ void display ( ) { struct Node * ptr ; ptr = head ; while ( ptr != NULL ) { cout << ptr -> data << " " ; ptr = ptr -> next ; } } int main ( ) { insert ( 5 ) ; // inserting data in the list insert ( 1 ) ; insert ( 4 ) ; insert ( 6 ) ; insert ( 7 ) ; cout << "The linked list is: " ; display ( ) ; return 0 ; }

Output

The linked list is: 7 6 4 1 5

Video Tutorial

Comment below if you have queries related to difference between array and linked list.

platttherstorted.blogspot.com

Source: https://www.thecrazyprogrammer.com/2019/08/array-vs-linked.html

Share this post