Linked list in Data structures and algorithms

The linked list is a basic data structure. it's an abstract data type that stores data into a noncontinuous memory location. and made up of nodes.

After completing this tutorial you will be able to learn

1. What is a Linked list?
2. The node of the linked list
3. Example of a linked list
4. Advantages of linked list
5. Disadvantages of linked list

in the array, we have the data arranged in a sequential and continuous memory location. as you see in the image given below.

What is Linked List?

In linked list data is not arranged in sequential order. as you see in the image given below. but with each item a reference to the next item stored in a memory location. so all the data connected together with the help of links.

The node of the linked list

A node is a basic building block of the linked list. the list item together with the link called a node of the linked list.



so all the nodes are connected together in a form to represent the linear order of the list.

Info part of the linked list contains the actual value and link part store the reference to the next value of the linked list.



Here is the example of a linked list that contains the six nodes. and all the values of the linked list connected using the link of every node.

Note: the first node contains the value of the first node and reference to the second node. as well the second node contains the value of the second node and reference of the third value and soon.

we only need to remember and store the reference of the first node. using the reference of the first node we can traverse the whole list and can access all the elements of the list.

Start variable

to implement a linked list we only store the reference to the first node using the start variable.

The advantage of the linked list

a linked list is a dynamic data structure.

it means we don't need to give the size of the linked list at the compile time of the program. we can give the size at the running time of the program. and also we can increase and decrease the size at the run time.

Data in a linked list is not stored in a contiguous memory location.

we don't need a contiguous memory to store the data of the linked list. it chooses randomly from the blank memory space to store the data.

Insertion and deletion of elements are easier and it can be used to implement the abstract data types like list, stack, queues.

The disadvantage of the linked list

we cannot access the data of the linked list in a random manner. like we need to traverse the whole list if we need to access the last element of the linked list.

to implementation of the linked list, we need extra memory. and this extra memory is used to store the links of every node.

Types of linked list

1. single linked list
2. double linked list
3. circular linked list
4. linked lists with header node
5. sorted linked list