Data Structures And Algorithms(Day #2)

#tutorial #java #beginners #todayilearned

Hello There, My Gorgeous Friend On The Internet

This is the second part of my Data Structures and Algorithms series.
Check out First article For Introduction to Data Structures and Arrays.

In this post, First we'll talk about Linked List Data Structure, Why should we use it and simple java programs implementing Linked List.

Also, Check out my GitHub repository for all the programs:

jamesshah / Data-Structures-And-Algorithms

Data Structures And Algorithms For Learning Purpose.

Linked List

So, the very first question that comes to my mind is:

What Is A Linked List?

A linked list is a particular list of some data elements linked to one other. In this every element point to the next element which represents the logical ordering.
Each element is called a 'node', which has two parts. DATA part which stores the information and POINTER which points to the next element.
The first 'node' of the Linked List is called "head".
POINTER field of the last node is "null", which means it doesn't point to any element.
We can access a linked list using the address of the head node and then it gives us the address of the next node and so on. It's like a treasure hunt, you go to the first guy and you get the location of the next guy.

Why Linked List?

And the answer is that Linked List is better than Arrays in terms of Space Complexity and in terms of Time Complexity.
In arrays, we must know the maximum size of the array in advance because arrays are contiguous collection of elements. By contiguous, we mean the elements of the array are adjacent to one another in memory with no gaps between them.
And thus, if we want to enter more elements than the size of an array, we need to create a new array of bigger size and then copy all the elements in this new array. This process is very time consuming and thus, not practical.
Memory utilization is inefficient in the Array. Conversely, memory utilization is efficient in the Linked List.

Types Of Linked List

Singly Linked List
Doubly Linked List
Circular Linked List

Singly Linked List

Singly linked list is a basic linked list type. A singly Linked list is a collection of nodes linked together in a sequential way where each node of the singly linked list contains a data field and an address field that contains the reference of the next node.

Here is a simple program implementing a Linked List in Java.

	//Implementing Singly Linked List in Java

	class LinkedList{
	Node head; //Reference to the Node class to create head node of the list.

	//Node class to create nodes. here we make static class so that main method
	//can recoginze it.
	static class Node{
	int data;
	Node next;

	//Constructor
	Node(int d){
	data = d;
	next = null;
	}
	}

	//To print the data of all the nodes of the list.
	public void printList(){
	Node tempNode = head;
	while (tempNode!= null) {
	System.out.print(tempNode.data + " " );
	tempNode = tempNode.next;
	}
	}

	public static void main(String[] args) {
	LinkedList list = new LinkedList();
	list.head = new Node(5);
	Node secondNode = new Node(6);
	Node thirdNode = new Node(7);

	//Connecting nodes of the list by adding Reference to the next node.
	list.head.next = secondNode;
	secondNode.next = thirdNode;

	//Printing data of all the nodes of the list.
	list.printList();
	}
	}

view raw LinkedList.java hosted with ❤ by GitHub

Insertion Of Nodes In Linked List

There is a total of three possibilities of inserting a node in the linked list as below.

Insertion of a node at the start of the linked list
Insertion of a node at the end of the linked list
Insertion of a node at a specific location in the linked list(i.e. after a given node.)

Here is a program that shows all three insertions in a linked list.

	//Insertion operation in a Linked List.
	//There are three possibilities for Insertion in a Linked List.
	//1- Insertion at the start of the list.
	//2- Insertion at the end of the list.
	//3- Insertion after a specific node.

	//Insertion at the start of the list.

	public void insertionAtStart(int new_node_data){
	Node new_node = new Node(new_node_data);
	//Creating a new node and adding data into it.
	//Adding reference of head node into new node.
	new_node.next = head;
	//And now new node becomes the head of the list.
	head = new_node;
	}
	}

	//Insertion at the end of the list.

	public void insertionAtEnd(int new_node_data){
	//Creating a new node and adding data into it.
	Node new_node = new Node(new_node_data);

	//Check if there the list is empty.
	if(head == null){
	head = new_node;
	}
	//else traverse through the whole list, untill we reach the last node.
	else{
	Node last = head;
	while(last.next != null){
	last = last.next;
	}
	last.next = new_node;
	}
	}

	//Insertion after a specific node.

	//Here we pass data of new node as well as previous node - after which the new
	//node is to be inserted.
	public void insertionAfterSpecificNode(Node prev_node, int new_node_data){
	if(prev_node == null){
	System.out.println("Error -- Given Previous Node is Null.");
	return ;
	}
	Node new_node = new Node(new_node_data);
	new_node.next = prev_node.next;
	prev_node.next = new_node;
	}

view raw LinkedList_Insertion.java hosted with ❤ by GitHub

And now we'll see a full program with the implementation of the Linked List and also all possibilities of insertion of the node.

	//Implementing Linked List with all three insertion possibilities in Java

	class LinkedList{
	Node head; //Reference to the Node class to create head node of the list.

	//Node class to create nodes. here we make static class so that main method
	//can recoginze it.
	static class Node{
	int data;
	Node next;

	//Constructor
	Node(int d){
	data = d;
	next = null;
	}
	}

	//Insertion at the start of the list.

	public void insertionAtStart(int new_node_data){
	Node new_node = new Node(new_node_data);
	//Creating a new node and adding data into it.
	//Adding reference of head node into new node.
	new_node.next = head;
	//And now new node becomes the head of the list.
	head = new_node;
	}

	//Insertion at the end of the list.

	public void insertionAtEnd(int new_node_data){
	//Creating a new node and adding data into it.
	Node new_node = new Node(new_node_data);

	//Check if there the list is empty.
	if(head == null){
	head = new_node;
	}
	//else traverse through the whole list, untill we reach the last node.
	else{
	Node last = head;
	while(last.next != null){
	last = last.next;
	}
	last.next = new_node;
	}
	}

	//Insertion after a specific node.

	//Here we pass data of new node as well as previous node - after which the new
	//node is to be inserted.
	public void insertionAfterSpecificNode(Node prev_node, int new_node_data){
	if(prev_node == null){
	System.out.println("Error -- Given Previous Node is Null.");
	return ;
	}
	Node new_node = new Node(new_node_data);
	new_node.next = prev_node.next;
	prev_node.next = new_node;
	}

	//To print the data of all the nodes of the list.
	public void printList(){
	Node tempNode = head;
	while (tempNode!= null) {
	System.out.print(tempNode.data + " " );
	tempNode = tempNode.next;
	}
	}

	public static void main(String[] args) {
	LinkedList list = new LinkedList();
	//Creating a head node for the list.
	list.head = new Node(5);
	//Inserting a new node at the end of the list.
	list.insertionAtEnd(10);
	//Insertinf a new node at the start of the list.
	list.insertionAtStart(15);
	//inserting a new node after second node in the list.
	list.insertionAfterSpecificNode(list.head.next,7);

	//Printing data of all the nodes of the list.
	list.printList();
	}

	}