Linked List

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.

Linked List
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;
}


Here’s a working example:

https://ideone.com/mgiD2n

Leave a Reply