Search for:

Have you ever wondered how data is stored in the computer’s memory?

It’s not very smart to just “throw” data into the memory without having a proper structure of data.

To provide a well-organized structure for the said data to get stored is something crucial when programming. This way, we can use and manage the stored data more efficiently. To provide this, we use Data Structures.

Every programming language provides fundamental data structures like:

  • Integer
  • Float
  • Char
  • Double

to store primitive type values.

But with the use of user-defined data types, we can now create data structure as required.

In this guide, you will see two of the most commonly used user define data types: Arrays and Linked List, the difference between them and their implementation.

Array

The most simple type of data structure is called an Array. 

An array is used to store a set of similar data in a contiguous block of memory under a heading or variable name. With its particular simplicity comes barriers like the need for a contiguous block of memory, or if free memory is available. If not, the block becomes inefficient to use arrays.

array representation
Array representation

Arrays indexing starts at 0, and every element can be accessed using its index. 

Operations on arrays are very fast, as any element can be accessed using array indexing. The name of the array is the base address and all its elements can be accessed using the base address. That’s because the memory allocated to array is consecutive.

Linked List

On the other hand, a very simple and yet useful data structure that doesn’t need a contiguous block is the Linked list.

The Linked lists are used in situations where there is no need to allocate memory dynamically during the runtime of a program.

It can be visualized like a train – the Engine (head) and all the carriages (nodes) are linked to the train engine either directly or indirectly.

linked list
Linked list representation

A linked list is a user-defined data type, and all the nodes of the list are linked using pointers. To access any node, you must traverse the list linearly – unline an array where you can have direct access to elements.

Difference between Arrays and Linked lists

Parameters Array Linked List
Definition It is a collection of elements having the same data type with a common name. It is an ordered collection of elements that 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 an 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 the node is required.
Searching Binary search and Linear search Linear search
Extra Space Extra space is not required. To link nodes of the 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.

Output

5 4 3 2 1

Linked List Implementation in C++

Output

The linked list is: 7 6 4 1 5

Write A Comment

Shares