Linked list

Types of Linked list

PrepBytes

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

A Linked List is a linear data structure. In linked list elements are not stored at contiguous locations. Linked list contain nodes and these nodes are linked using pointers. The various types of linked lists are explained below:

Singly Linked List

In Singly Linked list:

  • Each node contains data and has a pointer that will point to the next node of the same datatype.
  • We can traverse the list in one way only in forward direction.

Structure of Singly Linked List Node

class Node {
public:
int data;
// Pointer to next node in LL
Node* next;
};

Creation and Traversal of list

#include 
using namespace std;
 
// Structure of Node
class Node {
public:
    int data;
    Node* next;
    Node(int x){
    data = x;
    next = NULL;
}
};
 
// This function will print data present in the linked list from 
// start to end
void printList(Node* n)
{
 
    // move till n is NULL
    while (n != NULL) {
 
        // Print the data
        cout << n->data << " ";
        n = n->next;
    }
}
 
// Driver Code
int main()
{
    Node* head = NULL;
    Node* second = NULL;
    Node* third = NULL;
 
    // create 3 nodes with data 
    head = new Node(10);
    second = new Node(12);
    third = new Node(37);
 
    // create a linke from first node to second node
    head->next = second;
 
    // create a linke from second node to third node
    second->next = third;
 
    // make last node’s next as NULL
    third->next = NULL;
 
    printList(head);
 
    return 0;
}

Output

10 12 37

Time complexity: O(n) for printList function where ‘n’ is the number of nodes present in the list
Space complexity: O(n), where ‘n’ is the number of nodes present in the list

Doubly Linked List

In Doubly Linked list:

  • Each node contains data and has two pointers named next and previous. The next pointer points to the next node and the previous one will point to the previous node.
  • We can traverse in both directions in this list.

Structure of Doubly Linked List Node

class Node {
public:
int data;
// Pointer to next node in LL
Node* next,*prev;
Node(int x){
    data = x;
    next = NULL;
    prev = NULL;
    }
};

Creation and Traversal of list

#include 
using namespace std;
 
// Doubly linked list node
class Node {
public:
    int data;
    Node* next;
    Node* prev;
    Node(int x){
        data = x;
        prev = NULL;
        next = NULL;
    }
};
 
// This function will add a new node in front of the list
void push(Node** head_ref, int new_data)
{
    // create a new node with given data 
    Node* new_node = new Node(new_data);
 
    
 
    // assign head node’s address to next of new node
    new_node->next = (*head_ref);
 
    // assign NULL to prev of new node
    new_node->prev = NULL;
 
    // update the previous of old node as new node
    if ((*head_ref) != NULL)
        (*head_ref)->prev = new_node;
 
    // update the head node of list as new node 
    (*head_ref) = new_node;
}
 
// This function will print data present in the linked list from 
// start to end and also in reverse order
void printList(Node* node)
{
    Node* last;
 
    cout << "\nTraversal in forward"
        << " direction \n";
    while (node != NULL) {
 
        // Print the data
        cout << " " << node->data << " ";
        last = node;
        node = node->next;
    }
 
    cout << "\nTraversal in reverse"
        << " direction \n";
    while (last != NULL) {
 
        // Print the data
        cout << " " << last->data << " ";
        last = last->prev;
    }
}
 
// Driver Code
int main()
{
    // Start with the empty list
    Node* head = NULL;
 
    // Insert 10.
    // So linked list becomes 10->NULL
    push(&head, 10);
 
    // Insert 44 at the beginning. So
    // linked list becomes 44->10->NULL
    push(&head, 44);
 
    // Insert 11 at the beginning. So
    // linked list becomes 11->44->10->NULL
    push(&head, 11);
 
    cout << "Created DLL is: ";
    printList(head);
 
    return 0;
}

Output

Created DLL is:
Traversal in forward direction
11 44 10
Traversal in reverse direction
10 44 11

Time Complexity:

  • Push function: O(1)
  • printList function: O(n), where ‘n’ is the number of nodes present in the list

Space Complexity: O(n), where ‘n’ is the number of nodes present in the list

Circular Linked List

In Circular Linked list:

  • Each node contains data and a pointer that points to the next node.
  • A special property of this list is that the last node will point to the first node which makes it look circular and we can traverse the full linked list starting from any node.

Structure of Circular Linked List Node

class Node {
public:
int data;
// Pointer to next node in LL
Node* next;
};

Creation and Traversal of list

#include 
using namespace std;
 
// Structure for a node
class Node {
public:
    int data;
    Node* next;
    Node(int x){
    data = x;
    next = NULL;
}
};
 
// This function will insert a node at the beginning of the
// list
void push(Node** head_ref, int data)
{
    Node* ptr1 = new Node(data);
    Node* temp = *head_ref;
    ptr1->next = *head_ref;
 
    if (*head_ref != NULL) {
        while (temp->next != *head_ref) {
            temp = temp->next;
        }
        temp->next = ptr1;
    }
 
    else
        ptr1->next = ptr1;
 
    *head_ref = ptr1;
}
 
// This function will print data of all nodes in the list
void printList(Node* head)
{
    Node* temp = head;
    if (head != NULL) {
        do {
 
            // Print the data
            cout << temp->data << " ";
            temp = temp->next;
        } while (temp != head);
    }
}
 
// Main function
int main()
{
    Node* head = NULL;
    push(&head, 14);
    push(&head, 35);
    push(&head, 5);
    push(&head, 9);
    //created list will be 9->5->35->14
    cout << "Contents of Circular"
        << " Linked List\n ";
    printList(head);
 
    return 0;
}

Output

Contents of Circular Linked List
9 5 35 14

Time complexity

  • Push function: O(n), where ‘n’ is the number of nodes present in the list.
  • printList function: O(n), where ‘n’ is the number of nodes present in the list.

Space Complexity: O(n), where ‘n’ is the number of nodes present in the list

Doubly Circular Linked List

In Doubly Circular Linked list:

  • Each node contains data and has two pointers named next and previous.
  • The next pointer points to the next node and the previous one will point to the previous node.
  • Apart from this, the last node’s next pointer will point to the first node and the first node’s previous pointer will point to the last node.

Structure of Doubly Circular Linked List Node

class Node {
public:
int data;
// Pointer to next node in LL
Node* next,*prev;
Node(int x){
    data = x;
    next = NULL;
    prev = NULL;
    }
};

Creation and Traversal of list

#include 
using namespace std;
 
// Structure of a Node
class Node {
public:
int data;
// Pointer to next node in LL
Node* next,*prev;
Node(int x){
    data = x;
    next = NULL;
    prev = NULL;
}
 
};
 
// This function will insert a node at the beginning of the
// list
void insertBegin(Node** start,
                int value)
{
    // when list is empty
    if (*start == NULL) {
        Node* new_node = new Node(value);
        new_node->next
            = new_node->prev = new_node;
        *start = new_node;
        return;
    }
 
    // last node
    Node* last = (*start)->prev;
 
    Node* new_node = new Node(value);
 
    // update the prev and next pointers
    new_node->next = *start;
    new_node->prev = last;
 
    // Update next and previous
    // pointers of start & last
    last->next = (*start)->prev
        = new_node;
 
    // Update start pointer
    *start = new_node;
}
 
// This function will print the data in nodes of our list
void display(Node* start)
{
    Node* temp = start;
 
    printf("\nTraversal in"
        " forward direction \n");
    while (temp->next != start) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("%d ", temp->data);
 
    printf("\nTraversal in "
        "reverse direction \n");
    Node* last = start->prev;
    temp = last;
 
    while (temp->prev != last) {
 
        // Print the data
        printf("%d ", temp->data);
        temp = temp->prev;
    }
    printf("%d ", temp->data);
}
 
// Driver Code
int main()
{
    // Start with the empty list
     Node* start = NULL;
 
    // Insert 7
    // So linked list becomes 7->NULL
    insertBegin(&start, 7);
 
    // Insert 5 at the beginning
    // So linked list becomes 5->7
    insertBegin(&start, 5);
 
    // Insert 10 at the end
    // So linked list becomes 10->5->7
    insertBegin(&start, 10);
 
    printf("Created circular doubly"
        " linked list is: ");
    display(start);
 
    return 0;
}

Output

Created circular doubly linked list is:
Traversal in forward direction
10 5 7
Traversal in reverse direction
7 5 10

Time Complexity

  • insertBegin function: O(1)
  • Display function: O(n), where ‘n’ is the number of nodes present in the list

Space Complexity: O(n), where ‘n’ is the number of nodes present in the list

So, in this blog, we have tried to explain different types of Linked lists. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Previous post Insert a node at a specific position in a linked list
Next post Point arbit pointer to greatest value right-side node in a linked list

Leave a Reply

Your email address will not be published. Required fields are marked *

Close

Related Post