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
- What is a Linked list?
- The node of the linked list
- Example of a linked list
- Advantages of linked list
- 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 a Linked List?
In the 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 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 together 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 store 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 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 they can be used to implement abstract data types like lists, stacks, and 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 implement the linked list, we need extra memory. and this extra memory is used to store the links of every node.
Types of linked list
- single linked list
- double linked list
- circular linked list
- linked lists with header node
- sorted linked list
