A Linked List is a data structure in which the objects are arranged in a linear order. Unlike Arrays, you cannot access any element directly through its index. Time complexity of access operation in Linked lists is O(n) where n is the size of linked list.
Also unlike an array, Linked list’s elements are not stored in contiguous memory location. The individual elements of a linked list are stored at different places like a dispersed family but still bound together.
Searching in a Linked List
List-Search (L, k) 1. x = head[L] 2. while x != NULL && info[x] != k 3. do x = next[x] 4. return x List-Search has O(n) Time complexity and O(1) Space complexity
Inserting into a Linked List
List-Insert (L, x) 1. if head[L] != NULL 2. next[x] = head[L] 3. head[L] = x 4. return x List-Insert has O(1) Time complexity and O(1) Space complexity
Inserting into a Linked List after element k
List-Insert-Position (L, x, k) 1. node = head[L] 2. while node != NULL && info[node] != k 3. do node = next[node] 4. end 5. if node != NULL 6. next[x] = next[node] 7. next[node] = x 8. return head[L] List-Insert-Position has O(n) Time complexity and O(1) Space complexity
Deleting from a Linked List
List-Delete (L, k) 1. x = head[L] 2. if x != NULL && info[x] == k 3. head[L] = x->next 4. return head[L] 2. while x != NULL && info[x] != k 3. do prev = x 4. x = next[x] 5. end 6. if x != NULL 7. next[prev] = next[x] 8. Delete(x) (to prevent memory leak) 9. return head[L] List-Delete has O(n) Time complexity and O(1) Space complexity
Code Implementation
//
// main.cpp
// Linked List
//
// Created by Himanshu on 12/09/21.
//
#include <iostream>
using namespace std;
struct node {
int info = 0;
struct node *next;
};
typedef struct node Node;
node* newNode(int data) {
node* Node = new node();
Node->info = data;
Node->next = NULL;
return(Node);
}
void printLinkedList (Node* head) {
Node *x = head;
while (x != NULL) {
cout<<(x->info)<<" ";
x = x->next;
}
cout<<endl;
}
Node* insertNode (Node *head, Node* x) {
x->next = head;
head = x;
return head;
}
Node* searchNode (Node *head, int k) {
Node* x = head;
while (x != NULL && x->info != k) {
x = x->next;
}
if (x != NULL && x->info == k) {
return x;
} else {
return NULL;
}
}
Node* insertAtPosition (Node *head, Node* x, int k) {
Node* node = head;
while (node != NULL && node->info != k) {
node = node->next;
}
if (node != NULL) {
x->next = node->next;
node->next = x;
}
return head;
}
Node* deleteNode (Node *head, int k) {
Node* x = head, *prev = NULL;
if (x != NULL && x->info == k) {
head = x->next;
//To prevent Memory Leak
delete (x);
return head;
}
while (x != NULL && x->info != k) {
prev = x;
x = x->next;
}
// Deleting a node, requires the node
// previous to the node to be deleted.
if (x != NULL) {
prev->next = x->next;
//To prevent Memory Leak
delete (x);
}
return head;
}
int main() {
Node *head = newNode(5);
head = insertNode (head, newNode(4));
head = insertNode (head, newNode(3));
head = insertNode (head, newNode(2));
head = insertNode (head, newNode(1));
cout<<"Linked List:"<<endl;
printLinkedList(head);
cout<<"Searching Node 3"<<endl;
if (searchNode(head, 3)) {
cout<<"Node 3 is present"<<endl;
}
cout<<"Searching Node 6 "<<endl;
if (!searchNode(head, 6)) {
cout<<"Node 6 is not present"<<endl;
}
cout<<"Inserting Node 6 after 5 "<<endl;
head = insertAtPosition(head, newNode(6), 5);
cout<<"Linked List:"<<endl;
printLinkedList(head);
cout<<"Deleting Node 1"<<endl;
head = deleteNode(head, 1);
cout<<"Linked List:"<<endl;
printLinkedList(head);
cout<<"Deleting Node 6"<<endl;
head = deleteNode(head, 6);
cout<<"Linked List:"<<endl;
printLinkedList(head);
return 0;
}
Output
Linked List: 1 2 3 4 5 Searching Node 3 Node 3 is present Searching Node 6 Node 6 is not present Inserting Node 6 after 5 Linked List: 1 2 3 4 5 6 Deleting Node 1 Linked List: 2 3 4 5 6 Deleting Node 6 Linked List: 2 3 4 5
Here’s a working example: Linked List