A linked list is a linear data structure. In the Linked list, we connect some nodes one after another. Every node consists of the value and address of other nodes.
A linked list can be of multiple types: Singly linked list, Doubly linked list, Circular linked list, and circular doubly linked list.
We will learn Linked list with a Singly linked list, then we will learn about other types of linked lists in next tutorial.
Represent of Singly Linked List
Linked List is represented with custom data types we will say nodes.
Every node consists
- Data
- Address of next node.
Singly Linked List representation with C++
// Creating a node
class Node {
public:
int value;
Node* next;
};
Let’s create three node and set value 1, 2 and 3 respectively.
Node* head;
Node* one = NULL;
Node* two = NULL;
Node* three = NULL;
// allocate 3 nodes in the heap
one = new Node();
two = new Node();
three = new Node();
// Assign value values
one->value = 1;
two->value = 2;
three->value = 3;
Now we have to link those one after another.
// Connect nodes
one->next = two;
two->next = three;
three->next = NULL;
Now this linked list look likes
If we merge this together.
// Linked list implementation in C++
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
// Creating a node
class Node {
public:
int value;
Node* next;
};
int main() {
Node* head;
Node* one = NULL;
Node* two = NULL;
Node* three = NULL;
// allocate 3 nodes in the heap
one = new Node();
two = new Node();
three = new Node();
// Assign value values
one->value = 1;
two->value = 2;
three->value = 3;
// Connect nodes
one->next = two;
two->next = three;
three->next = NULL;
// print the linked list value
head = one;
while (head != NULL) {
cout << head->value;
head = head->next;
}
}
Linked List in Python
# Linked list implementation in Python
class Node:
# Creating a node
def __init__(self, item):
self.item = item
self.next = None
class LinkedList:
def __init__(self):
self.head = None
if __name__ == '__main__':
linked_list = LinkedList()
# Assign item values
linked_list.head = Node(1)
second = Node(2)
third = Node(3)
# Connect nodes
linked_list.head.next = second
second.next = third
# Print the linked list item
while linked_list.head != None:
print(linked_list.head.item, end=" ")
linked_list.head = linked_list.head.next
Insertion in Singly Linked List
Time complexity of inserting new node in singly linked list is O(1).
Suppose we have a new node “a” , we want to insert it after the node “b”. To insert this, assign node b’s next node to a’s next node. Then assign a to b node’s next node.
a->next = b->next
b->next=a
Deletion in Singly Linked List
Time complexity of deletion is also O(1) if we know the previous node. but if we don’t know the previous node, then first we have to search for previous which is in worst case O(n) complexity.
Suppose we have a node currentNode and previous node of this node is prevNode. Now we want to delete currentNode.
prevNode->next=currentNode->next
