Linked List
A linked list is a type of linear data structure that include a series of inter connected nodes. The elements in Linked list are not stored at an adjacent location and they linked using pointers.
Basically, a linked list is a sequence of data structures, that are connected with one another via links.
A linked list is a sequence of links that contain items. Each link includes a connection to another link. The Linked list is the next most-used data structure following the array.
Why Linked List?
Arrays can be used to store linear data of similar types, but arrays have the following limitations.
1) The array size is fixed: We must know in advance the upper limit on the number of elements.
2) Inserting a new element in an array of elements is expensive in terms of time consumption. This is because the room has to be built for the new elements and all the following elements have to be shifted.
A linked list is a random sequence of data structures, which are connected together via links and contain items. Each link of the element contains a connection to another link.
Following are the important terms in Linked List Data Structures:
- Link − Every link of a linked list can hold data called an element.
- Next − All the link of a linked list contains a link to the next link called Next.
- LinkedList − A Linked List holds the connection link to the first link called First.
Representation:
A linked list is represented by a pointer to the first node of the linked list. The first node is called the head. If the linked list is empty, then the value of the head is NULL.
Each node in a list consists of at least two parts:
1) data
2) Pointer (Or Reference) to the next node
Types of Linked List
Following are the various types of linked list.
- Simple Linked List − Item navigation is forward only.
- Doubly Linked List − Items can be navigated forward and backward.
- Circular Linked List − Last item contains link of the first element as next and the first element has a link to the last element as previous.
Linked List Complexity
Time Complexity
| Worst case | Average Case | |
|---|---|---|
| Search | O(n) | O(n) |
| Insert | O(1) | O(1) |
| Deletion | O(1) | O(1) |
Linked List Applications
- Dynamic memory allocation
- Hash tables, Graphs
- Implemented in stack and queue
- In undoing functionality of the software
Basic Operations
Following are the basic operations supported by a list.
- Insertion − Appends an element at the beginning of the list.
- Deletion − Removes an element at the beginning of the list.
- Display − Presents the complete list.
- Search − Examines an element using the given key.
- Delete − Destroys an element using the given key.
Advantages over arrays
1) Dynamic size
2) Ease of insertion/deletion
Drawbacks:
1) Random access is not possible: We have to access elements starting from the first node of the list. So we cannot do a binary search with linked lists efficiently with its default implementation.
2) Additional memory space to hold a pointer is needed with each element of the list.
3) Not cache-friendly. Since array components are contiguous locations, there is the locality of reference which is not present in the case of linked lists.
SYNTAX:
#include <bits/stdc++.h>
using namespace std;
int main()
{
class Node
{
public:
int data;
Node * next;
};
}
