Month: September 2021

Linked List

A linked list is a linear data structure that does not store the members at adjacent memory locations. In the related Links, the components are connected using points. A linked list of nodes comprises basic words, where each node has a data field and a reference(link) to the following node in the link.

Singly Linked List

This is the simplest type of related Link in which every node holds certain information and a reference to the following node of the same data type. The node carries a reference to the following node, meaning that the node stores in the following node address. Only one direction can a single related Links travel data. The picture for the same is below.

Structure of Singly Linked List

// Node of a doubly linked list
static class Node
{
int data;

// Pointer to next node in LL
Node next;
};

//this code is contributed by ali

Creation and Traversal of Singly Linked List:

// Java program to illustrate
// creation and traversal of
// Singly Linked List
class GFG{

// Structure of Node
static class Node
{
int data;
Node next;
};

// Function to print the content 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;
}
}

// Driver Code
public static void main(String[] args)
{
Node head = null;
Node second = null;
Node third = null;

// Allocate 3 nodes in
// the heap
head = new Node();
second = new Node();
third = new Node();

// Assign data in first
// node
head.data = 1;

// Link first node with
// second
head.next = second;

// Assign data to second
// node
second.data = 2;
second.next = third;

// Assign data to third
// node
third.data = 3;
third.next = null;

printList(head);
}
}

// This code is contributed by Ali

Doubly Linked List

A double-related Links or a two-way listed link is a more complicated form of a listed link that has a sequential indicator for the next node and the previous one. Hence it comprises three pieces of data. An indicator for the next node. An indicator for the previous one. This would allow us also to go back through the list. The picture below is identical.

Structure of Doubly Related Links

// Doubly linked list
// node
static class Node
{
int data;

// Pointer to next node in DLL
Node next;

// Pointer to the previous node in DLL
Node prev;

};

// This code is contributed by ali

Creation and Traversal of Doubly Related Links:

// Java program to illustrate
// creation and traversal of
// Doubly Linked List
import java.util.*;
class GFG{

// Doubly linked list
// node
static class Node
{
int data;
Node next;
Node prev;
};

static Node head_ref;

// Function to push a new
// element in the Doubly
// Linked List
static void push(int new_data)
{
// Allocate node
Node new_node = new Node();

// Put in the data
new_node.data = new_data;

// Make next of new node as
// head and previous as null
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;

// Move the head to point to
// the new node
head_ref = new_node;
}

// Function to traverse the
// Doubly LL in the forward
// & backward direction
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;
}
}

// Driver Code
public static void main(String[] args)
{
// Start with the empty list
head_ref = null;

// Insert 6.
// So linked list becomes
// 6.null
push(6);

// Insert 7 at the beginning.
// So linked list becomes
// 7.6.null
push(7);

// Insert 1 at the beginning.
// So linked list becomes
// 1.7.6.null
push(1);

System.out.print(“Created DLL is: “);
printList(head_ref);
}
}

// This code is contributed by Ali

Circular Linked List

A circular related Links holds the pointer to the initial node of the list. While we go through a circular. We may begin at any node and go back. Forth through the list in any direction until we have reached the same node that we started. So there is no start and no end to a circular related Links. The picture below is identical.

Structure of Circular Related Links:

// Structure for a node
static class Node
{
int data;

// Pointer to next node in CLL
Node next;
};

// This code is contributed by ali2110

Creation and Traversal of Circular Related Links:

// Java program to illustrate
// creation and traversal of
// Circular LL
import java.util.*;
class GFG{

// Structure for a
// node
static class Node
{
int data;
Node next;
};

// Function to insert a node
// at the beginning of Circular
// LL
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);
}
}

// Driver Code
public static void main(String[] args)
{
// Initialize list as empty
Node head = null;

// Created linked list will
// be 11.2.56.12
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);
}
}

// This code is contributed by Ali1

Double Circular

A dubious situation A circular related Link or a circular linked double-way list is a more complicated form of a connected list that contains both the next and the last nodes in the sequence. The difference between the two doubling lists is the same as between the one-bound list and the one-bound list. In the preceding field of the first node, the circulated double-related Links does not include null. The picture for the same is below.

Structure of Doubly Circular Related Links:

// Structure of a Node
static class Node
{
int data;

// Pointer to next node in DCLL
Node next;

// Pointer to the previous node in DCLL
Node prev;

};

//this code is contributed by ali2110

Creation and Traversal of Doubly Circular Linked List:

// Java program to illustrate creation
// & traversal of Doubly Circular LL
import java.util.*;

class GFG{

// Structure of a Node
static class Node
{
int data;
Node next;
Node prev;
};

// Start with the empty list
static Node start = null;

// Function to insert Node at
// the beginning of the List
static void insertBegin(
int value)
{
// If the list is empty
if (start == null)
{
Node new_node = new Node();
new_node.data = value;
new_node.next
= new_node.prev = new_node;
start = new_node;
return;
}

// Pointer points to last Node
Node last = (start).prev;

Node new_node = new Node();

// Inserting the data
new_node.data = value;

// Update the previous and
// next of new node
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;

}

// Function to traverse the circular
// doubly linked list
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)
{

    // Print the data
    System.out.printf("%d ", temp.data);
    temp = temp.prev;
}
System.out.printf("%d ", temp.data);

}

// Driver Code
public static void main(String[] args)
{

// Insert 5
// So linked list becomes 5.null
insertBegin( 5);

// Insert 4 at the beginning
// So linked list becomes 4.5
insertBegin( 4);

// Insert 7 at the end
// So linked list becomes 7.4.5
insertBegin( 7);

System.out.printf("Created circular doubly"
    + " linked list is: ");
display();

}
}

// This code is contributed by Ali

Header Linked List

A linked list header is a particular form of related Links containing a header node at the start of the list. START will thus not point at the initial node of the list in header-related Links, but START will include the header node address. Below is the picture of the related Links Grounded Header.

Structure of Header Linked List:

// Structure of the list
static class link {
int info;

// Pointer to the next node
link next;

};

// this code is contributed by Ali2110

Creation and Traversal of Header Linked List:

// Java program to illustrate creation
// and traversal of Header Linked List

class GFG{
// Structure of the list
static class link {
int info;
link next;
};

// Empty List
static link start = null;

// Function to create header of the
// header linked list
static link create_header_list(int data)
{

// Create a new node
link new_node, node;
new_node = new link();
new_node.info = data;
new_node.next = null;

// If it is the first node
if (start == null) {

    // Initialize the start
    start = new link();
    start.next = new_node;
}
else {

    // Insert the node in the end
    node = start;
    while (node.next != null) {
        node = node.next;
    }
    node.next = new_node;
}
return start;

}

// Function to display the
// header linked list
static link display()
{
link node;
node = start;
node = node.next;

// Traverse until node is
// not null
while (node != null) {

    // Print the data
    System.out.printf("%d ", node.info);
    node = node.next;
}
System.out.printf("\n");

// Return the start pointer
return start;

}

// Driver Code
public static void main(String[] args)
{
// Create the list
create_header_list(11);
create_header_list(12);
create_header_list(13);

// Print the list
System.out.printf("List After inserting"
    + " 3 elements:\n");
display();
create_header_list(14);
create_header_list(15);

// Print the list
System.out.printf("List After inserting"
    + " 2 more elements:\n");
display();

}
}

// This code is contributed by Ali