A linked list is a set of data structures that are interconnected by links.
A linked list is a set of links that contains items. Linked lists are the second most widely used data structure after arrays. A linked list is a very commonly used linear data structure that consists of a group of nodes in a sequence.
Each node contains own data and address of next node, forming a chain-like structure. Linked lists are used to create trees and charts.
The following are important terms for understanding the concept of linked lists.
- Links: Each link in a linked list can store data called items.
- Next: Each link in the link list contains a link to the next link, called Next.
- LinkedList: The linked list contains a connection link to the first link called First.
Types of Linked Lists:
There are three different types of linked lists. It is as follows.
- Singly Linked List
- Doubly Linked List
- Circular Linked List
Learn more about them and how they differ from each other.
1) Singly Linked Lists:
- The first node is the main node, which points to the next node in the sequence.
- The last node reference is null, marking the end of the list.
2) Doubly Linked Lists:
- Each node has two pointers, one to point to the next node and one to point to the previous node.
- The pointer next to the last node and the pointer before the first node (head) are null.
3) Circular Linked Lists:
- A circular linked list is very similar to a single linked list, except that the last node points to the first node and becomes a circular list, as shown below.
Basic Operations of the Linked List:
- Traversal: Traverse all nodes one after another.
- Insert: Adds a node at the specified location.
- Delete: Deletes the node.
- Search: Search for an item by value.
- Update: Updates the node.
- Sort: Sort the nodes in the linked list in a specific order.
- Merge: Merges two linked lists into one.
Advantages of the Linked List:
- Dynamic data structure: Because linked lists are dynamically placed, they can be scaled up and down at run time using memory allocation and deallocation. Therefore, you do not need to specify the initial size of the linked list.
- No memory waste: Linked lists increase or decrease the size of the linked list at run time, resulting in no memory waste and no need to preallocate memory for efficient memory usage.
- Implementation: Linear data structures, such as stacks and queues, are often easy to implement using linked lists.
- Insert and Delete Operations: Linked lists make insert and delete operations easy. There is no need to change the item after inserting or removing it, just update the address at the next pointer.
Disadvantages of the Linked List:
- Memory usage: Linked lists require more memory compared to arrays. This is because the linked list also needs a pointer to store the address of the next item, which in turn requires additional memory.
- Traversal: In a linked list, the traversal takes longer than a matrix. Linked lists do not allow direct access to elements, such as indexed arrays. For example, to access the mode at position n, you must traverse all the nodes above.
- Reverse Traversing: A simple linked list does not allow reverse traverse, but a double linked list does because each node contains a pointer to a previously connected node. This is a memory leak because the backspace pointer requires additional memory.
- Random Access: Due to dynamic memory allocation, linked lists cannot be randomly accessed as much as possible.
Applications of Linked Lists:
- Linked lists are used to implement stacks, queues, charts, and more.
- Linked lists allow you to insert items at the beginning and end of a list.
- Linked lists do not require you to know the size in advance.
Conclusion:
A linked list is a data structure that is used to store data items in a linear fashion, but in non-contiguous locations. A linked list is a collection of nodes that contains parts of the data and the next pointer that contains the memory addresses of the next item in the list.
The pointer to the next item in the last item in the list is set to NULL, which marks the end of the list. The first item in the list is called the head. Linked lists support various operations, such as insert, delete, and loop. For dynamic memory allocation, linked lists take precedence over arrays.
This article describes the concept of linked lists. You can also see the pros and cons of using LinkedList on arrays. These include nodes that cannot be easily accessed and must be accessed from the beginning of the LinkedList.
References:
- https://www.tutorialspoint.com/data_structures_algorithms/linked_list_algorithms.htm
- https://www.studytonight.com/data-structures/introduction-to-linked-list#:~:text=Introduction%20to%20Linked%20Lists,to%20create%20trees%20and%20graphs.
- https://www.programiz.com/dsa/linked-list
