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
struct Node { int data; struct Node* next; };
class Node { public: int data; // Pointer to next node in LL Node* next; };
class Node { public int data; Node next; }
class Node: def __init__(self, data=None, next=None): self.data = data self.next = next
Creation and Traversal of list
#include<stdio.h> #include<stdlib.h> // Structure of Node struct Node { int data; struct Node* next; }; // This function will print data present in the linked list from // start to end void printList(struct Node* n) { // move till n is NULL while (n != NULL) { // Print the data printf("%d ",n->data); n = n->next; } } // Driver Code int main() { struct Node* head = NULL; struct Node* second = NULL; struct 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; }
#include <bits stdc++.h=""> 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; }
class SinglyLinkedList { public int data; SinglyLinkedList next; SinglyLinkedList(int data) { this.data=data; } static void printList(SinglyLinkedList n) { while(n!=null) { System.out.print(n.data+" "); n=n.next; } } public static void main(String[] args) { SinglyLinkedList head=null; SinglyLinkedList second=null; SinglyLinkedList third=null; head =new SinglyLinkedList(10); second=new SinglyLinkedList(12); third=new SinglyLinkedList(37); head.next=second; second.next=third; third.next=null; printList(head); } }
class Node: def __init__(self, data=None, next=None): self.data = data self.next = next # This function will print data present in the linked list from start to end def printList(head): while (head != None): print( head.data , end=" ") head = head.next head = None second = None third = None # create 3 nodes with data head = Node(10) second = Node(12) third = Node(37) # create a link from first node to second node head.next = second # create a link from second node to third node second.next = third printList(head)
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
struct node { struct node *prev; int data; struct node *next; }
class Node { public: int data; // Pointer to next node in LL Node* next,*prev; Node(int x){ data = x; next = NULL; prev = NULL; } };
class Node { public: int data; // Pointer to next node in LL Node* next,*prev; Node(int x){ data = x; next = NULL; prev = NULL; } };
class Node: def __init__(self, data=None, next=None, prev=None): self.data = data self.next = next self.prev = prev
Creation and Traversal of list
#include <stdio.h> #include<stdlib.h> struct node { struct node *prev; int data; struct node *next; } void push(Node** head_ref, int new_data) { // create a new node with given data struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); // 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(struct Node* node) { struct Node* last; printf("\nTraversal in forward direction \n"; while (node != NULL) { // Print the data pritnf("%d ,node->data);; last = node; node = node->next; } printf("\nTraversal in reverse direction \n"; while (last != NULL) { // Print the data printf("%d ,last->data); last = last->prev; } } // Driver Code int main() { // Start with the empty list struct 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); printf("Created DLL is: "); printList(head); return 0; }
#include <bits stdc++.h=""> 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; }
class Node: def __init__(self, data=None, next=None, prev=None): self.data = data self.next = next self.prev = prev # This function will add a new node in front of the list def push(head, new_data): # create a new node with given data new_node = Node(new_data) # assign head node’s address to next of new node new_node.next = head # update the previous of old node as new node if head is not None: head.prev = new_node # update the head node of list as new node head = new_node return new_node # This function will print data present in the linked list from start to end def printList(node): print("Traversal in forward direction") while node: print(node.data,end=" ") last = node node = node.next print("\nTraversal in reverse direction",) while last: print(last.data,end=" ") last = last.prev # Start with the empty list head = None # Insert 10. # So linked list becomes 10->NULL head = push(head,10) # Insert 44 at the beginning. So # linked list becomes 44->10->NULL head = push(head,44) # Insert 11 at the beginning. So # linked list becomes 11->44->10->NULL head = push(head,11) print("Created DLL is:") printList(head)
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
#includeusing 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; } };
class Node: def __init__(self, data=None, next=None, prev=None): self.data = data self.next = next self.prev = prev
Creation and Traversal of list
#includeusing 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.