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)
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)
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)
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

List-Insert-Position has O(n) Time complexity and O(1) Space complexity
###### Deleting from a Linked List
List-Delete (L, k)
2. if x != NULL && info[x] == k
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)

List-Delete has O(n) Time complexity and O(1) Space complexity

Code Implementation

//
//  main.cpp
//
//  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);
}

while (x != NULL) {
cout<<(x->info)<<" ";
x = x->next;
}

cout<<endl;
}

Node* insertNode (Node *head, Node* x) {
}

Node* searchNode (Node *head, int k) {

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) {

while (node != NULL && node->info != k) {
node = node->next;
}

if (node != NULL) {
x->next = node->next;
node->next = x;
}

}

Node* deleteNode (Node *head, int k) {
Node* x = head, *prev = NULL;

if (x != NULL && x->info == k) {

//To prevent Memory Leak
delete (x);

}

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);
}

}

int main() {

cout<<"Searching Node 3"<<endl;
cout<<"Node 3 is present"<<endl;
}

cout<<"Searching Node 6 "<<endl;
cout<<"Node 6 is not present"<<endl;
}

cout<<"Inserting Node 6 after 5 "<<endl;

cout<<"Deleting Node 1"<<endl;

cout<<"Deleting Node 6"<<endl;

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
2 3 4 5