Types of Linked List
Types of Linked List
Types of linked list
-
- Singly linked lists
- Doubly linked lists
- Circular linked lists
1. Singly Linked List
A linked list is a set of nodes where each node has two fields ‘data’ and ‘link’. The ‘data’ field stores actual piecce of information ad ‘link’ field is used to point to next node. Basically ‘link’ field is address only.
Structure of Singly Linked List
static class Node
{
int data;
Node next;
};
Creation and Traversal of Singly Linked List in C++
#include <bits/stdc++.h>
using namespace std;
// Structure of Node
class Node {
public:
int data;
Node* next;
};
// Function to print the element of linked list starting from the given node
void printList(Node* n)
{
while (n != NULL) {
// Print the data
cout << n->data << " ";
n = n->next;
}
}
int main()
{
Node* head = NULL;
Node* second = NULL;
Node* third = NULL;
// Allocate 3 nodes
head = new Node();
second = new Node();
third = new Node();
// allocate data in first node
head->data = 1;
// Link first node with second
head->next = second;
// allocate data to second node
second->data = 2;
second->next = third;
// allocate data to third node
third->data = 3;
third->next = NULL;
printList(head);
return 0;
}
Creation and Traversal of Singly Linked List in Python
# structure of Node
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
self.last_node = None
# function to add content to linked list
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
# function to print the element of linked list
def display(self):
current = self.head
# traversing the linked list
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)
# displaying elements of linked list
L.display()
Output
1 2 3
Creation and Traversal of Singly Linked List in Java
class studyExpert{
// Structure of Node
static class Node
{
int data;
Node next;
};
// Function to print the element of linked list starting from the given node
static void printList(Node n)
{
// Iterate till n reaches null
while (n != null)
{
// Print the data
System.out.print(n.data + " ");
n = n.next;
}
}
public static void main(String[] args)
{
Node head = null;
Node second = null;
Node third = null;
// Assign 3 nodes in the heap
head = new Node();
second = new Node();
third = new Node();
// allocate data in first node
head.data = 1;
head.next = second;
// allocate data to second node
second.data = 2;
second.next = third;
// allocate data to third node
third.data = 3;
third.next = null;
printList(head);
}
}
Output
1 2 3
2. Doubly Linked List
In double link list every node has link to its previous node and next node . So, we traverse forward by using next field and also can traverse backward by using previous field. Every node in a double list contain three field and they are shown in following figure.
Structure of Double Linked List
static class Node
{
int data;
Node next;
Node prev;
};
Creation and Traversal of Doubly Linked List in C++
#include <bits/stdc++.h>
using namespace std;
// Doubly linked list node
class Node {
public:
int data;
Node* next;
Node* prev;
};
// Function to push a new element in the Doubly Linked List
void push(Node** head_ref, int new_data)
{
// assign node
Node* new_node = new Node();
// Put in the data
new_node->data = new_data;
new_node->next = (*head_ref);
new_node->prev = NULL;
// Change prev of head node to the new node
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) {
// 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;
}
}
int main()
{
// Start with the empty list
Node* head = NULL;
// Insert 6.
push(&head, 6);
// Insert 7 at the beginning.
push(&head, 7);
// Insert 1 at the beginning.
push(&head, 1);
cout << "Created DLL is: ";
printList(head);
return 0;
}
Output
Created DLL is: Traversal in forward direction 1 7 6 Traversal in reverse direction 6 7 1
Creation and Traversal of Doubly Linked List in Python
# structure of Node
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
# function to add elements to doubly linked list
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')
Output
Created DLL is: Traversal in forward direction 1 7 6 Traversal in reverse direction 6 7 1
Creation and Traversal of Doubly Linked List in Java
import java.util.*;
class studyExpert{
// Doubly linked list node
static class Node
{
int data;
Node next;
Node prev;
};
static Node head_ref;
// Function to insert a new element in the Doubly Linked List
static void push(int new_data)
{
// assign node
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)
{
// Print the data
System.out.print(" " + node.data +
" ");
last = node;
node = node.next;
}
System.out.print("\nTraversal in reverse" +
" direction \n");
while (last != null)
{
// Print the data
System.out.print(" " + last.data +
" ");
last = last.prev;
}
}
public static void main(String[] args)
{
// Start with the empty list
head_ref = null;
// Insert 6.
push(6);
// Insert 7 at the beginning.
push(7);
// Insert 1 at the beginning.
push(1);
System.out.print("Created DLL is: ");
printList(head_ref);
}
}
Output
Created DLL is: Traversal in forward direction 1 7 6 Traversal in reverse direction 6 7 1
3. Circular Linked List
Circular Linked list is a sequence of elements in which every element has link to its next element in the sequence and the last element has link to the first element in the sequence. That means circular linked list is similar to the single linked list excluded that the last node points to the first node in the list
Structure of Circular Linked List
class Node {
public:
int data;
Node* next;
};
Creation and Traversal of Circular Linked List in C++
#include <bits/stdc++.h>
using namespace std;
// Structure for a node
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 linked list is not NULL then set the next of last node
if (*head_ref != NULL) {
while (temp->next != *head_ref) {
temp = temp->next;
}
temp->next = ptr1;
}
// For the first node
else
ptr1->next = ptr1;
*head_ref = ptr1;
}
// Function to print nodes in the Circular Linked List
void printList(Node* head)
{
Node* temp = head;
if (head != NULL) {
do {
cout << temp->data << " ";
temp = temp->next;
} while (temp != head);
}
}
int main()
{
// Initialize list as empty
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;
}
Output
Contents of Circular Linked List 11 2 56 12
Creation and Traversal of Circular Linked List in Python
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
self.last_node = None
# function to add elements to circular linked list
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
# function to print the content of circular linked list
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()
Output
Contents of Circular Linked List 11 2 56 12
Creation and Traversal of Circular Linked List in Java
import java.util.*;
class studyExperts{
// Structure for a node
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 linked list is not null then set the next of last node
if (head_ref != null)
{
while (temp.next != head_ref)
{
temp = temp.next;
}
temp.next = ptr1;
}
// For the first node
else
ptr1.next = ptr1;
head_ref = ptr1;
return head_ref;
}
// Function to print nodes in the Circular Linked List
static void printList(Node head)
{
Node temp = head;
if (head != null)
{
do
{
// Print the data
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);
}
}
Output
Contents of Circular Linked List 11 2 56 12
Read more, Linked List Operations