In this post we’ll see an implementation of Linked List in Java. Operations covered in this singly Linked List Java implementation are as per the given table of contents-
Linked List data structure
Linked list data structure though linear in nature doesn’t store its node in contiguous memory location like array. In Linked list nodes are linked by each node holding reference to the next node.
Following image shows the nodes in the Linked List and how nodes are linked.
Java program for Linked List
For representing nodes of the linked list a separate class is used which, apart from the data, also holds a reference to itself.
class Node{
//data
int i;
// Reference to next node
Node next;
}
Java implementation of linked list given here is a double ended list where we have two references head and tail; head always points to the first node and the tail is a reference to the last node.
Insertion in linked list
For insertion there are three scenarios insert at the beginning, insert at the end and insert at the given index.
1- Inserting node in linked list at the beginning has two scenarios.If it is the first node then both head and tail should point to it.
If nodes already exist then the inserted node should reference the current first node and head should start pointing to the inserted node.
public void insertFirst(int i){
//Create a new node
Node newNode = new Node(i);
if(isEmpty()){
tail = newNode;
}
newNode.next = head;
head = newNode;
size++;
}
Note here that size variable is used to store the current size of the List.
2- Inserting node in linked list at the end has two scenarios.If it is the first node then both head and tail should point to it.
If nodes already exist then the current last node should reference the inserted node and tail should start pointing to the inserted node.
public void insertLast(int i){
Node newNode = new Node(i);
if(isEmpty()){
head = newNode;
}else{
tail.next = newNode;
}
tail = newNode;
size++;
}
3- Inserting node in linked list at the given index has three scenarios.
If inserting at index 0 that is equivalent to insertFirst.
If inserting at index when (index == size) that is equivalent to insertLast.
Otherwise traverse to the node currently at the given index and change the references so that the new node starts referencing the current node and the node which was previously referencing the current node should start referencing the new node.
public void insertAtIndex(int i, int index){
if(!isValidIndex(index)){
throw new IndexOutOfBoundsException("Index " + index +" not valid for linked list of size " + size);
}
Node newNode = new Node(i);
Node current = head;
Node temp = head;
//insert at the start
if(index == 0){
insertFirst(i);
}
// insert at last
else if(index == size){
insertLast(i);
}else{
for(int j = 0; j < index && current.next != null; j++){
temp = current;
current = current.next;
}
newNode.next = current;
temp.next = newNode;
size++;
}
}
Linked List traversal
For Linked list traversal from start to end you need to start from head and then move sequentially unless the next node reference is not null.
// Method to traverse and display all nodes
public void displayList(){
Node current = head;
while(current != null){
current.displayData();
current = current.next;
}
System.out.println("");
}
To get element at a given index traverse to the node currently at that index and return that node.
public Node get(int index){
if(!isValidIndex(index)){
throw new IndexOutOfBoundsException("Index " + index +" not valid for linked list of size " + size);
}
Node current = head;
for(int j = 0; j < index; j++){
current = current.next;
}
return current;
}
Deleting node in Linked List
For deletion there are three scenarios-
- Delete first node
- Delete last node
- Delete node at given index
1- If you are deleting the first node then in your Linked list Java program what you need to do is to change the head reference so that it starts referencing the next node.
public void removeFirst(){
if(head == null){
throw new RuntimeException("List is empty..");
}
// if there is only one node
if(head.next == null){
tail = null;
}
head = head.next;
size--;
}
2- If you are deleting the last node in a linked list then change the reference for tail so that it starts referencing the previous node. Since it is a singly linked list implementation so you need to start from the first node and traverse the list till the end.
public void removeLast(){
if(tail == null){
throw new RuntimeException("List is empty..");
}
Node current = head;
Node temp = head;
// if there is only one node
if(head.next == null){
head = null;
}
while(current != tail){
temp = current;
current = current.next;
}
tail = temp;
tail.next = null;
size--;
}
3- Deleting node at the given index has three scenarios.
If deleting node at index 0 that is equivalent to removeFirst.
If deleting node at index when (index == size) that is equivalent to removeLast.
Otherwise traverse to the node at the given index and change the references so that the node on the left of the node to be deleted starts referencing the node on the right of the node to be deleted.
public void removeAtIndex(int index){
if(!isValidIndex(index +1)){
throw new IndexOutOfBoundsException("Index " + index +" not valid for linked list of size " + size);
}
Node current = head;
Node temp = head;
//remove at the start
if(index == 0){
removeFirst();
}
// remove at last
else if(index == size - 1){
removeLast();
}else{
for(int j = 0; j < index && current.next != null; j++){
temp = current;
current = current.next;
}
temp.next = current.next;
current.next = null;
size--;
}
}
Linked List implementation in Java – Full Program
class Node{
//data
int i;
// Reference to next node
Node next;
public Node(int i){
this.i = i;
this.next = null;
}
public void displayData(){
System.out.print(" " + i);
}
}
public class LinkedList {
private Node head;
private Node tail;
private int size = 0;
public LinkedList(){
head = null;
tail = null;
}
public boolean isEmpty(){
return head == null;
}
public void insertFirst(int i){
//Create a new node
Node newNode = new Node(i);
if(isEmpty()){
tail = newNode;
}
newNode.next = head;
head = newNode;
size++;
}
public void insertLast(int i){
Node newNode = new Node(i);
if(isEmpty()){
head = newNode;
}else{
tail.next = newNode;
}
tail = newNode;
size++;
}
public void insertAtIndex(int i, int index){
if(!isValidIndex(index)){
throw new IndexOutOfBoundsException("Index " + index +" not valid for linked list of size " + size);
}
Node newNode = new Node(i);
Node current = head;
Node temp = head;
//insert at the start
if(index == 0){
insertFirst(i);
}
// insert at last
else if(index == size){
insertLast(i);
}else{
for(int j = 0; j < index && current.next != null; j++){
temp = current;
current = current.next;
}
newNode.next = current;
temp.next = newNode;
size++;
}
}
public Node get(int index){
if(!isValidIndex(index)){
throw new IndexOutOfBoundsException("Index " + index +" not valid for linked list of size " + size);
}
Node current = head;
for(int j = 0; j < index; j++){
current = current.next;
}
return current;
}
// Method to traverse and display all nodes
public void displayList(){
Node current = head;
while(current != null){
current.displayData();
current = current.next;
}
System.out.println("");
}
public void removeFirst(){
if(head == null){
throw new RuntimeException("List is empty..");
}
// if there is only one node
if(head.next == null){
tail = null;
}
head = head.next;
size--;
}
public void removeLast(){
if(tail == null){
throw new RuntimeException("List is empty..");
}
Node current = head;
Node temp = head;
// if there is only one node
if(head.next == null){
head = null;
}
while(current != tail){
temp = current;
current = current.next;
}
tail = temp;
tail.next = null;
size--;
}
public void removeAtIndex(int index){
if(!isValidIndex(index +1)){
throw new IndexOutOfBoundsException("Index " + index +" not valid for linked list of size " + size);
}
Node current = head;
Node temp = head;
//remove at the start
if(index == 0){
removeFirst();
}
// remove at last
else if(index == size - 1){
removeLast();
}else{
for(int j = 0; j < index && current.next != null; j++){
temp = current;
current = current.next;
}
temp.next = current.next;
current.next = null;
size--;
}
}
private boolean isValidIndex(int index){
return index >= 0 && index <= size;
}
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.insertFirst(1);
list.insertLast(2);
list.insertLast(3);
list.insertLast(4);
list.insertLast(5);
System.out.println("After insertions--");
list.displayList();
list.removeLast();
System.out.println("After removal--");
list.displayList();
list.removeAtIndex(1);
System.out.println("After removal--");
list.displayList();
System.out.println("Get Node--");
Node node = list.get(1);
node.displayData();
}
}
Output
After insertions-- 1 2 3 4 5 After removal-- 1 2 3 4 After removal-- 1 3 4 Get Node-- 3
That's all for this topic Linked List Implementation Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!
>>>Return to Java Programs Page
Related Topics
You may also like-
No comments:
Post a Comment