Hi folks,
Linked list is one of the most discussed data structures and is frequently asked in interviews in many higher level companies like google, amazon etc., I have tried to implement the Single List comprehensively in Java.
Don't we already have a LinkedList in Java?
Yes we do. But the one that I have given here is a Single Linked List which means that we can traverse only one side. This code will be the base for all the problems in linked list that we are going to solve. I have provided both the class and its testcase.
Supporting Node datastructure for the singly linked list
package dsa.linkedlist;
public class Node<E>{
E data;
Node<E> next;
}
The SingleLinkedList class,
package dsa.linkedlist;
/**
* This is a singly linked list with no prev pointer.
* @author Braga
* @param <E>
*/
public class SinglyLinkedList<E> {
Node<E> start;
int size;
public SinglyLinkedList(){
start = null;
size = 0;
}
//insertAtLast
public void add(E data){
insertAtLast(data);
}
public void insertAtLast(E data){
if(size==0){
start = new Node<E>();
start.next = null;
start.data = data;
}else{
Node<E> currentNode = getNodeAt(size-1);
Node<E> newNode = new Node<E>();
newNode.data = data;
newNode.next = null;
currentNode.next = newNode;
}
size++;
}
public void insertAtFirst(E data){
if(size==0){
start = new Node<E>();
start.next = null;
start.data = data;
}else{
Node<E> newNode = new Node<E>();
newNode.data = data;
newNode.next = start;
start = newNode;
}
size++;
}
public Node<E> getNodeAt(int nodePos) throws ArrayIndexOutOfBoundsException{
if(nodePos>=size || nodePos<0){
throw new ArrayIndexOutOfBoundsException();
}
Node<E> temp = start;//Move pointer to front
int counter = 0;
for(;counter<nodePos;counter++){
temp = temp.next;
}
return temp;
}
public void insertAt(int position, E data){
if(position == 0){
insertAtFirst(data);
}else if(position==size-1){
insertAtLast(data);
}else{
Node<E> tempNode = getNodeAt(position-1);
Node<E> newNode = new Node<E>();
newNode.data = data;
newNode.next = tempNode.next;
tempNode.next = newNode;
size++;
}
}
public Node<E> getFirst(){
return getNodeAt(0);
}
public Node<E> getLast(){
return getNodeAt(size-1);
}
public E removeAtFirst(){
if(size==0){
throw new ArrayIndexOutOfBoundsException();
}
E data = start.data;
start = start.next;
size--;
return data;
}
public E removeAtLast(){
if(size==0){
throw new ArrayIndexOutOfBoundsException();
}
Node<E> tempNode = getNodeAt(size-2);
E data = tempNode.next.data;
tempNode.next = null;
size--;
return data;
}
public E removeAt(int position){
if(position==0){
return removeAtFirst();
}else if(position == size-1){
return removeAtLast();
}else{
Node<E> tempNode = getNodeAt(position-1);
E data = tempNode.next.data;
tempNode.next = tempNode.next.next;
size--;
return data;
}
}
public int size(){
return size;
}
public String toString(){
if(size==0){
return "";
}else{
StringBuilder output = new StringBuilder();
Node<E> tempNode = start;
while(tempNode.next!=null){
output.append(tempNode.data).append(", ");
tempNode = tempNode.next;
}
output.append(tempNode.data);
return output.toString();
}
}
}
The JUnit test for the SingleLinkedList class
package dsa.linkedlist;
import junit.framework.TestCase;
public class SinglyLinkedListTest extends TestCase{
private int labRats;
public void setUp(){
labRats = 10;
}
public void testAdd(){
SinglyLinkedList<Integer> sampleList = getLabRatList(labRats);
sampleList.add(100);
assertEquals(sampleList.getLast().data.intValue(),100);
}
public void testInsertAtLast(){
SinglyLinkedList<Integer> sampleList = getLabRatList(labRats);
sampleList.insertAtLast(100);
assertEquals(sampleList.getLast().data.intValue(),100);
}
public void testInsertAtFirst(){
SinglyLinkedList<Integer> sampleList = getLabRatList(labRats);
sampleList.insertAtFirst(100);
assertEquals(sampleList.getFirst().data.intValue(),100);
}
public void testInsertAt(){
SinglyLinkedList<Integer> sampleList = getLabRatList(labRats);
sampleList.insertAt(2, 100);
assertEquals(sampleList.getNodeAt(2).data.intValue(),100);
}
public void testGetNodeAt(){
SinglyLinkedList<Integer> sampleList = getLabRatList(labRats);
assertEquals(sampleList.getNodeAt(2).data.intValue(),2);
}
public void testGetFirst(){
SinglyLinkedList<Integer> sampleList = getLabRatList(labRats);
assertEquals(sampleList.getFirst().data.intValue(),0);
}
public void testGetLast(){
SinglyLinkedList<Integer> sampleList = getLabRatList(labRats);
assertEquals(sampleList.getLast().data.intValue(),labRats-1);
}
public void testRemoveAtFirst(){
SinglyLinkedList<Integer> sampleList = getLabRatList(labRats);
int returnValue = sampleList.removeAtFirst();
assertEquals(returnValue,0);
assertEquals(sampleList.getFirst().data.intValue(),1);
}
public void testRemoveAtLast(){
SinglyLinkedList<Integer> sampleList = getLabRatList(labRats);
int returnValue = sampleList.removeAtLast();
assertEquals(returnValue,labRats-1);
assertEquals(sampleList.getLast().data.intValue(),labRats-2);
}
public void testRemoveAt(){
SinglyLinkedList<Integer> sampleList = getLabRatList(labRats);
int returnValue = sampleList.removeAt(4);
assertEquals(returnValue,4);
assertEquals(sampleList.getNodeAt(4).data.intValue(),5);
}
public void testToString(){
SinglyLinkedList<Integer> sampleList = getLabRatList(labRats);
assertEquals(sampleList.toString(),"0, 1, 2, 3, 4, 5, 6, 7, 8, 9");
}
private SinglyLinkedList<Integer> getLabRatList(int count){
SinglyLinkedList<Integer> sampleList = new SinglyLinkedList<Integer>();
for(int i=0;i<count;i++){
sampleList.add(i);
}
return sampleList;
}
}
Cheers,
Bragaadeesh.
