Linked List in Data Structure | DSA Tutorials

Linked List in Data Structure – The linked list is a basic data structure. It’s an abstract data type that stores data in a noncontinuous memory location and is 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 a linked list
5. Disadvantages of a linked list

In the array, we have the data arranged in a sequential and continuous memory location, as you see in Figure 1.

What is a Linked List?

In the linked list, the data is not arranged in sequential order, as you see in Figure 2, but with each item, a reference to the next item is stored in a memory location. So all the data is 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, is called a node of the linked list.

So all the nodes are connected in a form to represent the linear order of the list. The info part of the linked list contains the actual value, and the link part stores the reference to the next value of the linked list.

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

Note: the first node contains the value of the first node and a reference to the second node, as well as the second node containing the value of the second node and a reference to the third node, and so on. 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 in linked list – To implement a linked list, we only store the reference to the first node using the start variable.

Advantages 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 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 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 they can be used to implement abstract data types like lists, stacks, and queues.

Disadvantages of the linked list

We cannot access the data of the linked list in a random manner. We need to traverse the whole list if we need to access the last element of the linked list. To implement the linked list, we need extra memory, and this extra memory is used to store the links of every node.