In previous post, we saw the implementations of different add and remove functionality in linked list. This post is about implementation of index based linked list. We have seen the introduction, of linked list.Linked list is a linear data structure whose order is not given by the physical location of object. Data stored at non-contiguous memory locations , so we can not get the elements of linked list by passing the position.Refer the below graphical explanation.
Since , there is no fixed pattern for consecutive object memory location , indexing is not possible in linked list.That’s why accessing the elements in linked list is costly operation.But still we can access the elements by position in linked list through traversing the entire linked list.We are going to implement below two methods in linked list.[Try Yourself]
get(int index) : This method will return the object at particular position by traversing the linked list in forward direction. In Doubly Linked list we can traverse the list in both forward and backward direction based on index.Valid Index starts from 0 and ends on (N-1) , where N=size of linked list.
Steps:
- if index=0 , return the data at root node.
- if index=sizeof list – 1 , then return the data at last node.
- if 0 < index < sizeof list – 1 , traverse through each node and increment the pointer by 1. If pointer value and index value matches, return the data from pointer node.
indexOf(T data) : This method will return the position of data in linked list from root node if data present in linked list otherwise it will return -1. If linked list has duplicate data, then it will return the position of first occurrence of data in forward direction.
Steps:
- Start with root node as pointer node and initialize index with 0;
- If pointer node data equal to input data , then return the index value.
- If pointer node data is not equal to input data, increment index by one and update pointer node as next node.
- Continue the steps 2 and 3 end of the linked list.
- If data not found in linked list , return -1.
package com.study.singlyLinkedList;
public class Node<T> {
private T data ;
private Node<T> node;
public Node(T data) {
this.data = data;
}
public Node<T> getNode() {
return node;
}
public void setNode(Node<T> node) {
this.node = node;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
@Override
public String toString() {
return data+"" ;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((data == null) ? 0 : data.hashCode());
result = prime * result + ((node == null) ? 0 : node.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (!(obj instanceof Node))
return false;
Node other = (Node) obj;
if (data == null) {
if (other.data != null)
return false;
} else if (!data.equals(other.data))
return false;
if (node == null) {
if (other.node != null)
return false;
} else if (!node.equals(other.node))
return false;
return true;
}
}
package com.study.singlyLinkedList;
public class SinglyLinkedList<T> {
private int size = 0;
private Node<T> node;
/**
* Add element at last.
*
* @param data
*/
public void add(T data) {
if (data == null) {
return;
}
if (node == null) {
node = new Node<T>(data);
} else {
Node<T> newNode = new Node<T>(data);
Node<T> lastNode = getLastNode(node);
lastNode.setNode(newNode);
}
size++;
}
/**
* Add element at first. set the newly created node as root node
*
* @param data
*/
public void addAtFirst(T data) {
if (data == null) {
return;
}
Node<T> newNode = new Node<T>(data);
if (this.node != null) {
newNode.setNode(this.node);
this.node = newNode;
} else {
this.node = newNode;
}
size++;
}
/**
* Add the element at specified index. Index start from 0 to n-1 where n=size of
* linked list. If index is negative value, nothing will be added to linked
* list.
*
* if index =0 , element will be added at head and element become the first
* node.
*
* @param data
* @param index
* - index at which element to be added.
*/
public void add(T data, int index) throws IndexOutOfBoundsException {
if (data == null) {
return;
}
// If index=0 , we should add the data at head
if (index == 0) {
addAtFirst(data);
return;
}
// If index= size, we should add the data at last
if (index == this.size) {
add(data);
} else if (index < this.size) {
Node<T> newNode = new Node<T>(data);
// get the node at (index) from linked list and mark as rightNode.
// get the node at (index-1) from linked list and mark as leftNode.
// set node of newly created node as right node.
// set node of left nose as newly created Node.
Node<T> leftNode = getNode(index - 1);
Node<T> rightNode = getNode(index);
newNode.setNode(rightNode);
leftNode.setNode(newNode);
size++;
} else {
throw new IndexOutOfBoundsException("Index not available.");
}
}
public T get(int index) {
return getNode(index).getData();
}
/**
* Returns the index of data. Index starts from 0 to n. If data not found in
* list, return -1
*
* @param data
* @return
*/
public int indexof(T data) {
Node<T> pointerNode = this.node;
int index = 0;
while (pointerNode != null && pointerNode.getData() != null) {
if (pointerNode.getData().equals(data)) {
return index;
} else {
pointerNode = pointerNode.getNode();
index++;
}
}
return -1;
}
private Node<T> getNode(int index) {
if (index < 0 || index > this.size - 1) {
throw new IndexOutOfBoundsException("Index not available.");
}
// If index=0 , return head
if (index == 0) {
return this.node;
}
// If index= size, return last node
if (index == this.size - 1) {
return getLastNode(this.node);
}
int pointer = 0;
Node<T> pointerNode = this.node;
while (pointer <= index) {
if (pointer == index) {
return pointerNode;
} else {
pointerNode = next(pointerNode);
pointer++;
}
}
return null;
}
private Node<T> getLastNode(Node<T> node) {
Node<T> lastNode = node;
if (lastNode.getNode() != null) {
return getLastNode(lastNode.getNode());
} else {
return lastNode;
}
}
private Node<T> next(Node<T> node) {
if (node.getNode() != null) {
return node.getNode();
} else {
return null;
}
}
public int size() {
return this.size;
}
/**
* Delete the first occurrence of element from linked list if exists and returns
* true. If data not available , it returns false;
*
* @param data
* @return
*/
public boolean delete(T data) {
if (this.node == null) {
return false;
}
Node<T> pointerNode = this.node;
// If input data is the head of linked list.
if (pointerNode.getData().equals(data)) {
this.node = next(pointerNode);
size--;
return true;
}
int indexofData = indexof(data);
if(indexofData >0 ) {
return deleteByIndex(indexofData);
}
else {
return false;
}
}
/**
* Delete the data by index.
*
* @param index
* @return
*/
public boolean deleteByIndex(int index) {
if (this.node == null) {
return false;
}
if (index < 0 || index > this.size - 1) {
throw new IndexOutOfBoundsException("Index not available.");
}
// If index=0 , put head node = Node at index 1.
if (index == 0) {
if(this.node.getNode()!=null) {
this.node = getNode(index + 1);
}else {
this.node=null;
}
size--;
return true;
}
// If index= size -1 means need to delete last node, get the 2nd last node and
// set next node as null.
if (index == this.size - 1) {
getNode(index - 1).setNode(null);
size--;
return true;
}
// if index is in between 0 and size of linked list , set Node of leftNode as
// rightNode
Node<T> leftNode = getNode(index - 1);
Node<T> rightNode = getNode(index + 1);
leftNode.setNode(rightNode);
size--;
return true;
}
/**
* Clear the linked list
*/
public void clear() {
this.node = null;
this.size = 0;
}
@Override
public String toString() {
String represent = "[";
Node<T> nextNode = this.node;
while (nextNode != null) {
represent = represent + nextNode.toString();
nextNode = next(nextNode);
if (nextNode != null) {
represent = represent + ",";
}
}
represent = represent + "]";
return represent;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((node == null) ? 0 : node.hashCode());
result = prime * result + size;
return result;
}
/**
* Two linked list is equal when their size is equals and both have similar node structure
*/
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (!(obj instanceof SinglyLinkedList))
return false;
SinglyLinkedList other = (SinglyLinkedList) obj;
if (node == null) {
if (other.node != null)
return false;
} else if (!node.equals(other.node))
return false;
if (size != other.size)
return false;
return true;
}
}
package com.study.DTO;
public class Item {
private Integer itemId;
private String itemName;
private Double price;
public Item(Integer itemId, String itemName, Double price) {
super();
this.itemId = itemId;
this.itemName = itemName;
this.price = price;
}
public Integer getItemId() {
return itemId;
}
public void setItemId(Integer itemId) {
this.itemId = itemId;
}
public String getItemName() {
return itemName;
}
public void setItemName(String itemName) {
this.itemName = itemName;
}
public Double getPrice() {
return price;
}
public void setPrice(Double price) {
this.price = price;
}
@Override
public String toString() {
return "Item [itemId=" + itemId + ", itemName=" + itemName + ", price=" + price + "]";
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((itemId == null) ? 0 : itemId.hashCode());
result = prime * result + ((itemName == null) ? 0 : itemName.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (!(obj instanceof Item))
return false;
Item other = (Item) obj;
if (itemId == null) {
if (other.itemId != null)
return false;
} else if (!itemId.equals(other.itemId))
return false;
if (itemName == null) {
if (other.itemName != null)
return false;
} else if (!itemName.equals(other.itemName))
return false;
return true;
}
}
package com.study.singlyLinkedList;
import com.study.DTO.Item;
public class TestSinglyLinkedList {
public static void main(String[] args) {
SinglyLinkedList<Item> linkedList=new SinglyLinkedList<Item>();
linkedList.add(new Item(101, "IPhone-5S", 200.00));
linkedList.add(new Item(102, "IPhone-6S", 500.00));
linkedList.add(new Item(103, "IPhone-XX", 1000.00));
linkedList.addAtFirst(new Item(104, "Samsung Pro", 300.00));
linkedList.add(new Item(105, "Samsung Pro Plus", 500.00) , 2);
System.out.println("****** ADDING DUPLICATE Item TO END OF THE LINKED LIST ******");
linkedList.add(new Item(101, "IPhone-5S", 200.00));
System.out.println("AFTER ADDING ALL ITEMS , size: "+linkedList.size() + " "+linkedList);
System.out.println(" ");
System.out.println("Item at position 0 :" +linkedList.get(0));
System.out.println("Item at position 2 :" +linkedList.get(2));
System.out.println(" ");
System.out.println("Position of IPhone-5S:" +linkedList.indexof(new Item(101, "IPhone-5S", 200.00)));
System.out.println("Position of Samsung Pro:" +linkedList.indexof(new Item(104, "Samsung Pro", 300.00)));
}
}
Output:
****** ADDING DUPLICATE Item TO END OF THE LINKED LIST ******
AFTER ADDING ALL ITEMS , size: 6 [Item [itemId=104, itemName=Samsung Pro, price=300.0],Item [itemId=101, itemName=IPhone-5S, price=200.0],Item [itemId=105, itemName=Samsung Pro Plus, price=500.0],Item [itemId=102, itemName=IPhone-6S, price=500.0],Item [itemId=103, itemName=IPhone-XX, price=1000.0],Item [itemId=101, itemName=IPhone-5S, price=200.0]]
Item at position 0 :Item [itemId=104, itemName=Samsung Pro, price=300.0]
Item at position 2 :Item [itemId=105, itemName=Samsung Pro Plus, price=500.0]
Position of IPhone-5S:1
Position of Samsung Pro:0
————————————————————————————————–
Hope you like this post. Please give your valuable suggestions/comments.
In next post, we will see how to reverse the linked list.
You may like –
- Singly Linked List Implementation using in java.
- Singly Linked List Implementation using generics in Java.
- Delete/Remove operations in Linked list
- Reverse a Singly Linked List.
- Find the middle element of a Singly Linked List.
- Merge sort for Linked List in Java.
- Remove duplicate node from linked list.
- Rotation of Linked List.
- Intersection of two linked lists.
- Iterator for singly linked list java.
