16 January 2010

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.

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;
}
```

```package dsa.linkedlist;

/**
* This is a singly linked list with no prev pointer.
* @author Braga
* @param <E>
*/

Node<E> start;
int size;

start = null;
size = 0;
}

//insertAtLast
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;

private int labRats;

public void setUp(){
labRats = 10;
}

assertEquals(sampleList.getLast().data.intValue(),100);
}

public void testInsertAtLast(){
sampleList.insertAtLast(100);
assertEquals(sampleList.getLast().data.intValue(),100);
}

public void testInsertAtFirst(){
sampleList.insertAtFirst(100);
assertEquals(sampleList.getFirst().data.intValue(),100);
}

public void testInsertAt(){
sampleList.insertAt(2, 100);
assertEquals(sampleList.getNodeAt(2).data.intValue(),100);
}

public void testGetNodeAt(){
assertEquals(sampleList.getNodeAt(2).data.intValue(),2);
}

public void testGetFirst(){
assertEquals(sampleList.getFirst().data.intValue(),0);
}

public void testGetLast(){
assertEquals(sampleList.getLast().data.intValue(),labRats-1);
}

public void testRemoveAtFirst(){
int returnValue = sampleList.removeAtFirst();
assertEquals(returnValue,0);
assertEquals(sampleList.getFirst().data.intValue(),1);
}

public void testRemoveAtLast(){
int returnValue = sampleList.removeAtLast();
assertEquals(returnValue,labRats-1);
assertEquals(sampleList.getLast().data.intValue(),labRats-2);
}

public void testRemoveAt(){
int returnValue = sampleList.removeAt(4);
assertEquals(returnValue,4);
assertEquals(sampleList.getNodeAt(4).data.intValue(),5);
}

public void testToString(){
assertEquals(sampleList.toString(),"0, 1, 2, 3, 4, 5, 6, 7, 8, 9");
}

for(int i=0;i<count;i++){
}
return sampleList;
}
}
```

Cheers,

Horninc said...

realy good work!

BragBoy said...

@Horninc: Thank you very much for reading!

Maya (Nand) Jha said...

Thank you so much! Really good information.

BragBoy said...

@Maya: You're most welcome!

Unknown said...

Its Awesome Blog..Well Done Brag..Keep it Up ..Keep Sharing Your Knowledge

BragBoy said...