Create Custom Linked List - JAVA with Examples | Tutorials - Scratcharound
What is Linked List -
Like arrays Linked list is a linear data structure, but elements in a linked list are not stored in a contiguous location. Elements in a linked list are linked together with some pointer ie. each element in Linked list has a pointer to the next element(singly linked list). In this article we will create our own custom Linked with some basic operations like insertion, deletion and printing a linked list.
You can easily understand the basic structure of a linked list with the help of below diagram.
It has different nodes, each node has data and pointer to the next node element. The very first node is called Head Node. If there are no more elements in the Linked list then next will be be null.
Simple Linked list in JAVA:
package com.ds.linkedlist;
public class CLinkedList {
Node head;
static class Node{
int data;
Node next;
Node(int d){
data = d;
next = null;
}
}
}
We have created a custom linked list ClinkedList, it has a inner static class Node and can hold integer type data. Node has two member variables int to contain the integer type data and next which will hold the next node of the linked list. ClinkedList has a head member variable which is a Node. Head is the first node of a CLinkedList.
Inserting elements in a LinkedList
We can insert elements insdie a linked list at different positions.
1. Insertion at the beginning of the LinkedList
2. Insertion at the end of the LinkedList 3. Insertion in middle of the LinkedList after some given Node. 1. Inserting at the Beginning of the LinkedList
If we add the element in the beginning of the list, then 'head' variable will refer to the newly created Node and the next of this New Node will refer to the old Head node.
// adds an element in the beginning of list
public void push(int data){
Node n = new Node(data);
if(head == null){
head = n;
return;
}
n.next = this.head;
this.head = n;
}
2. Inserting at the End of the LinkedList
First we have to find out the last element of the LinkedList and then set the new Node as the next of this last node of the LinkedList.
// insert element at the end
public void append(int data){
Node new_node = new Node(data);
if(this.head == null){
head = new_node;
}
Node lastNode = this.head;
while(lastNode.next != null){
lastNode = lastNode.next;
}
lastNode.next = new_node;
}
3. Inserting after a given Node in LinkedList
We will just set the next of the given node to the Newly creater Node.
// insert after a node
public void insertAfter(Node n, int data){
if(n == null){
System.out.println("Previous node cannot be null");
return;
}
Node new_node = new Node(data);
new_node.next = n.next;
n.next = new_node;
}
Delete an element from LinkedList
We will find the previous and next node for the given element. Set next of previous node to the next of deleted node and set next of deleted element to null
// delete an element
public void delete(int data){
Node prevNode = null;
Node temp = head;
if(head!=null && head.data == data){
head = temp.next;
temp = null;
return;
}
while(temp != null && temp.data != data){
prevNode = temp;
temp = temp.next;
}
if(temp==null){
System.out.println("element not found");
return;
}
prevNode.next = temp.next;
temp.next = null;
}
Printing a LinkedList
//print list
public void printList(){
if(head == null){
System.out.println("List is empty");
return;
}
Node pNode = head;
while(pNode != null){
System.out.print(pNode.data+" ");
pNode = pNode.next;
}
}
Count elements of LinkedList
This count function will return the total number of elements in the CLinkedList.
public int count(){
int count = 0;
if(head == null) return count;
Node temp = head;
while(temp!=null){
temp = temp.next;
count += 1;
}
return count;
}
So these were some basic operations we can perform with our Custom Linked List in java. This whole ClinkedList will look something like the code given below:
Custom Linked List Full Code
package com.ds.linkedlist;
public class CLinkedList {
Node head;
static class Node{
int data;
Node next;
Node(int d){
data = d;
next = null;
}
}
// adds an element in the beginning of list
public void push(int data){
Node n = new Node(data);
if(head == null){
head = n;
return;
}
n.next = this.head;
this.head = n;
}
public void insertAfter(Node n, int data){
if(n == null){
System.out.println("Previous node cannot be null");
return;
}
Node new_node = new Node(data);
new_node.next = n.next;
n.next = new_node;
}
public void append(int data){
Node new_node = new Node(data);
if(this.head == null){
head = new_node;
}
Node lastNode = this.head;
while(lastNode.next != null){
lastNode = lastNode.next;
}
lastNode.next = new_node;
}
// delete an element
public void delete(int data){
Node prevNode = null;
Node temp = head;
if(head!=null && head.data == data){
head = temp.next;
temp = null;
return;
}
while(temp != null && temp.data != data){
prevNode = temp;
temp = temp.next;
}
if(temp==null){
System.out.println("element not found");
return;
}
prevNode.next = temp.next;
temp.next = null;
}
public int count(){
int count = 0;
if(head == null) return count;
Node temp = head;
while(temp!=null){
temp = temp.next;
count += 1;
}
return count;
}
//print list
public void printList(){
if(head == null){
System.out.println("List is empty");
return;
}
Node pNode = head;
while(pNode != null){
System.out.print(pNode.data+" ");
pNode = pNode.next;
}
}
}
Now lets try to perform these operations with this CLinkedList
Example 1: Inserting element inside the LinkedList
package com.ds.linkedlist;
import com.ds.linkedlist.CLinkedList.Node;
public class Test {
public static void main(String[] args) {
CLinkedList l = new CLinkedList();
l.head = new Node(1);
l.append(2);
l.append(3);
l.append(4);
l.push(5);
l.insertAfter(l.head, 6);
l.append(7);
l.append(9);
l.printList();
}
}
Above example pushes the element 5 which makes it the head element. Then we have inserted the element 6 after the head element
5 which maked 6 the second element in the list. Output : 5 6 1 2 3 4 7 9
Example 1: Deleting element from the LinkedList
package com.ds.linkedlist;
import com.ds.linkedlist.CLinkedList.Node;
public class Test {
public static void main(String[] args) {
CLinkedList l = new CLinkedList();
l.head = new Node(1);
l.append(2);
l.append(3);
l.append(4);
l.push(5);
l.insertAfter(l.head, 6);
l.append(7);
l.append(9);
l.delete(3);
l.printList();
}
}
Output : 5 6 1 2 4 7 9 Example 1: Count total elements LinkedList
package com.ds.linkedlist;
import com.ds.linkedlist.CLinkedList.Node;
public class Test {
public static void main(String[] args) {
CLinkedList l = new CLinkedList();
l.head = new Node(1);
l.append(2);
l.append(3);
l.append(4);
l.push(5);
l.insertAfter(l.head, 6);
l.append(7);
l.append(9);
System.out.println("Size is "+l.count());
l.delete(3);
System.out.println("Size is "+l.count());
l.printList();
}
}
Output :Size is 8 Size is 7 5 6 1 2 4 7 9
These were some basic operations performed with our Custom Linked list. Now as we have seen the things in action, we can point out some advantages and discadvantages of linked list over Array.
Linked List VS Array
Some advantages of LinkedList over array are that we can easily insert or delete an element in the liked list, whereas if want to delete or insert an element in an Array, we will have to shift all other next elements in the Array, which is a complex process and time consuming.Another advantage of LinkedlIst over array is that its size is not fixed like arrays, we can insert more elements inside it without declaring its size.
There are also some drawbacks of using LinkeList, like if we need extra memory space for the pointer. Also we cannot access elements randomly , we will have to start from the head to get the desired element.
So these were some advantages and disadvantages of LinkedList over Arrays. If you have any questions please feel free to write in the comments below.
What is Linked List -
Like arrays Linked list is a linear data structure, but elements in a linked list are not stored in a contiguous location. Elements in a linked list are linked together with some pointer ie. each element in Linked list has a pointer to the next element(singly linked list). In this article we will create our own custom Linked with some basic operations like insertion, deletion and printing a linked list.
You can easily understand the basic structure of a linked list with the help of below diagram.
It has different nodes, each node has data and pointer to the next node element. The very first node is called Head Node. If there are no more elements in the Linked list then next will be be null.
Simple Linked list in JAVA:
package com.ds.linkedlist;
public class CLinkedList {
Node head;
static class Node{
int data;
Node next;
Node(int d){
data = d;
next = null;
}
}
}
We have created a custom linked list ClinkedList, it has a inner static class Node and can hold integer type data. Node has two member variables int to contain the integer type data and next which will hold the next node of the linked list. ClinkedList has a head member variable which is a Node. Head is the first node of a CLinkedList.
Inserting elements in a LinkedList
We can insert elements insdie a linked list at different positions.
1. Insertion at the beginning of the LinkedList
2. Insertion at the end of the LinkedList 3. Insertion in middle of the LinkedList after some given Node. 1. Inserting at the Beginning of the LinkedList
If we add the element in the beginning of the list, then 'head' variable will refer to the newly created Node and the next of this New Node will refer to the old Head node.
// adds an element in the beginning of list
public void push(int data){
Node n = new Node(data);
if(head == null){
head = n;
return;
}
n.next = this.head;
this.head = n;
}
2. Inserting at the End of the LinkedList
First we have to find out the last element of the LinkedList and then set the new Node as the next of this last node of the LinkedList.
// insert element at the end
public void append(int data){
Node new_node = new Node(data);
if(this.head == null){
head = new_node;
}
Node lastNode = this.head;
while(lastNode.next != null){
lastNode = lastNode.next;
}
lastNode.next = new_node;
}
3. Inserting after a given Node in LinkedList
We will just set the next of the given node to the Newly creater Node.
// insert after a node
public void insertAfter(Node n, int data){
if(n == null){
System.out.println("Previous node cannot be null");
return;
}
Node new_node = new Node(data);
new_node.next = n.next;
n.next = new_node;
}
Delete an element from LinkedList
We will find the previous and next node for the given element. Set next of previous node to the next of deleted node and set next of deleted element to null
// delete an element
public void delete(int data){
Node prevNode = null;
Node temp = head;
if(head!=null && head.data == data){
head = temp.next;
temp = null;
return;
}
while(temp != null && temp.data != data){
prevNode = temp;
temp = temp.next;
}
if(temp==null){
System.out.println("element not found");
return;
}
prevNode.next = temp.next;
temp.next = null;
}
Printing a LinkedList
//print list
public void printList(){
if(head == null){
System.out.println("List is empty");
return;
}
Node pNode = head;
while(pNode != null){
System.out.print(pNode.data+" ");
pNode = pNode.next;
}
}
Count elements of LinkedList
This count function will return the total number of elements in the CLinkedList.
public int count(){
int count = 0;
if(head == null) return count;
Node temp = head;
while(temp!=null){
temp = temp.next;
count += 1;
}
return count;
}
So these were some basic operations we can perform with our Custom Linked List in java. This whole ClinkedList will look something like the code given below:
Custom Linked List Full Code
package com.ds.linkedlist;
public class CLinkedList {
Node head;
static class Node{
int data;
Node next;
Node(int d){
data = d;
next = null;
}
}
// adds an element in the beginning of list
public void push(int data){
Node n = new Node(data);
if(head == null){
head = n;
return;
}
n.next = this.head;
this.head = n;
}
public void insertAfter(Node n, int data){
if(n == null){
System.out.println("Previous node cannot be null");
return;
}
Node new_node = new Node(data);
new_node.next = n.next;
n.next = new_node;
}
public void append(int data){
Node new_node = new Node(data);
if(this.head == null){
head = new_node;
}
Node lastNode = this.head;
while(lastNode.next != null){
lastNode = lastNode.next;
}
lastNode.next = new_node;
}
// delete an element
public void delete(int data){
Node prevNode = null;
Node temp = head;
if(head!=null && head.data == data){
head = temp.next;
temp = null;
return;
}
while(temp != null && temp.data != data){
prevNode = temp;
temp = temp.next;
}
if(temp==null){
System.out.println("element not found");
return;
}
prevNode.next = temp.next;
temp.next = null;
}
public int count(){
int count = 0;
if(head == null) return count;
Node temp = head;
while(temp!=null){
temp = temp.next;
count += 1;
}
return count;
}
//print list
public void printList(){
if(head == null){
System.out.println("List is empty");
return;
}
Node pNode = head;
while(pNode != null){
System.out.print(pNode.data+" ");
pNode = pNode.next;
}
}
}
Now lets try to perform these operations with this CLinkedList
Example 1: Inserting element inside the LinkedList
package com.ds.linkedlist;
import com.ds.linkedlist.CLinkedList.Node;
public class Test {
public static void main(String[] args) {
CLinkedList l = new CLinkedList();
l.head = new Node(1);
l.append(2);
l.append(3);
l.append(4);
l.push(5);
l.insertAfter(l.head, 6);
l.append(7);
l.append(9);
l.printList();
}
}
Above example pushes the element 5 which makes it the head element. Then we have inserted the element 6 after the head element
5 which maked 6 the second element in the list. Output : 5 6 1 2 3 4 7 9
Example 1: Deleting element from the LinkedList
package com.ds.linkedlist;
import com.ds.linkedlist.CLinkedList.Node;
public class Test {
public static void main(String[] args) {
CLinkedList l = new CLinkedList();
l.head = new Node(1);
l.append(2);
l.append(3);
l.append(4);
l.push(5);
l.insertAfter(l.head, 6);
l.append(7);
l.append(9);
l.delete(3);
l.printList();
}
}
Output : 5 6 1 2 4 7 9 Example 1: Count total elements LinkedList
package com.ds.linkedlist;
import com.ds.linkedlist.CLinkedList.Node;
public class Test {
public static void main(String[] args) {
CLinkedList l = new CLinkedList();
l.head = new Node(1);
l.append(2);
l.append(3);
l.append(4);
l.push(5);
l.insertAfter(l.head, 6);
l.append(7);
l.append(9);
System.out.println("Size is "+l.count());
l.delete(3);
System.out.println("Size is "+l.count());
l.printList();
}
}
Output :Size is 8 Size is 7 5 6 1 2 4 7 9
These were some basic operations performed with our Custom Linked list. Now as we have seen the things in action, we can point out some advantages and discadvantages of linked list over Array.
Linked List VS Array
Some advantages of LinkedList over array are that we can easily insert or delete an element in the liked list, whereas if want to delete or insert an element in an Array, we will have to shift all other next elements in the Array, which is a complex process and time consuming.Another advantage of LinkedlIst over array is that its size is not fixed like arrays, we can insert more elements inside it without declaring its size.
There are also some drawbacks of using LinkeList, like if we need extra memory space for the pointer. Also we cannot access elements randomly , we will have to start from the head to get the desired element.
So these were some advantages and disadvantages of LinkedList over Arrays. If you have any questions please feel free to write in the comments below.
No comments :
Post a Comment