A Linked List is a data structure which can change during the execution it consists of a set of nodes linked together each node is divided into two parts one part consists of the data to be stored and the other part stores the address of the next node.

Some key points for a linked list -

• Successive elements are connected by pointers.

• last elements point to NULL in case of singly linked list and doubly linked list

• It can grow or shrink in size during the execution of the program.

• It does not waste memory space.

Types of Linked Lists -

• Singly Linked List -

  

• Doubly Linked List -

  

  pointers exist between adjacent nodes in both directions, the list can be traversed either forward or backward, and two pointers are maintained to track known as head and tail.

• Circular Linked List -

  

  the pointer of the last element in the list points back to the first element.

Basic operations of Linked Lists -

• Insert a node in Linked List.

• Delete a node in Linked List.

• Traverse a Linked List.

Implementation of a Linked List -

Singly Linked List

// node structure
class Node {
public:
  int data; // data element
  Node *next;//stores address of next element in a list

  Node()
  {
    data = 0;
    next = NULL;
  }
  Node(int x)
  {
    this->data = x;
    this->next = NULL;
  }
}

class ll {
Node *head;
public:
  ll(){head = NULL}

  Node *insert(int pos, int x) {
    Node *temp = new node(x);
    Node *curr;
    curr = head;
    if (pos == 1) // insert at first position
    {
      temp->next = head;
      head = temp;
      return head;
    }
    for (int i = 1; i <= pos - 2 && curr != NULL; i++) 
    // insert anywhere
    {
      curr = curr->next;
    }
    temp->next = curr->next;
    curr->next = temp;
    return head;
  }

  Node *del(int pos) {
    Node *curr;
    curr = head;
    if (pos == 1) // delete first node
    {
      head = head->next;
      return head;
    }
    for (int i = 1; i <= pos - 2 && curr != NULL; i++)
    // delete any node
    {
      curr = curr->next;
    }
    curr->next = curr->next->next;
    return head;
  }

  void display() { // traversing the list
    Node *curr = head;
    while (curr != NULL){
      cout << curr->data << " ";
      curr = curr->next;
    }
  }
}

Doubly Linked List -

class Node{
public:
    int data;
    Node *prev;
    Node *next;

    Node()
    {
        prev = NULL;
        next = NULL;
        data = 0;
    }
    Node(int x)
    {
        data = x;
        prev = NULL;
        next = NULL;
    }
}

class dll{
    Node *head;
public:
    dll() { head = NULL }

    void insertFront(int x)
    {
        Node *newNode = new Node(x);
        NewNode->next = head;
        newNode->prev = NULL;
        if (head != NULL){
            head->prev = newNode;
        }
        head = newNode;
    }

    void insertAfter(Node *prevNode, int x){
        if (prevNode == NULL){
            cout << "previous cant be null";
            return;
        }
        Node *newNode = new Node(x);
        newNode->prev = prevNode;
        newNode->next = prevNode->next;
        prevNode->next = newNode;
        if (newNode->next != NULL){
            newNode->next->prev = newNode;
        }
    }
    void insertEnd(int x){
        Node *newNode = new Node(x);
        newNode->next = NULL;
        Node *last = head;
        if (head == NULL){
            newNode->prev = NULL;
            head = newNode;
            return;
        }
        while (last->next != NULL){
            last = last->next;
        }
        last->next = newNode;
        newNode->prev = last;
    }
    void deleteNode(Node *delNode){
        if(head == NULL || delNode == NULL){
            return;
        }
        if(head == delNode){ // del first node;
            head = delNode->next;
        }
        if(delNode->next!=NULL){ 
            delNode->next->prev = delNode->prev;
        }
        if(delNode->prev!=NULL){
            delNode->prev->next = delNode->next;
        }
        delete delNode;
    }

    void display(Node *node) { // displays a list after a given node
        Node *last;

        // forward direction
        while (node != NULL){
            cout << node->data << "<==>";
            last = node;
            node = node->next;
        }
        // backward direction
        while (last != NULL){
            cout << last->data << "<==>";
            last = last->prev;
        }
    }
}

Circular Linked List -

class Node{
public:
    int data;
    Node *next;
    Node(){
        this->data = 0;
        this->next = NULL;
    }
    Node(int x){
        this->data = x;
        this->next = NULL;
    }
}

class cll{
    Node *head;
    Node *tail;

public:
    cll(){
        this->head = NULL;
        this->tail = NULL;
    }
    void insert(int x)
    {
        Node *newNode = newNode(x);
        if (head == NULL){
            head = newNode;
            tail = newNode;
            return;
        }
        tail->next = newNode;
        newNode->next = head;
        tail = newNode;
    }

    void delNode(int x)
    {
        Node *temp = head;
        if (head == tail){
            head = NULL;
            tail = NULL;
            return;
        }
        if (temp->data == x){
            head = head->next;
            tail->next = head;
            return;
        }
        do{
            Node *n = temp->next;
            if (n->data == x){
                temp->next = n->next;
                break;
            }
            temp = temp->next;
        } while (temp != head);
    }

    void display(){
        Node *temp = head;
        if (head != NULL){
            do{
                cout << temp->data << "-->";
                if (temp->next != NULL){
                    temp = temp->next;
                }
            } while (temp != head);
        }
    }
}

Interview Questions on Linked Lists -

Check out all the questions about linked lists that have been asked in the FAANG interviews frequently in this GitHub repository also make sure to follow me on GitHub to stay updated on such content, also you can too contribute to this repo.

Other related blogs -

Congrats! you have learned the fundamentals of Linked List Data-Structure, make sure to subscribe to my blog to follow this series and follow me on Hashnode, where I'll be uploading content on Data Structures and Algorithms every weekend.