Introduction to Linked List in Data Structure:
A list is a way to keep data items next to each other. In memory, we can keep data in two ways, Sequential(contiguous) and random manner. We have already discussed the sequential data structure in the form of a Stack, where data items were stored in a contiguous manner and the address of that data was also continuous.
When we talk about a Random manner it means data did not arrange in a contiguous memory location, data were scattered across the memory called heap memory. In a heap, data is scattered but connected through links. When the list of data items were connected through a link there the concept of a link list arrives. The best thing about a linked list is that data can grow and shrink dynamically during the execution of the program as required. According to the linked list concept, data is stored in some block. Block stores two things’ data itself and the address of other data to which it needs to link.
A linked list is node based linear data structure where a list of items is stored in blocks which are called nodes. The concept of a linked list will be better understood through its properties.
Linked List Properties :
- The first node in a linked list is the head, and we can perform various operations on the linked list through the head. The reference to the linked list’s head node will be provided in each linked list question.
- The last node of the linked list implies NULL(None), indicating that it is the final node.
- Linked list elements, unlike arrays, are not stored in adjacent memory locations.
- Because Linked Lists are dynamic, they overcome some of the shortcomings of arrays, such as their fixed size.
Each block in the linked list contains two types of items first Data itself and second one is the address location of other data available in Heap.
To hold the address of another data, the concept of the pointer is applied.
Syntax of Linked List :
In C language, a linked list can be implemented using structure and pointers.
struct LinkedList {
int data ;
struct LinkedList *next ;
};
The above definition is used to create every node in the list. The data field stores the element and the next is a pointer to store the address of the next node.
In place of a data type, struct LinkedList is written before next. That’s because it’s a self-referencing pointer. It means the pointer holds the address of other data. Here next is a part of a node and it will point to the next node.
Advantages of a linked list :
- Linked lists are a dynamic data structure, which can grow and be pruned, allocating and deallocating memory while the program is running.
- Items can be added or removed from the middle of the list.
- There is no need to define the initial size of the Linked list.
- Insertion and deletion node operations are easily implemented in a linked list.
- Linear data structures such as stacks and queues can be implemented using a linked list.
Singly Linked List has the following applications:
- It is used to implement stacks and queues, which are basic needs in computer science.
- We use a singly linked list to prevent data in the hash map from colliding.
- If you’ve ever used a casual notepad, you’ll notice that it also uses a singly linked list to perform undo, redo, and delete functions.
- We can imagine it being used in a photo viewer to view photos continuously in a slide show.
- In the train system, the idea is similar to a singly linked list in that if you want to add a Boggie, you must either take a new boggie to add at the end or find a space between boggies and add it.
I hope a brief Idea about an Array is clear to you. Please do comment your valuable suggestions.
Also Understand the concept about :
