403 - Java Programming Language
Unit-5 : Data Structure Implementation using Java Class
Concepts of Linked List
The Linked Lists in Java is important type of data structure.
A Linked List is a collection of similar types of data elements, called nodes, which point to
the next following nodes by means of pointers.
Need for Linked lists:
Linked lists overcome the drawbacks of arrays because in linked lists there is no need to
define the number of elements before using it, therefore the allocation or deallocation of
memory can be during the processing according to the requirement, making the insertions
and deletions much easier and simpler.
How the LinkedList works?
The LinkedList stores its items in "containers." The list has a link to the first container and
each container has a link to the next container in the list.
To add an element to the list, the element is placed into a new container and that container
is linked to one of the other containers in the list.
Types of Linked Lists
Singly Linked List
A singly-linked list is a linked list that stores data and the reference to the next node or a null
value.
Singly-linked lists are also known as one-way lists as they contain a node with a single
pointer pointing to the next node in the sequence.
There is a START pointer that stores the very first address of the linked list also called the
Head.
The Next pointer of the last or end node stores NULL value, which points to the last node of
the list which does not point to any other node.
In Java, LinkedList can be represented as a class and a Node as a separate class. The
LinkedList class contains a reference of Node class type.
o Each element in the list is called a node.
o A node is made of two parts, namely data and pointer.
o Data is the data stored in the data part and the pointer is the next node in the
list.
o The first node in the list is referred to as the head of the list.
o The last node in the list is the tail, and it points to NULL.
Each node in the list can be accessed linearly by traversing through the list from head to tail.
The following operations can be performed on a Singly Linked List:
1|P ag e C.B. Patel Computer College
403 - Java Programming Language
o Adding element at specific position
o Adding element at the start
o Adding element at the end
o Removing element from specific Node
o Removing First element
o Remove Last Element
o Traverse all the elements, etc
import java.lang.*;
class LinkedList
{
Node head;
// Node Class
class Node
{
int data;
Node next;
Node(int x)
{
data = x;
next = null;
}
}
public Node insertBeginning(int data)
{
Node newNode = new Node(data);
newNode.next = head;
head = newNode;
return head;
}
public void insertEnd(int data)
{
Node newNode = new Node(data);
if(head==null)
{
head = newNode;
return;
}
Node temp = head;
while(temp.next!=null)
temp = temp.next;
temp.next = newNode;
}
public void insertAfter(int n,int data)
{
int size = calcSize(head);
2|P ag e C.B. Patel Computer College
403 - Java Programming Language
// Can only insert after 1st position
// Can't insert if position to insert is greater than size of Linked List
if(n < 1 || n > size)
{
System.out.println("Can't insert\n");
}
else
{
Node newNode = new Node(data);
// required to traverse
Node temp = head;
// traverse to the nth node
while(--n > 0)
temp=temp.next;
newNode.next= temp.next;
temp.next = newNode;
}
}
public void deleteStart()
{
if (head == null){
System.out.println("List is empty, not possible to delete");
return;
}
System.out.println("Deleted: " + head.data);
// move head to next node
head = head.next;
}
public void deleteLast()
{
if (head == null){
System.out.println("List is empty, not possible to delete");
return;
}
// if LL has only one node
if(head.next == null)
{
System.out.println("Deleted: " + head.data);
head = head.next;
}
Node previous = null;
Node temp = head;
// else traverse to the last node
while (temp.next != null)
3|P ag e C.B. Patel Computer College
403 - Java Programming Language
{
// store previous link node as we need to change its next val
previous = temp;
temp = temp.next;
}
// Curr assign 2nd last node's next to Null
System.out.println("Deleted: " + temp.data);
previous.next = null;
// 2nd last now becomes the last node
}
public void deleteNthNode(int n)
{
int len = calcSize(head);
if(n < 1 || n > len)
{
System.out.println("Can't delete\n");
}
else
{
if(n == 1)
{
// head has to be deleted
System.out.println("Deleted: " + head.data);
head = head.next;
return;
}
// required to traverse
Node temp = head;
Node previous = null;
// traverse to the nth node
while(--n > 0) {
previous = temp;
temp = temp.next;
}
// assigned next node of the previous node to nth node's next
previous.next = temp.next;
System.out.println("Deleted: " + temp.data);
}
}
public void display()
{
Node node = head;
//as linked list will end when Node reaches Null
while(node!=null)
{
System.out.print(node.data + " ");
4|P ag e C.B. Patel Computer College
403 - Java Programming Language
node = node.next;
}
System.out.println();
}
public int calcSize(Node node){
int size = 0;
while(node!=null){
node = node.next;
size++;
}
return size;
}
}
class Main{
public static void main(String args[])
{
LinkedList listObj = new LinkedList();
listObj.insertBeginning(15);
listObj.insertBeginning(10);
listObj.insertBeginning(5);
listObj.display();
listObj.insertEnd(20);
listObj.insertEnd(25);
listObj.insertEnd(30);
listObj.insertEnd(35);
listObj.display();
listObj.insertAfter(3,100);
listObj.display();
listObj.deleteLast();
listObj.display();
listObj.deleteStart();
listObj.display();
listObj.deleteNthNode(3);
listObj.display();
}
}
LinkedList Class
The LinkedList class, just like the ArrayList, is a collection that can hold numerous items of
the same type. Here the elements are not stored in contiguous locations and each element
is a separate object with a data part and address part.
5|P ag e C.B. Patel Computer College
403 - Java Programming Language
Each element is known as a node and is linked using pointers and addresses.
The LinkedList class implements the List and Deque interfaces and inherits the AbstractList
class.
LinkedList is a part of the Collection framework present in java.util package.
Constructors in the LinkedList:
In order to create a LinkedList, we need to create an object of the LinkedList class.
The LinkedList class consists of various constructors that allow the possible creation of the
list.
LinkedList(): This constructor is used to create an empty linked list. If we wish to create an
empty LinkedList with the name linkList, then, it can be created as:
Syntax: LinkedList<type> linkedList = new LinkedList<>();
For example, LinkedList<Integer> l_list = new LinkedList<>();
This will create an empty linked list named l_list of integer type.
LinkedList(Collection C): This constructor is used to create an ordered list that contains all
the elements of a specified collection, as returned by the collection’s iterator. If we wish to
create a LinkedList with the name linkList, then, it can be created as:
LinkedList<type> linkedList = new LinkedList<>(Collection c);
LinkedList class provides API that supports various methods to manipulate the Linked list.
Methods of LinkedList for Inserting Nodes
1. add():
Adding at the end - void add(Object Element)
This method appends the specified element to the end of this list. This function accepts a
single parameter element as shown in the above syntax.
Adding at specific index - void add(int index, Object element)
This method inserts an element at a specified index in the list.
It shifts the element currently at that position (if any) and any subsequent elements to the
right (will add one to their indices).
o index: The index at which the specified element is to be inserted.
o element: The element which is needed to be inserted.
2. addFirst():
addFirst() method in Java is used to insert a specific element at the beginning of a LinkedList.
void addFirst(Object element)
3. addLast():
addLast() method in Java is used to insert a specific element at the end of a LinkedList.
void addLast(Object element)
Methods of LinkedList for Traversing Nodes
To print the contents or carry out any operations on the elements of the LinkedList, you
need to traverse through its elements.
6|P ag e C.B. Patel Computer College
403 - Java Programming Language
1. get()
The get() method is used to fetch or retrieve an element at a specific index from a
LinkedList.
var = get(int index)
2. getFirst()
getFirst() : This method returns the first element in this list.
var = getFirst()
3. getLast()
getLast() : This method returns the first element in this list.
var = getLast()
Methods of LinkedList for Deleting Nodes
Types of remove() method present inside this class:
1. void remove() - With no arguments inside
It is used to remove an element from a linked list. The element is removed from the
beginning or head of the linked list.
2. void remove(int index) - Passing index as in arguments
It is used to remove an element from a linked list from a specific position or index.
list.remove(4); // Removes element from index 4
3. void remove(Object O) - Passing object as in arguments
It is used to remove any particular element from the linked list.
list.remove(10); // Removes the element 10 from the list
4. <type> removeFirst() – With no arguments
removeFirst() method is used to remove the first element from a linked list. This function
also returns the first element after removing it.
var = removeFirst()
Other methods of LinkedList Class
1. list.size():
size() method is used to get the size of the Linked list or the number of elements present in
the linked list.
2. list.toString():
This method returns a string containing all of the elements in this list in proper sequence
(from first to the last element), each element is separated by commas and the String is
enclosed in square brackets.
7|P ag e C.B. Patel Computer College
403 - Java Programming Language
3. list.set(int index, Object element):
set() method is used to replace any particular element in the linked list created using the
LinkedList class with another element.
This can be done by specifying the position of the element to be replaced and the new
element in the parameter of the set() method.
LinkedList.set(int index, Object element)
Return Value: The method returns the previous value from the linked list that is replaced
with the new value.
Sample Program implementing the LinkedList Class Methods
8|P ag e C.B. Patel Computer College
403 - Java Programming Language
Advantages of Linked List
The linked list is a dynamic data structure. We can allocate and de-allocate the memory at
run-time itself.
The node can be easily inserted or deleted using the insertion and deletion function.
The linked list makes good use of memory. Because we don't have to allocate memory
ahead of time.
It has an extremely rapid access time and can be accessed at a specific time without any
memory overhead.
Linear data structures like stack and the queue can be easily used linked list.
Disadvantages of Linked List
As each node of the linked list points to a pointer, it requires more memory to store the
elements than an array.
Traversing the nodes of a linked list is quite tough. We won't be able to access any node at
random in this case (As we do in the array by index.)
In a linked list, reverse traversing is harder since the pointer demands extra memory.
Circular Singly Linked List
A circular singly linked list is a linear data structure, in which the elements are stored in the
form of a node. Each node contains two sub-elements. A data part that stores the value of
the element and the next part that stores the link to the next node
The first node also known as HEAD is always used as a reference to traverse the list.
The last node points to HEAD. A circular singly linked list can be visualized as a chain of
nodes, where every node points to the next node. Along with this, next of the last node is
linked to the head node.
In the Circular Linked List, all the nodes align to form a circle.
With this simple change, we gain some benefits:
o Any node in the circular linked list can be a starting point
o Consequently, the whole list can be traversed starting from any node
o Since the last node of the circular linked list has the pointer to the first node, it's
easy to perform enqueue and dequeue operations
o Circular linked lists are useful in implementing a circular queue.
Insert at Beginning of List
IF Head==Null
o Head -> newNode
o Tail -> newNode
o newNode->next = Head
o EXIT
9|P ag e C.B. Patel Computer College
403 - Java Programming Language
ELSE
o Node Temp = head
o newNode->next = Temp
o head = newNode
o tail->next = Head
o EXIT
class CircularLinkedList {
//Node definition for circular linked list
public class Node{
int data;
Node next;
public Node(int data) {
this.data = data;
}
}
//Initially head and tail pointers point to null
public Node head = null;
public Node tail = null;
//add new node to the circular linked list
public void add(int data){
//Create new node
Node newNode = new Node(data);
//check if list is empty
if(head == null) {
//head and tail point to same node if list is empty
head = newNode;
tail = newNode;
newNode.next = head;
}
else {
//tail points to new node if list is not
empty
tail.next = newNode;
//New node becomes new tail.
tail = newNode;
//tail points back to head
tail.next = head;
}
}
//Display the nodes in circular linked list
public void displayList() {
Node current = head;
if(head == null) {
System.out.println("The List is empty");
10 | P a g e C.B. Patel Computer College
403 - Java Programming Language
}
else {
System.out.println("Circular linked list
nodes: ");
do{
//Print each node of the linked list
System.out.print(current.data + " ");
current = current.next;
}while(current != head);
System.out.println();
}
}
}
class Main{
public static void main(String[] args) {
//create a CircularLinkedList object
CircularLinkedList c_list = new
CircularLinkedList();
//Add data to the list
c_list.add(10);
c_list.add(20);
c_list.add(30);
c_list.add(40);
//Display the nodes in circular linked list
c_list.displayList();
}
}
11 | P a g e C.B. Patel Computer College
