0

Linked List

Linked list is a data structure used to store data in linear order.

We know array , data structure which is used to store data in linear order, then why we need another data structure for same??

Answer to this question highlights main difference between array and linked list. For an array, data always stored in a continuous memory locations. so if I declare array of size 10, depending on size of data type * 10 memory block is reserved for array elements.

However for linked list, no continuous memory allocation is required. In linked list each element stores a data and pointer to (address of) the next element. So no continuous memory allocation require to store data. Each of this structure containing data and address is referred as ‘Node’.

The first element of linked list always referred as ‘Head’ and last node has address as ‘null’.

So what are the advantages and disadvantages of linked list compared to array?

Advantages:

1. Linked list is a dynamic data structure means the number of nodes in a list is not fixed and can grow and shrink on demand. Memory allocation is done when program is running.

2. Insertion and deletion operation is easy  to implement compared to array.

3. They can reduce access time and may expand in real time without memory overhead.

 

Disadvantages:

1. Linked list requires more memory space to store reference of next node.

2. Linked list provides sequential access which means linked list accessed from head. So it is not possible to get element at specific location directly.

3. Time require to access individual element is more.

4. It is difficult to reverse traverse linked list as compared to arrays.

 

There are three variations in linked list as follows:

1. Singly linked list:  This is a basic linked list which is described above. Each node contains pointer to the next element is list.

Singly linked list

2. Doubly Linked List: In this list each element store pointer to the next element and a previous element.  So for head node previous pointer value is Null and for last node pointer to next element is stored as Null.

Doubly linked list

3. Circular Linked List: This linked list is like a singly linked list only difference is last node of linked list store pointer of head.

Circular linked list

 

We will discuss basic operations like insert, delete, traverse on each type of  linked list in next session..


Warning: count(): Parameter must be an array or an object that implements Countable in /home/algotu5/public_html/wp-includes/class-wp-comment-query.php on line 405