Linked Lists and its types

Linked list is a linear data structure that consists of a sequence of nodes, where each node contains a value and a reference (or pointer) to the next node in the sequence. The last node in the sequence has a reference to null, indicating the end of the list.

The main advantage of a linked list over an array is that it allows for efficient insertion and deletion of elements, as these operations do not require shifting of elements like in an array. However, accessing an element at a particular index in a linked list takes O(n) time, while in an array it takes O(1) time.

There are two major types of linked lists:

Singly Linked List: In a singly linked list, each node has only one reference to the next node in the sequence.

Doubly Linked List: In a doubly linked list, each node has two references, one to the next node and one to the previous node in the sequence.

Real-time examples of a linked list include:

A playlist of songs in a music streaming app.

A list of messages in a chat app.

A list of webpages in a browser's history.


// Singly Linked List
 
#include <iostream>
using namespace std;
 
class Node {
public:
	int data;
	Node* next;
	Node(int d) {
    	data = d;
    	next = NULL;
	}
};
 
class LinkedList {
public:
	Node* head;
	LinkedList() {
    	head = NULL;
	}
 
	// Insert a node at the beginning of the list
	void insertAtBeginning(int d) {
    	Node* new_node = new Node(d);
    	new_node->next = head;
    	head = new_node;
	}
 
	// Insert a node at the end of the list
	void insertAtEnd(int d) {
    	Node* new_node = new Node(d);
    	if (head == NULL) {
        	head = new_node;
        	return;
    	}
    	Node* last = head;
    	while (last->next != NULL) {
        	last = last->next;
    	}
    	last->next = new_node;
	}
 
	// Delete a node with given key
	void deleteNode(int key) {
    	Node* temp = head, *prev = NULL;
 	   if (temp != NULL && temp->data == key) {
        	head = temp->next;
        	delete temp;
        	return;
    	}
    	while (temp != NULL && temp->data != key) {
        	prev = temp;
        	temp = temp->next;
    	}
    	if (temp == NULL) {
        	return;
    	}
    	prev->next = temp->next;
    	delete temp;
	}
 
	// Print the list
	void printList() {
    	Node* current_node = head;
    	while (current_node != NULL) {
        	cout << current_node->data << " ";
        	current_node = current_node->next;
    	}
    	cout << endl;
	}
};
 
int main() {
	LinkedList l;
	l.insertAtEnd(1);
	l.insertAtEnd(2);
	l.insertAtEnd(3);
	l.insertAtBeginning(0);
	l.printList();
	l.deleteNode(2);
	l.printList();
	return 0;
}


// Doubly Linked List

#include <iostream>

using namespace std;

// Define a node of the doubly linked list
class Node {
public:
    int data;
    Node* prev;
    Node* next;
};

// Define the doubly linked list
class DoublyLinkedList {
private:
    Node* head;
public:
    DoublyLinkedList() {
        head = NULL;
    }
    
    // Add a node at the beginning of the list
    void insertAtBeginning(int data) {
        Node* new_node = new Node;
        new_node->data = data;
        new_node->prev = NULL;
        new_node->next = head;
        if (head != NULL) {
            head->prev = new_node;
        }
        head = new_node;
    }
    
    // Add a node at the end of the list
    void insertAtEnd(int data) {
        Node* new_node = new Node;
        new_node->data = data;
        new_node->next = NULL;
        if (head == NULL) {
            new_node->prev = NULL;
            head = new_node;
            return;
        }
        Node* temp = head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = new_node;
        new_node->prev = temp;
    }
    
    // Remove a node from the list
    void remove(int data) {
        Node* temp = head;
        while (temp != NULL && temp->data != data) {
            temp = temp->next;
        }
        if (temp == NULL) {
            return;
        }
        if (temp->prev != NULL) {
            temp->prev->next = temp->next;
        } else {
            head = temp->next;
        }
        if (temp->next != NULL) {
            temp->next->prev = temp->prev;
        }
        delete temp;
    }
    
    // Print the list
    void printList() {
        Node* temp = head;
        while (temp != NULL) {
            cout << temp->data << " ";
            temp = temp->next;
        }
        cout << endl;
    }
};

int main() {
    DoublyLinkedList list;
    list.insertAtEnd(10);
    list.insertAtBeginning(20);
    list.insertAtEnd(30);
    list.insertAtEnd(40);
    list.printList();
    list.remove(30);
    list.printList();
    return 0;
}

PRACTICE PROBLEMS :

Reverse a LinkedList

Detect a cycle in Linked List