Data structures are introduced in order to store, organize and manipulate data in programming

languages. They are designed in a way that makes accessing and processing of the data a little
easier and simpler. These data structures are not confined to one particular programming
language; they are just pieces of code that structure data in the memory.

Data types are often confused as a type of data structures, but it is not precisely correct even
though they are referred to as Abstract Data Types. Data types represent the nature of the data
while data structures are just a collection of similar or different data types in one

There are usually just two types of data structures −

 Linear
 Non-Linear

Linear Data Structures

The data is stored in linear data structures sequentially. These are rudimentary structures since
the elements are stored one after the other without applying any mathematical operations.
Linear data structures are usually easy to implement but since the memory allocation might
become complicated, time and space complexities increase. Few examples of linear data
structures include −

 Arrays
 Linked Lists
 Stacks
 Queues

Based on the data storage methods, these linear data structures are divided into two sub-types.
They are − static and dynamic data structures.

Static Linear Data Structures

In Static Linear Data Structures, the memory allocation is not scalable. Once the entire memory
is used, no more space can be retrieved to store more data. Hence, the memory is required to be
reserved based on the size of the program. This will also act as a drawback since reserving more
memory than required can cause a wastage of memory blocks.

The best example for static linear data structures is an array.

Dynamic Linear Data Structures

In Dynamic linear data structures, the memory allocation can be done dynamically when
required. These data structures are efficient considering the space complexity of the program.

Few examples of dynamic linear data structures include: linked lists, stacks and queues.

Non-Linear Data Structures

Non-Linear data structures store the data in the form of a hierarchy. Therefore, in contrast to the
linear data structures, the data can be found in multiple levels and are difficult to traverse
through.
However, they are designed to overcome the issues and limitations of linear data structures. For
instance, the main disadvantage of linear data structures is the memory allocation. Since the data
is allocated sequentially in linear data structures, each element in these data structures uses one
whole memory block. However, if the data uses less memory than the assigned block can hold,
the extra memory space in the block is wasted. Therefore, non-linear data structures are
introduced. They decrease the space complexity and use the memory optimally.

Few types of non-linear data structures are −

 Graphs
 Trees
 Tries
 Maps

Linked Lists
A linked list is a collection of “nodes” connected together via links. These nodes consist of the
data to be stored and a pointer to the address of the next node within the linked list. In the case of
arrays, the size is limited to the definition, but in linked lists, there is no defined size. Any
amount of data can be stored in it and can be deleted from it.

Linked List Representation

Linked list can be visualized as a chain of nodes, where every node points to the next node.

As per the above illustration, following are the important points to be considered.
  Linked List contains a link element called first (head).
 Each link carries a data field(s) and a link field called next.
 Each link is linked with its next link using its next link.
 Last link carries a link as null to mark the end of the list.

Types of Linked List

Following are the various types of linked list.

Singly Linked Lists

Singly linked lists contain two “buckets” in one node; one bucket holds the data and the other
bucket holds the address of the next node of the list. Traversals can be done in one direction only
as there is only a single link between two nodes of the same list.

Doubly Linked Lists

Doubly Linked Lists contain three “buckets” in one node; one bucket holds the data and the other
buckets hold the addresses of the previous and next nodes in the list. The list is traversed twice as
the nodes in the list are connected to each other from both sides.

Circular Linked Lists

Circular linked lists can exist in both singly linked list and doubly linked list.

Since the last node and the first node of the circular linked list are connected, the traversal in this
linked list will go on forever until it is broken.
Basic Operations in the Linked Lists

The basic operations in the linked lists are insertion, deletion, searching, display, and deleting an
element at a given key. These operations are performed on Singly Linked Lists as given below −

 Insertion − Adds an element at the beginning of the list.

 Deletion − Deletes an element at the beginning of the list.
 Display − Displays the complete list.
 Search − Searches an element using the given key.
 Delete − Deletes an element using the given key.

Insertion Operation

Adding a new node in linked list is a more than one step activity. We shall learn this with
diagrams here. First, create a node using the same structure and find the location where it
has to be inserted.

 Imagine that we are inserting a node B (NewNode), between A (LeftNode) and C

(RightNode). Then point [Link] to C −
 [Link] −> RightNode;
 It should look like this −


 Now, the next node at the left should point to the new node.
 [Link] −> NewNode;
  This will put the new node in the middle of the two. The new list should look like this −
 Insertion in linked list can be done in three different ways. They are explained as follows
−

Insertion at Beginning

 In this operation, we are adding an element at the beginning of the list.

Algorithm

 1. START
 2. Create a node to store the data
 3. Check if the list is empty
 4. If the list is empty, add the data to the node and assign the head pointer to it.
 5 If the list is not empty, add the data to a node and link to the current head. Assign the
head to the newly added node.
 6. END

Example

Following are the implementations of this operation in various programming languages −

public class Linked_List {

static class node {
int data;
node next;
node (int value) {
data = value;
next = null;
}
}
static node head;
// display the list
static void printList() {
node p = head;
[Link]("\n[");

//start from the beginning

while(p != null) {
[Link](" " + [Link] + " ");
p = [Link];
}
[Link]("]");
}

//insertion at the beginning

static void insertatbegin(int data) {

//create a link
node lk = new node(data);;

// point it to old first node

[Link] = head;

//point first to new first node

head = lk;
}
public static void main(String args[]) {
int k=0;
insertatbegin(12);
insertatbegin(22);
insertatbegin(30);
insertatbegin(44);
insertatbegin(50);
insertatbegin(33);
[Link]("Linked List: ");
 // print list
printList();
}
}

Output
Linked List:
[33 50 44 30 22 12 ]

Insertion at Ending

In this operation, we are adding an element at the ending of the list.

Algorithm

1. START
2. Create a new node and assign the data
3. Find the last node
4. Point the last node to new node
5. END

Example

public class Linked_List {

static class node {
int data;
node next;
node (int value) {
data = value;
next = null;
}
}
static node head;

// display the list

static void printList() {
node p = head;
[Link]("\n[");
 //start from the beginning
while(p != null) {
[Link](" " + [Link] + " ");
p = [Link];
}
[Link]("]");
}

//insertion at the beginning

static void insertatbegin(int data) {

//create a link
node lk = new node(data);;

// point it to old first node

[Link] = head;

//point first to new first node

head = lk;
}
static void insertatend(int data) {

//create a link
node lk = new node(data);
node linkedlist = head;

// point it to old first node

while([Link] != null)
linkedlist = [Link];

//point first to new first node

[Link] = lk;
}
public static void main(String args[]) {
int k=0;
 insertatbegin(12);
insertatbegin(22);
insertatbegin(30);
insertatend(44);
insertatend(50);
insertatend(33);
[Link]("Linked List: ");

// print list
printList();
}
}
Output
Linked List:
[ 30 22 12 44 50 33 ]

Insertion at a Given Position

In this operation, we are adding an element at any position within the list.

Algorithm

1. START
2. Create a new node and assign data to it
3. Iterate until the node at position is found
4. Point first to new first node
5. END

Example

public class Linked_List {

static class node {
int data;
node next;
node (int value) {
data = value;
next = null;
}
}
static node head;

// display the list

static void printList() {
node p = head;
[Link]("\n[");

//start from the beginning

while(p != null) {
[Link](" " + [Link] + " ");
p = [Link];
}
[Link]("]");
}

//insertion at the beginning

static void insertatbegin(int data) {

//create a link
node lk = new node(data);;

// point it to old first node

[Link] = head;

//point first to new first node

head = lk;
}
static void insertafternode(node list, int data) {
node lk = new node(data);
[Link] = [Link];
[Link] = lk;
}
public static void main(String args[]) {
int k=0;
insertatbegin(12);
 insertatbegin(22);
insertatbegin(30);
insertatbegin(44);
insertafternode([Link], 50);
insertafternode([Link], 33);
[Link]("Linked List: ");

// print list
printList();
}
}
Output
Linked List:

[44 30 50 33 22 12 ]

Deletion Operation

Deletion is also a more than one step process. We shall learn with pictorial representation. First,
locate the target node to be removed, by using searching algorithms.

The left (previous) node of the target node now should point to the next node of the target node −

[Link] −> [Link];

This will remove the link that was pointing to the target node. Now, using the following code, we
will remove what the target node is pointing at.

[Link] −> NULL;

We need to use the deleted node. We can keep that in memory otherwise we can simply
deallocate memory and wipe off the target node completely.

Similar steps should be taken if the node is being inserted at the beginning of the list. While
inserting it at the end, the second last node of the list should point to the new node and the new
node will point to NULL.

Deletion in linked lists is also performed in three different ways. They are as follows −

Deletion at Beginning

In this deletion operation of the linked, we are deleting an element from the beginning of the list.
For this, we point the head to the second node.

Algorithm

1. START
2. Assign the head pointer to the next node in the list
3. END

Example

public class Linked_List {

static class node {
int data;
 node next;
node (int value) {
data = value;
next = null;
}
}
static node head;

// display the list

static void printList() {
node p = head;
[Link]("\n[");

//start from the beginning

while(p != null) {
[Link](" " + [Link] + " ");
p = [Link];
}
[Link]("]");
}

//insertion at the beginning

static void insertatbegin(int data) {

//create a link
node lk = new node(data);;

// point it to old first node

[Link] = head;

//point first to new first node

head = lk;
}
static void deleteatbegin() {
head = [Link];
}
 public static void main(String args[]) {
int k=0;
insertatbegin(12);
insertatbegin(22);
insertatbegin(30);
insertatbegin(44);
insertatbegin(50);
insertatbegin(33);
[Link]("Linked List: ");

// print list
printList();
deleteatbegin();
[Link]("\nLinked List after deletion: ");

// print list
printList();
}
}
Output
Linked List:
[ 33 50 44 30 22 12 ]

Linked List after deletion:

[50 44 30 22 12 ]

Deletion at Ending

In this deletion operation of the linked, we are deleting an element from the ending of the list.

Algorithm

1. START
2. Iterate until you find the second last element in the list.
3. Assign NULL to the second last element in the list.
4. END
Example

public class Linked_List {

static class node {
int data;
node next;
node (int value) {
data = value;
next = null;
}
}
static node head;

// display the list

static void printList() {
node p = head;
[Link]("\n[");

//start from the beginning

while(p != null) {
[Link](" " + [Link] + " ");
p = [Link];
}
[Link]("]");
}

//insertion at the beginning

static void insertatbegin(int data) {

//create a link
node lk = new node(data);;

// point it to old first node

[Link] = head;

//point first to new first node

 head = lk;
}
static void deleteatend() {
node linkedlist = head;
while ([Link] != null)
linkedlist = [Link];
[Link] = null;
}
public static void main(String args[]) {
int k=0;
insertatbegin(12);
insertatbegin(22);
insertatbegin(30);
insertatbegin(44);
insertatbegin(50);
insertatbegin(33);
[Link]("Linked List: ");

// print list
printList();

//deleteatbegin();
deleteatend();
[Link]("\nLinked List after deletion: ");

// print list
printList();
}
} Output
Linked List:
[ 33 50 44 30 22 12 ]
Linked List after deletion:

[ 33 50 44 30 22 ]
Deletion at a Given Position

In this deletion operation of the linked, we are deleting an element at any position of the list.

Algorithm

1. START
2. Iterate until find the current node at position in the list
3. Assign the adjacent node of current node in the list to its previous node.
4. END

Example

public class Linked_List {

static class node {
int data;
node next;
node (int value) {
data = value;
next = null;
}
}
static node head;

// display the list

static void printList() {
node p = head;
[Link]("\n[");

//start from the beginning

while(p != null) {
[Link](" " + [Link] + " ");
p = [Link];
}
[Link]("]");
}

//insertion at the beginning

static void insertatbegin(int data) {

//create a link
node lk = new node(data);;

// point it to old first node

[Link] = head;

//point first to new first node

head = lk;
}
static void deletenode(int key) {
node temp = head;
node prev = null;
if (temp != null && [Link] == key) {
head = [Link];
return;
}

// Find the key to be deleted

while (temp != null && [Link] != key) {
prev = temp;
temp = [Link];
}

// If the key is not present

if (temp == null) return;

// Remove the node

[Link] = [Link];
}
public static void main(String args[]) {
int k=0;
insertatbegin(12);
insertatbegin(22);
 insertatbegin(30);
insertatbegin(44);
insertatbegin(50);
insertatbegin(33);
[Link]("Linked List: ");

// print list
printList();

//deleteatbegin();
//deleteatend();
deletenode(12);
[Link]("\nLinked List after deletion: ");

// print list
printList();
}
}
Output
Linked List:

[ 33 50 44 30 22 12 ]
Linked List after deletion:

[ 33 50 44 30 22 ]

Reverse Operation

This operation is a thorough one. We need to make the last node to be pointed by the head node
and reverse the whole linked list.
First, we traverse to the end of the list. It should be pointing to NULL. Now, we shall make it
point to its previous node −

We have to make sure that the last node is not the last node. So we'll have some temp node,
which looks like the head node pointing to the last node. Now, we shall make all left side nodes
point to their previous nodes one by one.

Except the node (first node) pointed by the head node, all nodes should point to their
predecessor, making them their new successor. The first node will point to NULL.

We'll make the head node point to the new first node by using the temp node.

Algorithm

Step by step process to reverse a linked list is as follows −

1 START
2. We use three pointers to perform the reversing: prev, next, head.
3. Point the current node to head and assign its next value to the prev node.
4. Iteratively repeat the step 3 for all the nodes in the list.
5. Assign head to the prev node.

Example

public class Linked_List {

static Node head;
static class Node {
int data;
Node next;
Node (int value) {
data = value;
next = null;
}
}

// display the list

static void printList(Node node) {
[Link]("\n[");

//start from the beginning

while(node != null) {
[Link](" " + [Link] + " ");
node = [Link];
}
[Link]("]");
}
static Node reverseList(Node head) {
Node prev = null;
Node cur = head;
Node temp = null;
while (cur != null) {
temp = [Link];
[Link] = prev;
prev = cur;
cur = temp;
 }
head = prev;
return head;
}
public static void main(String args[]) {
Linked_List list = new Linked_List();
[Link] = new Node(33);
[Link] = new Node(50);
[Link] = new Node(44);
[Link] = new Node(22);
[Link] = new Node(12);
[Link]("Linked List: ");

// print list
[Link](head);
head = [Link](head);
[Link]("\nReversed linked list ");
[Link](head);
}
}
Output
Linked List:
[ 33 50 44 22 12 ]
Reversed linked list

[ 12 22 44 50 33 ]

Search Operation

Searching for an element in the list using a key element. This operation is done in the same way
as array search; comparing every element in the list with the key element given.

Algorithm

1 START
2 If the list is not empty, iteratively check if the list contains the key
3 If the key element is not present in the list, unsuccessful search
4 END
Example

public class Linked_List {

static class node {
int data;
node next;
node (int value) {
data = value;
next = null;
}
}
static node head;

// display the list

static void printList() {
node p = head;
[Link]("\n[");

//start from the beginning

while(p != null) {
[Link](" " + [Link] + " ");
p = [Link];
}
[Link]("]");
}

//insertion at the beginning

static void insertatbegin(int data) {

//create a link
node lk = new node(data);;

// point it to old first node

[Link] = head;

//point first to new first node

 head = lk;
}
static int searchlist(int key) {
node temp = head;
while(temp != null) {
if ([Link] == key) {
return 1;
}
temp=[Link];
}
return 0;
}
public static void main(String args[]) {
int k=0;
insertatbegin(12);
insertatbegin(22);
insertatbegin(30);
insertatbegin(44);
insertatbegin(50);
insertatbegin(33);
[Link]("Linked List: ");

// print list
printList();
k = searchlist(44);
if (k == 1)
[Link]("\nElement is found");
else
[Link]("\nElement is not present in the list");
}
}
Output
Linked List:

[33 50 44 30 22 12 ]
Element is found
Traversal Operation

The traversal operation walks through all the elements of the list in an order and displays the
elements in that order.

Algorithm

1. START
2. While the list is not empty and did not reach the end of the list, print the data in each node
3. END

Example

public class Linked_List {

static class node {
int data;
node next;
node (int value) {
data = value;
next = null;
}
}
static node head;

// display the list

static void printList() {
node p = head;
[Link]("\n[");

//start from the beginning

while(p != null) {
[Link](" " + [Link] + " ");
p = [Link];
}
[Link]("]");
}

//insertion at the beginning

 static void insertatbegin(int data) {

//create a link
node lk = new node(data);;

// point it to old first node

[Link] = head;

//point first to new first node

head = lk;
}
public static void main(String args[]) {
int k=0;
insertatbegin(12);
insertatbegin(22);
insertatbegin(30);
insertatbegin(44);
insertatbegin(50);
insertatbegin(33);
[Link]("Linked List: ");

// print list
printList();
}
}

Output
Linked List:
[ 33 50 44 30 22 12 ]

Data Structure Doubly Linked List:

Doubly Linked List is a variation of Linked list in which navigation is possible in both ways,
either forward and backward easily as compared to Single Linked List. Following are the
important terms to understand the concept of doubly linked list.
  Link − Each link of a linked list can store a data called an element.
 Next − Each link of a linked list contains a link to the next link called Next.
 Prev − Each link of a linked list contains a link to the previous link called Prev.
 Linked List − A Linked List contains the connection link to the first link called First and
to the last link called Last.

Doubly Linked List Representation

As per the above illustration, following are the important points to be considered.

 Doubly Linked List contains a link element called first and last.
 Each link carries a data field(s) and a link field called next.
 Each link is linked with its next link using its next link.
 Each link is linked with its previous link using its previous link.
 The last link carries a link as null to mark the end of the list.

Basic Operations

Following are the basic operations supported by a list.

 Insertion − Adds an element at the beginning of the list.

 Deletion − Deletes an element at the beginning of the list.
 Insert Last − Adds an element at the end of the list.
 Delete Last − Deletes an element from the end of the list.
 Insert After − Adds an element after an item of the list.
 Delete − Deletes an element from the list using the key.
 Display forward − Displays the complete list in a forward manner.
 Display backward − Displays the complete list in a backward manner.

Insertion at the Beginning

In this operation, we create a new node with three compartments, one containing the data, the
others containing the address of its previous and next nodes in the list. This new node is inserted
at the beginning of the list.

Algorithm

1. START
2. Create a new node with three variables: prev, data, next.
3. Store the new data in the data variable
4. If the list is empty, make the new node as head.
5. Otherwise, link the address of the existing first node to the next variable of the new node, and
assign null to the prev variable.
6. Point the head to the new node.
7. END

Example

//Java code for doubly linked list

import [Link].*;
class Node {
public int data;
public int key;
public Node next;
public Node prev;
public Node(int data, int key) {
[Link] = data;
[Link] = key;
[Link] = null;
[Link] = null;
}
}
public class Main {
//this link always point to first Link
static Node head = null;
//this link always point to last Link
static Node last = null;
static Node current = null;
// is list empty
public static boolean is_empty() {
return head == null;
}
//display the doubly linked list
public static void print_list() {
 Node ptr = head;
while (ptr != null) {
[Link]("(" + [Link] + "," + [Link] + ")");
ptr = [Link];
}
}
//insert link at the first location
public static void insert_first(int key, int data) {
//create a link
Node link = new Node(data, key);
if (is_empty()) {
//make it the last link
last = link;
} else {
//update first prev link
[Link] = link;
}
//point it to old first link
[Link] = head;
//point first to new first link
head = link;
}
public static void main(String[] args) {
insert_first(1, 10);
insert_first(2, 20);
insert_first(3, 30);
insert_first(4, 1);
insert_first(5, 40);
insert_first(6, 56);
[Link]("\nDoubly Linked List: ");
print_list();
}
} Output
Doubly Linked List: (6,56)(5,40)(4,1)(3,30)(2,20)(1,10)

Deletion at the Beginning

This deletion operation deletes the existing first nodes in the doubly linked list. The head is
shifted to the next node and the link is removed.

Algorithm

1. START
2. Check the status of the doubly linked list
3. If the list is empty, deletion is not possible
4. If the list is not empty, the head pointer is shifted to the next node.
5. END

Example

//Java code for doubly linked list

import [Link].*;
class Node {
public int data;
public int key;
public Node next;
public Node prev;
public Node(int data, int key) {
[Link] = data;
[Link] = key;
[Link] = null;
[Link] = null;
}
}
public class Main {
//this link always point to first Link
public static Node head = null;
//this link always point to last Link
public static Node last = null;
//this link always point to current Link
public static Node current = null;
//is list empty
public static boolean isEmpty() {
return head == null;
}
//display the doubly linked list
public static void printList() {
Node ptr = head;
while (ptr != null) {
[Link]("(" + [Link] + "," + [Link] + ") ");
ptr = [Link];
}
}
//insert link at the first location
public static void insertFirst(int key, int data) {
//create a link
Node link = new Node(data, key);
if (isEmpty()) {
//make it the last link
last = link;
} else {
//update first prev link
[Link] = link;
}
//point it to old first link
[Link] = head;
head = link;
}
//delete the first item
public static Node deleteFirst() {
//save reference to first link
Node tempLink = head;
//if only one link
if ([Link] == null) {
last = null;
} else {
[Link] = null;
}
head = [Link];
//return the deleted link
 return tempLink;
}
public static void main(String[] args) {
insertFirst(1, 10);
insertFirst(2, 20);
insertFirst(3, 30);
insertFirst(4, 1);
insertFirst(5, 40);
insertFirst(6, 56);
[Link]("\nDoubly Linked List: ");
printList();
[Link]("\nList after deleting first record: ");
deleteFirst();
printList();
}
} Output
Doubly Linked List:
(6,56) (5,40) (4,1) (3,30) (2,20) (1,10)
List after deleting first record:
(5,40) (4,1) (3,30) (2,20) (1,10)

Insertion at the End

In this insertion operation, the new input node is added at the end of the doubly linked list; if the
list is not empty. The head will be pointed to the new node, if the list is empty.

Algorithm

1. START
2. If the list is empty, add the node to the list and point the head to it.
3. If the list is not empty, find the last node of the list.
4. Create a link between the last node in the list and the new node.
5. The new node will point to NULL as it is the new last node.
6. END

Example

import [Link].*;
class Node {
public int data;
public int key;
public Node next;
public Node prev;
public Node(int data, int key) {
[Link] = data;
[Link] = key;
[Link] = null;
[Link] = null;
}
}
public class Main {
static Node head = null;
static Node last = null;
static Node current = null;
public static boolean isEmpty() {
return head == null;
}
public static void printList() {
Node ptr = head;
while (ptr != null) {
[Link]("(" + [Link] + "," + [Link] + ") ");
ptr = [Link];
}
}
public static void insertFirst(int key, int data) {
Node link = new Node(data, key);
if (isEmpty()) {
last = link;
} else {
[Link] = link;
}
[Link] = head;
head = link;
}
 public static void insertLast(int key, int data) {
Node link = new Node(data, key);
if (isEmpty()) {
last = link;
} else {
[Link] = link;
[Link] = last;
}
last = link;
}

public static void main(String[] args) {

insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertLast(5,40);
insertLast(6,56);
[Link]("\nDoubly Linked List: ");
printList();
}
} Output
Doubly Linked List: (4,1) (3,30) (2,20) (1,10) (5,40) (6,56)

Circular Linked List

Circular Linked List is a variation of Linked list in which the first element points to the last
element and the last element points to the first element. Both Singly Linked List and Doubly
Linked List can be made into a circular linked list.

Singly Linked List as Circular

In singly linked list, the next pointer of the last node points to the first node.
Doubly Linked List as Circular

In doubly linked list, the next pointer of the last node points to the first node and the previous
pointer of the first node points to the last node making the circular in both directions.

As per the above illustration, following are the important points to be considered.

 The last link's next points to the first link of the list in both cases of singly as well as
doubly linked list.
 The first link's previous points to the last of the list in case of doubly linked list.

Basic Operations

Following are the important operations supported by a circular list.

 insert − Inserts an element at the start of the list.

 delete − Deletes an element from the start of the list.
 display − Displays the list.

Insertion Operation

The insertion operation of a circular linked list only inserts the element at the start of the list.
This differs from the usual singly and doubly linked lists as there is no particular starting and
ending points in this list. The insertion is done either at the start or after a particular node (or a
given position) in the list.

Algorithm

1. START
2. Check if the list is empty
3. If the list is empty, add the node and point the head to this node
4. If the list is not empty, link the existing head as the next node to the new node.
5. Make the new node as the new head.
6. END

Example
//Java program for circular link list
import [Link].*;
class Node {
int data;
int key;
Node next;
}
public class Main {
static Node head = null;
static Node current = null;
static boolean isEmpty() {
return head == null;
}
//insert link at the first location
static void insertFirst(int key, int data) {
//create a link
Node link = new Node();
[Link] = key;
[Link] = data;
if (isEmpty()) {
head = link;
[Link] = head;
} else {
//point it to old first node
[Link] = head;
//point first to new first node
head = link;
}
}
//display the list
static void printList() {
Node ptr = head;
[Link]("\n[ ");
//start from the beginning
if (head != null) {
while ([Link] != ptr) {
 [Link]("(" + [Link] + "," + [Link] + ") ");
ptr = [Link];
}
}
[Link](" ]");
}
public static void main(String[] args) {
insertFirst(1, 10);
insertFirst(2, 20);
insertFirst(3, 30);
insertFirst(4, 1);
insertFirst(5, 40);
insertFirst(6, 56);
[Link]("Circular Linked List: ");
//print list
printList();
}
}
Output
Circular Linked List: [ (6,56) (5,40) (4,1) (3,30) (2,20) ]

Deletion Operation

The Deletion operation in a Circular linked list removes a certain node from the list. The deletion
operation in this type of lists can be done at the beginning, or a given position, or at the ending.

Algorithm

1. START
2. If the list is empty, then the program is returned.
3. If the list is not empty, we traverse the list using a current pointer that is set to the head pointer
and create another pointer previous that points to the last node.
4. Suppose the list has only one node, the node is deleted by setting the head pointer to NULL.
5. If the list has more than one node and the first node is to be deleted, the head is set to the next
node and the previous is linked to the new head.
6. If the node to be deleted is the last node, link the preceding node of the last node to head node.
7. If the node is neither first nor last, remove the node by linking its preceding node to its
succeeding node.
8. END

Example

//Java program for circular linked list

import [Link].*;
public class Main {
static class Node {
int data;
int key;
Node next;
}
static Node head = null;
static Node current = null;

static boolean isEmpty() {

return head == null;
}
//insert link at the first location
static void insertFirst(int key, int data) {
//create a link
Node link = new Node();
[Link] = key;
[Link] = data;
if (isEmpty()) {
head = link;
[Link] = head;
} else {
//point it to old first node
[Link] = head;
//point first to new first node
head = link;
}
}
//delete first item
static Node deleteFirst() {
 //save reference to first link
Node tempLink = head;
if ([Link] == head) {
head = null;
return tempLink;
}
//mark next to first link as first
head = [Link];
//return the deleted link
return tempLink;
}
//display the list
static void printList() {
Node ptr = head;
//start from the beginning
if (head != null) {
while ([Link] != ptr) {
[Link]("(%d,%d) ", [Link], [Link]);
ptr = [Link];
}
}
}
public static void main(String[] args) {
insertFirst(1, 10);
insertFirst(2, 20);
insertFirst(3, 30);
insertFirst(4, 1);
insertFirst(5, 40);
insertFirst(6, 56);
[Link]("Circular Linked List: ");
//print list
printList();
deleteFirst();
}
} Output
Circular Linked List: (6,56) (5,40) (4,1) (3,30) (2,20)
List after deleting the first item: (5,40) (4,1) (3,30) (2,20)

Display List Operation

The Display List operation visits every node in the list and prints them all in the output.

Algorithm

1. START
2. Walk through all the nodes of the list and print them
3. END

Example

//Java program for circular link list

import [Link].*;
class Node {
int data;
int key;
Node next;
}
public class Main {
static Node head = null;
static Node current = null;
static boolean isEmpty() {
return head == null;
}
//insert link at the first location
static void insertFirst(int key, int data) {
//create a link
Node link = new Node();
[Link] = key;
[Link] = data;
if (isEmpty()) {
head = link;
[Link] = head;
} else {
//point it to old first node
 [Link] = head;
//point first to new first node
head = link;
}
}
//display the list
static void printList() {
Node ptr = head;
[Link]("\n[ ");
//start from the beginning
if (head != null) {
while ([Link] != ptr) {
[Link]("(" + [Link] + "," + [Link] + ") ");
ptr = [Link];
}
}
[Link](" ]");
}
public static void main(String[] args) {
insertFirst(1, 10);
insertFirst(2, 20);
insertFirst(3, 30);
insertFirst(4, 1);
insertFirst(5, 40);
insertFirst(6, 56);
[Link]("Circular Linked List: ");
//print list
printList();
}
}
Output
Circular Linked List: [ (6,56) (5,40) (4,1) (3,30) (2,20) ]
 Stack

A stack is an Abstract Data Type (ADT), that is popularly used in most programming languages.
It is named stack because it has the similar operations as the real-world stacks, for example – a
pack of cards or a pile of plates, etc.

The stack follows the LIFO (Last in - First out) structure where the last element inserted would
be the first element deleted.

Stack Representation

A Stack ADT allows all data operations at one end only. At any given time, we can only access
the top element of a stack.

The following diagram depicts a stack and its operations −

A stack can be implemented by means of Array, Structure, Pointer, and Linked List. Stack can
either be a fixed size one or it may have a sense of dynamic resizing. Here, we are going to
implement stack using arrays, which makes it a fixed size stack implementation.
Basic Operations on Stacks

Stack operations usually are performed for initialization, usage and, de-initialization of the stack
ADT.

The most fundamental operations in the stack ADT include: push(), pop(), peek(), isFull(),
isEmpty(). These are all built-in operations to carry out data manipulation and to check the status
of the stack.

Stack uses pointers that always point to the topmost element within the stack, hence called as
the top pointer.

Insertion: push()

push() is an operation that inserts elements into the stack. The following is an algorithm that
describes the push() operation in a simpler way.

Algorithm

1 − Checks if the stack is full.

2 − If the stack is full, produces an error and exit.

3 − If the stack is not full, increments top to point next empty space.

4 − Adds data element to the stack location, where top is pointing.

5 − Returns success.

Example

import [Link].*;

import [Link].*; // util imports the stack class

public class StackExample {

public static void main (String[] args) {

Stack<Integer> stk = new Stack<Integer>();

// inserting elements into the stack

[Link](52);
 [Link](19);

[Link](33);

[Link](14);

[Link](6);

[Link]("The stack is: " + stk);

} Output

The stack is: [52, 19, 33, 14, 6]

Note − In Java we have used to built-in method push() to perform this operation.

Deletion: pop()

pop() is a data manipulation operation which removes elements from the stack. The following
pseudo code describes the pop() operation in a simpler way.

Algorithm

1 − Checks if the stack is empty.

2 − If the stack is empty, produces an error and exit.
3 − If the stack is not empty, accesses the data element at which top is pointing.
4 − Decreases the value of top by 1.
5 − Returns success.

Example

import [Link].*;

import [Link].*;

// util imports the stack class

public class StackExample {

public static void main (String[] args) {

 Stack<Integer> stk = new Stack<Integer>();

// Inserting elements into the stack

[Link](52);

[Link](19);

[Link](33);

[Link](14);

[Link](6);

[Link]("The stack is: " + stk);

// Deletion from the stack

[Link]("\nThe popped element is: ");

Integer n = (Integer) [Link]();

[Link](n);

} Output

The stack is: [52, 19, 33, 14, 6]

The popped element is: 6
Note − In Java we are using the built-in method pop().

peek()

The peek() is an operation retrieves the topmost element within the stack, without deleting it.
This operation is used to check the status of the stack with the help of the top pointer.

Algorithm

1. START
2. return the element at the top of the stack
3. END

Example

import [Link].*;

import [Link].*;

// util imports the stack class

public class StackExample {

public static void main (String[] args) {

Stack<Integer> stk = new Stack<Integer>();

// inserting elements into the stack

[Link](52);

[Link](19);

[Link](33);

[Link](14);

[Link](6);

[Link]("The stack is: " + stk);

Integer pos = (Integer) [Link]();

[Link]("\nThe element found is " + pos);

} Output

The stack is: [52, 19, 33, 14, 6]

The element found is 6
isFull()

isFull() operation checks whether the stack is full. This operation is used to check the status of
the stack with the help of top pointer.

Algorithm

1. START
2. If the size of the stack is equal to the top position of the stack, the stack is full. Return 1.
3. Otherwise, return 0.
4. END

Example

import [Link].*;

public class StackExample {

private int arr[];

private int top;

private int capacity;

StackExample(int size) {

arr = new int[size];

capacity = size;

top = -1;

public boolean isEmpty() {

return top == -1;

public boolean isFull() {

return top == capacity - 1;

}
 public void push(int key) {

if (isFull()) {

[Link]("Stack is Full\n");

return;

arr[++top] = key;

public static void main (String[] args) {

StackExample stk = new StackExample(5);

[Link](1); // inserting 1 in the stack

[Link](2);

[Link](3);

[Link](4);

[Link](5);

[Link]("Stack Full? " + [Link]());

} Output

Stack Full? true

isEmpty()

The isEmpty() operation verifies whether the stack is empty. This operation is used to check the
status of the stack with the help of top pointer.

Algorithm

1. START
2. If the top value is -1, the stack is empty. Return 1.
3. Otherwise, return 0.
4. END

Example

import [Link].*;

import [Link].*; // util imports the stack class

public class StackExample {

public static void main (String[] args) {

Stack<Integer> stk = new Stack<Integer>();

// Inserting elements into the stack

[Link](52);

[Link](19);

[Link](33);

[Link](14);

[Link](6);

[Link]("Stack empty? "+ [Link]());

} Output

Stack empty? false

Queue

Queue, like Stack, is also an abstract data structure. The thing that makes queue different from
stack is that a queue is open at both its ends. Hence, it follows FIFO (First-In-First-Out)
structure, i.e. the data item inserted first will also be accessed first. The data is inserted into the
queue through one end and deleted from it using the other end.
A real-world example of queue can be a single-lane one-way road, where the vehicle enters first,
exits first. More real-world examples can be seen as queues at the ticket windows and bus-stops.

Representation of Queues

Similar to the stack ADT, a queue ADT can also be implemented using arrays, linked lists, or
pointers. As a small example in this tutorial, we implement queues using a one-dimensional
array.

Basic Operations

Queue operations also include initialization of a queue, usage and permanently deleting the data
from the memory.

The most fundamental operations in the queue ADT include: enqueue(), dequeue(), peek(),
isFull(), isEmpty(). These are all built-in operations to carry out data manipulation and to check
the status of the queue.

Queue uses two pointers − front and rear. The front pointer accesses the data from the front end
(helping in enqueueing) while the rear pointer accesses data from the rear end (helping in
dequeuing).

Insertion operation: enqueue()

The enqueue() is a data manipulation operation that is used to insert elements into the stack. The
following algorithm describes the enqueue() operation in a simpler way.

Algorithm

1 − START
2 – Check if the queue is full.
3 − If the queue is full, produce overflow error and exit.
4 − If the queue is not full, increment rear pointer to point the next empty space.
5 − Add data element to the queue location, where the rear is pointing.
6 − return success.
7 – END

Example

import [Link];

import [Link];

public class QueueExample {

public static void main(String[] args) {

Queue<Integer> q = new LinkedList<>();

[Link](6);

[Link](1);

[Link](8);

[Link](4);

[Link](7);

[Link]("The queue is: " + q);

} Output

The queue is: [6, 1, 8, 4, 7]

Deletion Operation: dequeue()

The dequeue() is a data manipulation operation that is used to remove elements from the stack.
The following algorithm describes the dequeue() operation in a simpler way.

Algorithm

1 – START
2 − Check if the queue is empty.
3 − If the queue is empty, produce underflow error and exit.
4 − If the queue is not empty, access the data where front is pointing.
5 − Increment front pointer to point to the next available data element.
6 − Return success.
7 – END

Example

import [Link];

import [Link];

public class QueueExample {

public static void main(String[] args) {

Queue<Integer> q = new LinkedList<>();

[Link](6);

[Link](1);

[Link](8);

[Link](4);

[Link](7);

[Link]("The queue is: " + q);

int n = [Link]();

[Link]("The element deleted is: " + n);

[Link]("Queue after deletion: " + q);

}
} Output

The queue is: [6, 1, 8, 4, 7]

The element deleted is: 6
Queue after deletion: [1, 8, 4, 7]

The peek() Operation

The peek() is an operation which is used to retrieve the frontmost element in the queue, without
deleting it. This operation is used to check the status of the queue with the help of the pointer.

Algorithm

1 – START
2 – Return the element at the front of the queue
3 – END

Example

import [Link];

import [Link];

public class QueueExample {

public static void main(String[] args) {

Queue<Integer> q = new LinkedList<>();

[Link](6);

[Link](1);

[Link](8);

[Link](4);

[Link](7);

[Link]("The queue is: " + q);

}
Output

The queue is: [6, 1, 8, 4, 7]

The isFull() Operation

The isFull() operation verifies whether the stack is full.

Algorithm

1 – START
2 – If the count of queue elements equals the queue size, return true
3 – Otherwise, return false
4 – END

Example

import [Link].*;

public class QueueExample {

private int intArray[];

private int front;

private int rear;

private int itemCount;

private int MAX;

QueueExample(int size) {

intArray = new int[size];

front = 0;

rear = -1;

MAX = size;

itemCount = 0;

}
 public boolean isFull() {

return itemCount == MAX;

public void insert(int key) {

if(!isFull()) {

if(rear == MAX-1) {

rear = -1;

intArray[++rear] = key;

itemCount++;

public static void main (String[] args) {

QueueExample q = new QueueExample(5);

[Link](1); // inserting 1 in the stack

[Link](2);

[Link](3);

[Link](4);

[Link](5);

[Link]("Stack Full? " + [Link]());

} Output

Stack Full? true

The isEmpty() operation

The isEmpty() operation verifies whether the stack is empty. This operation is used to check the
status of the stack with the help of top pointer.

Algorithm

1 – START
2 – If the count of queue elements equals zero, return true
3 – Otherwise, return false
4 – END

Example

import [Link].*;

public class QueueExample {

private int intArray[];

private int front;

private int rear;

private int itemCount;

private int MAX;

QueueExample(int size) {

intArray = new int[size];

front = 0;

rear = -1;

MAX = size;

itemCount = 0;

public boolean isEmpty() {

return itemCount == 0;
 }

public static void main (String[] args) {

QueueExample q = new QueueExample(5);

[Link]("Stack Empty? " + [Link]());

Output
Stack Empty? true