A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers. In simple words, a linked list consists of nodes where each node contains a data field and a reference(link) to the next node in the list. Types Of Linked List - Singly Linked List: It is the simplest type of linked list in which every node contains some data and a pointer to the next node of the same data type. The node contains a pointer to the next node means that the node stores the address of the next node in the sequence. A single linked list allows traversal of data only in one way. Below is the image for the same:
- Structure of Singly Linked List:
class Node { public: int data; Node* next; }; |
static class Node { int data; Node next; }; |
class Node: def __init__(self, data): self.data = data self.next = None |
public class Node { public int data; public Node next; }; |
class Node { constructor() { this.data=0; this.next=null; } } |
- Creation and Traversal of Singly Linked List:
#include <bits/stdc++.h> using namespace std; class Node { public: int data; Node* next; }; void printList(Node* n) { while (n != NULL) { cout << n->data << " "; n = n->next; } } int main() { Node* head = NULL; Node* second = NULL; Node* third = NULL; head = new Node(); second = new Node(); third = new Node(); head->data = 1; head->next = second; second->data = 2; second->next = third; third->data = 3; third->next = NULL; printList(head); return 0; } |
class GFG{ static class Node { int data; Node next; }; static void printList(Node n) { while (n != null) { System.out.print(n.data + " "); n = n.next; } } public static void main(String[] args) { Node head = null; Node second = null; Node third = null; head = new Node(); second = new Node(); third = new Node(); head.data = 1; head.next = second; second.data = 2; second.next = third; third.data = 3; third.next = null; printList(head); } } |
using System; class GFG{ public class Node { public int data; public Node next; }; static void printList(Node n) { while (n != null) { Console.Write(n.data + " "); n = n.next; } } public static void Main(String[] args) { Node head = null; Node second = null; Node third = null; head = new Node(); second = new Node(); third = new Node(); head.data = 1; head.next = second; second.data = 2; second.next = third; third.data = 3; third.next = null; printList(head); } } |
class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None self.last_node = None def append(self, data): if self.last_node is None: self.head = Node(data) self.last_node = self.head else: self.last_node.next = Node(data) self.last_node = self.last_node.next def display(self): current = self.head while current is not None: print(current.data, end=' ') current = current.next print() if __name__ == '__main__': L = LinkedList() L.append(1) L.append(2) L.append(3) L.append(4) L.display() |
<script> class Node { constructor() { this.data=0; this.next=null; } } function printList(n) { while (n != null) { document.write(n.data + " "); n = n.next; } } let head = null; let second = null; let third = null; head = new Node(); second = new Node(); third = new Node(); head.data = 1; head.next = second; second.data = 2; second.next = third; third.data = 3; third.next = null; printList(head); </script> |
- Doubly Linked List: A doubly linked list or a two-way linked list is a more complex type of linked list which contains a pointer to the next as well as the previous node in sequence, Therefore, it contains three parts are data, a pointer to the next node, and a pointer to the previous node. This would enable us to traverse the list in the backward direction as well. Below is the image for the same:
- Structure of Doubly Linked List:
struct Node { int data; struct Node* next; struct Node* prev; }; |
static class Node { int data; Node next; Node prev; }; |
class Node: def __init__(self, data): self.previous = None self.data = data self.next = None |
public class Node { public int data; public Node next; public Node prev; }; |
- Creation and Traversal of Doubly Linked List:
#include <bits/stdc++.h> using namespace std; class Node { public: int data; Node* next; Node* prev; }; void push(Node** head_ref, int new_data) { Node* new_node = new Node(); new_node->data = new_data; new_node->next = (*head_ref); new_node->prev = NULL; if ((*head_ref) != NULL) (*head_ref)->prev = new_node; (*head_ref) = new_node; } void printList(Node* node) { Node* last; cout << "\nTraversal in forward" << " direction \n"; while (node != NULL) { cout << " " << node->data << " "; last = node; node = node->next; } cout << "\nTraversal in reverse" << " direction \n"; while (last != NULL) { cout << " " << last->data << " "; last = last->prev; } } int main() { Node* head = NULL; push(&head, 6); push(&head, 7); push(&head, 1); cout << "Created DLL is: "; printList(head); return 0; } |
import java.util.*; class GFG{ static class Node { int data; Node next; Node prev; }; static Node head_ref; static void push(int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = head_ref; new_node.prev = null; if (head_ref != null) head_ref.prev = new_node; head_ref = new_node; } static void printList(Node node) { Node last = null; System.out.print("\nTraversal in forward" + " direction \n"); while (node != null) { System.out.print(" " + node.data + " "); last = node; node = node.next; } System.out.print("\nTraversal in reverse" + " direction \n"); while (last != null) { System.out.print(" " + last.data + " "); last = last.prev; } } public static void main(String[] args) { head_ref = null; push(6); push(7); push(1); System.out.print("Created DLL is: "); printList(head_ref); } } |
class Node: def __init__(self, data): self.previous = None self.data = data self.next = None class DoublyLinkedList: def __init__(self): self.head = None self.start_node = None self.last_node = None def append(self, data): if self.last_node is None: self.head = Node(data) self.last_node = self.head else: new_node = Node(data) self.last_node.next = new_node new_node.previous = self.last_node new_node.next = None self.last_node = new_node def display(self, Type): if Type == 'Left_To_Right': current = self.head while current is not None: print(current.data, end=' ') current = current.next print() else: current = self.last_node while current is not None: print(current.data, end=' ') current = current.previous print() if __name__ == '__main__': L = DoublyLinkedList() L.append(1) L.append(2) L.append(3) L.append(4) L.display('Left_To_Right') L.display('Right_To_Left') |
using System; class GFG{ public class Node { public int data; public Node next; public Node prev; }; static Node head_ref; static void push(int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = head_ref; new_node.prev = null; if (head_ref != null) head_ref.prev = new_node; head_ref = new_node; } static void printList(Node node) { Node last = null; Console.Write("\nTraversal in forward" + " direction \n"); while (node != null) { Console.Write(" " + node.data + " "); last = node; node = node.next; } Console.Write("\nTraversal in reverse" + " direction \n"); while (last != null) { Console.Write(" " + last.data + " "); last = last.prev; } } public static void Main(String[] args) { head_ref = null; push(6); push(7); push(1); Console.Write("Created DLL is: "); printList(head_ref); } } |
OutputCreated DLL is:
Traversal in forward direction
1 7 6
Traversal in reverse direction
6 7 1 - Circular Linked List: A circular linked list is that in which the last node contains the pointer to the first node of the list. While traversing a circular liked list, we can begin at any node and traverse the list in any direction forward and backward until we reach the same node we started. Thus, a circular linked list has no beginning and no end. Below is the image for the same:
- Structure of Circular Linked List:
class Node { public: int data; Node* next; }; |
static class Node { int data; Node next; }; |
class Node: def __init__(self, data): self.data = data self.next = None |
public class Node { public int data; public Node next; }; |
- Creation and Traversal of Circular Linked List:
#include <bits/stdc++.h> using namespace std; class Node { public: int data; Node* next; }; void push(Node** head_ref, int data) { Node* ptr1 = new Node(); Node* temp = *head_ref; ptr1->data = data; 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; } void printList(Node* head) { Node* temp = head; if (head != NULL) { do { cout << temp->data << " "; temp = temp->next; } while (temp != head); } } int main() { Node* head = NULL; push(&head, 12); push(&head, 56); push(&head, 2); push(&head, 11); cout << "Contents of Circular" << " Linked List\n "; printList(head); return 0; } |
import java.util.*; class GFG{ static class Node { int data; Node next; }; static Node push(Node head_ref, int data) { Node ptr1 = new Node(); Node temp = head_ref; ptr1.data = data; 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; return head_ref; } static void printList(Node head) { Node temp = head; if (head != null) { do { System.out.print(temp.data + " "); temp = temp.next; } while (temp != head); } } public static void main(String[] args) { Node head = null; head = push(head, 12); head = push(head, 56); head = push(head, 2); head = push(head, 11); System.out.print("Contents of Circular" + " Linked List\n "); printList(head); } } |
class Node: def __init__(self, data): self.data = data self.next = None class CircularLinkedList: def __init__(self): self.head = None self.last_node = None def append(self, data): if self.last_node is None: self.head = Node(data) self.last_node = self.head else: self.last_node.next = Node(data) self.last_node = self.last_node.next self.last_node.next = self.head def display(self): current = self.head while current is not None: print(current.data, end=' ') current = current.next if current == self.head: break print() if __name__ == '__main__': L = CircularLinkedList() L.append(1) L.append(2) L.append(3) L.append(4) L.display() |
using System; class GFG{ public class Node { public int data; public Node next; }; static Node push(Node head_ref, int data) { Node ptr1 = new Node(); Node temp = head_ref; ptr1.data = data; 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; return head_ref; } static void printList(Node head) { Node temp = head; if (head != null) { do { Console.Write(temp.data + " "); temp = temp.next; } while (temp != head); } } public static void Main(String[] args) { Node head = null; head = push(head, 12); head = push(head, 56); head = push(head, 2); head = push(head, 11); Console.Write("Contents of Circular " + "Linked List\n "); printList(head); } } |
OutputContents of Circular Linked List
11 2 56 12 - Doubly Circular linked list: A Doubly Circular linked list or a circular two-way linked list is a more complex type of linked-list that contains a pointer to the next as well as the previous node in the sequence. The difference between the doubly linked and circular doubly list is the same as that between a singly linked list and a circular linked list. The circular doubly linked list does not contain null in the previous field of the first node. Below is the image for the same:
- Structure of Doubly Circular Linked List:
struct Node { int data; struct Node* next; struct Node* prev; }; |
static class Node { int data; Node next; Node prev; }; |
class Node: def __init__(self, data): self.previous = None self.data = data self.next = None |
public class Node { public int data; public Node next; public Node prev; }; |
- Creation and Traversal of Doubly Circular Linked List:
#include <bits/stdc++.h> using namespace std; struct Node { int data; struct Node* next; struct Node* prev; }; void insertBegin(struct Node** start, int value) { if (*start == NULL) { struct Node* new_node = new Node; new_node->data = value; new_node->next = new_node->prev = new_node; *start = new_node; return; } struct Node* last = (*start)->prev; struct Node* new_node = new Node; new_node->data = value; new_node->next = *start; new_node->prev = last; last->next = (*start)->prev = new_node; *start = new_node; } void display(struct Node* start) { struct 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) { printf("%d ", temp->data); temp = temp->prev; } printf("%d ", temp->data); } int main() { struct Node* start = NULL; insertBegin(&start, 5); insertBegin(&start, 4); insertBegin(&start, 7); printf("Created circular doubly" " linked list is: "); display(start); return 0; } |
import java.util.*; class GFG{ static class Node { int data; Node next; Node prev; }; static Node start = null; static void insertBegin( int value) { if (start == null) { Node new_node = new Node(); new_node.data = value; new_node.next = new_node.prev = new_node; start = new_node; return; } Node last = (start).prev; Node new_node = new Node(); new_node.data = value; new_node.next = start; new_node.prev = last; last.next = (start).prev = new_node; start = new_node; } static void display() { Node temp = start; System.out.printf("\nTraversal in" +" forward direction \n"); while (temp.next != start) { System.out.printf("%d ", temp.data); temp = temp.next; } System.out.printf("%d ", temp.data); System.out.printf("\nTraversal in " + "reverse direction \n"); Node last = start.prev; temp = last; while (temp.prev != last) { System.out.printf("%d ", temp.data); temp = temp.prev; } System.out.printf("%d ", temp.data); } public static void main(String[] args) { insertBegin( 5); insertBegin( 4); insertBegin( 7); System.out.printf("Created circular doubly" + " linked list is: "); display(); } } |
class Node: def __init__(self, data): self.previous = None self.data = data self.next = None class DoublyLinkedList: def __init__(self): self.head = None self.start_node = None self.last_node = None def append(self, data): if self.last_node is None: self.head = Node(data) self.last_node = self.head else: new_node = Node(data) self.last_node.next = new_node new_node.previous = self.last_node new_node.next = self.head self.last_node = new_node def display(self, Type = 'Left_To_Right'): if Type == 'Left_To_Right': current = self.head while current.next is not None: print(current.data, end=' ') current = current.next if current == self.head: break print() else: current = self.last_node while current.previous is not None: print(current.data, end=' ') current = current.previous if current == self.last_node.next: print(self.last_node.next.data, end=' ') break print() if __name__ == '__main__': L = DoublyLinkedList() L.append(1) L.append(2) L.append(3) L.append(4) L.display('Left_To_Right') L.display('Right_To_Left') |
using System; public class GFG{ public class Node { public int data; public Node next; public Node prev; }; static Node start = null; static void insertBegin( int value) { Node new_node = new Node(); if (start == null) { new_node.data = value; new_node.next = new_node.prev = new_node; start = new_node; return; } Node last = (start).prev; new_node.data = value; new_node.next = start; new_node.prev = last; last.next = (start).prev = new_node; start = new_node; } static void display() { Node temp = start; Console.Write("\nTraversal in" +" forward direction \n"); while (temp.next != start) { Console.Write(temp.data + " "); temp = temp.next; } Console.Write(temp.data + " "); Console.Write("\nTraversal in " + "reverse direction \n"); Node last = start.prev; temp = last; while (temp.prev != last) { Console.Write( temp.data + " "); temp = temp.prev; } Console.Write( temp.data + " "); } public static void Main(String[] args) { insertBegin( 5); insertBegin( 4); insertBegin( 7); Console.Write("Created circular doubly" + " linked list is: "); display(); } } |
OutputCreated circular doubly linked list is:
Traversal in forward direction
7 4 5
Traversal in reverse direction
5 4 7 - Header Linked List: A header linked list is a special type of linked list which contains a header node at the beginning of the list. So, in a header linked list START will not point to the first node of the list but START will contain the address of the header node. Below is the image for Grounded Header Linked List:
- Structure of Grounded Header Linked List:
struct link { int info; struct link* next; }; |
class Node: def __init__(self, data): self.data = data self.next = None |
static class link { int info; link next; }; |
public class link { public int info; public link next; }; |
- Creation and Traversal of Header Linked List:
#include <bits/stdc++.h> struct link { int info; struct link* next; }; struct link* start = NULL; struct link* create_header_list(int data) { struct link *new_node, *node; new_node = (struct link*) malloc(sizeof(struct link)); new_node->info = data; new_node->next = NULL; if (start == NULL) { start = (struct link*) malloc(sizeof(struct link)); start->next = new_node; } else { node = start; while (node->next != NULL) { node = node->next; } node->next = new_node; } return start; } struct link* display() { struct link* node; node = start; node = node->next; while (node != NULL) { printf("%d ", node->info); node = node->next; } printf("\n"); return start; } int main() { create_header_list(11); create_header_list(12); create_header_list(13); printf("List After inserting" " 3 elements:\n"); display(); create_header_list(14); create_header_list(15); printf("List After inserting" " 2 more elements:\n"); display(); return 0; } |
class GFG{ static class link { int info; link next; }; static link start = null; static link create_header_list(int data) { link new_node, node; new_node = new link(); new_node.info = data; new_node.next = null; if (start == null) { start = new link(); start.next = new_node; } else { node = start; while (node.next != null) { node = node.next; } node.next = new_node; } return start; } static link display() { link node; node = start; node = node.next; while (node != null) { System.out.printf("%d ", node.info); node = node.next; } System.out.printf("\n"); return start; } public static void main(String[] args) { create_header_list(11); create_header_list(12); create_header_list(13); System.out.printf("List After inserting" + " 3 elements:\n"); display(); create_header_list(14); create_header_list(15); System.out.printf("List After inserting" + " 2 more elements:\n"); display(); } } |
class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = Node(0) self.last_node = self.head def append(self, data): self.last_node.next = Node(data) self.last_node = self.last_node.next def display(self): current = self.head.next while current is not None: print(current.data, end=' ') current = current.next print() if __name__ == '__main__': L = LinkedList() L.append(1) L.append(2) L.append(3) L.append(4) L.display() |
using System; public class GFG{ public class link { public int info; public link next; }; static link start = null; static link create_header_list(int data) { link new_node, node; new_node = new link(); new_node.info = data; new_node.next = null; if (start == null) { start = new link(); start.next = new_node; } else { node = start; while (node.next != null) { node = node.next; } node.next = new_node; } return start; } static link display() { link node; node = start; node = node.next; while (node != null) { Console.Write("{0} ", node.info); node = node.next; } Console.Write("\n"); return start; } public static void Main(String[] args) { create_header_list(11); create_header_list(12); create_header_list(13); Console.Write("List After inserting" + " 3 elements:\n"); display(); create_header_list(14); create_header_list(15); Console.Write("List After inserting" + " 2 more elements:\n"); display(); } } |
OutputList After inserting 3 elements:
11 12 13
List After inserting 2 more elements:
11 12 13 14 15
|
