Saturday, March 19, 2016

Java LinkedList Implementation

//Creating Node
public class Node
{
    private int data;
 
    private Node link;
 
    Node()
    {
        link = null;
        data = 0;
    }
 
    Node(int data, Node ref)
    {
        this.data = data;
        this.link = ref;
    }
 
    public int getData()
    {
        return data;
    }
 
    public void setData(int data)
    {
        this.data = data;
    }
 
    public Node getLink()
    {
        return link;
    }
 
    public void setLink(Node link)
    {
        this.link = link;
    }
}



//Creating LinkedList operations
public class LinkedList
{
    private Node head;
 
    private int size;
 
    LinkedList()
    {
        head = null;
        size = 0;
    }
 
    public boolean isEmpty()
    {
        return head == null;
    }
 
    public int getSize()
    {
        return size;
    }
 
    public void insertAtStart(int val)
    {
        Node temp = new Node(val, null);
        size++;
        if (head == null)
        {
            head = temp;
        }
        else
        {
            temp.setLink(head);
            head = temp;
        }
    }
 
    public void display()
    {
        System.out.println("\n----Singly Linked List----");
        if (size == 0)
        {
            System.out.println("Empty");
            return;
        }
        if (head.getLink() == null)
        {
            System.out.println(head.getData());
            return;
        }
        Node temp = head;
        while (temp.getLink() != null)
        {
            System.out.print(temp.getData() + "->");
            temp = temp.getLink();
        }
        System.out.print(temp.getData() + "\n");
     
    }
 
    public void insertAtEnd(int val)
    {
        Node insert = new Node(val, null);
        size++;
        if (head == null)
        {
            head = insert;
         
        }
        else
        {
            Node temp1 = head;
            while (temp1.getLink() != null)
            {
                temp1 = temp1.getLink();
            }
            temp1.setLink(insert);
        }
    }
 
    public void insertAtPos(int val, int pos)
    {
        Node insert = new Node(val, null);
        Node temp = head;
        pos = pos - 1;
        for (int i = 1; i < size; i++)
        {
            if (i == pos)
            {
                Node temp1 = temp.getLink();
                temp.setLink(insert);
                insert.setLink(temp1);
                break;
            }
            temp = temp.getLink();
        }
        size++;
    }
 
    public void deleteAtPos(int pos)
    {
        Node temp = head;
        if (pos > size)
        {
            System.out.println("Wrong number");
            return;
        }
        else if (pos == 1)
        {
            head = head.getLink();
            size--;
            return;
        }
     
        else if (pos == size)
        {
            while (temp.getLink().getLink() != null)
            {
                temp = temp.getLink();
            }
            temp.setLink(null);
            return;
        }
        else
        {
            pos -= 1;
            for (int i = 1; i < size; i++)
            {
                if (pos == i)
                {
                    Node del = temp.getLink();
                    temp.setLink(del.getLink());
                    break;
                }
                temp = temp.getLink();
            }
        }
    }

public void swap(int first, int second) {
Node firstSwap = null;
Node secondSwap = null;
if (first == second) {
return;
}
if (first > second && first > size && second > size && first < 0 && second < 1) {
System.out.println("The Entered Positions are wrong");
return;
}
if(first == 1)
{
firstSwap = new Node(head.getData(),null);
}

first -= 1;
second -= 1;
boolean set = true;
Node temp = head;
for (int i = 1; i < size; i++) {
if (i == first && secondSwap == null) {
firstSwap = new Node(temp.getLink().getData(), null);

}
if (i == first && secondSwap != null) {
secondSwap.setLink(temp.getLink().getLink());
temp.setLink(secondSwap);
break;
}
if (i == second && set) {
secondSwap = new Node(temp.getLink().getData(), null);
firstSwap.setLink(temp.getLink().getLink());
temp.setLink(firstSwap);

//i = ;
temp = head;

if(first ==0)
{

secondSwap.setLink(temp.getLink());
head = secondSwap;
}

}
temp = temp.getLink();
if(i == second && set)
{
set = false;
i = 0;
temp = head;
}
}

}
public void sort()
{
Node temp = null;
int smallEle =0;
int firstIndex=0;
int secondIndex=0;

for(int i=1;i<size;i++)
{
firstIndex =i;
temp = head;
smallEle = temp.getData();
for(int k=1;k<i;k++)
{
temp = temp.getLink();
smallEle = temp.getData();
}
for(int j=i+1;j<=size;j++)
{
temp = temp.getLink();
if(temp == null)
break;
if(smallEle > temp.getData())
{
secondIndex = j;
smallEle = temp.getData();
}
}
swap(firstIndex, secondIndex);
}
}
 public void reverse()
    {
        Node prev = head;
       
        Node cur = head;
        Node future = head.getLink();
        prev.setLink(null);
        while (future != null)
        {
            cur = future;
            future = future.getLink();
            cur.setLink(prev);
            prev = cur;
        }
        head = prev;
    }
}


//Executing class
public class SinglyLinkedList
{
    public static void main(String args[])
    {
        LinkedList linkedList = new LinkedList();
        System.out.println(linkedList.isEmpty());
        linkedList.insertAtStart(1);
        linkedList.insertAtStart(2);
        linkedList.insertAtStart(3);
        linkedList.insertAtStart(4);
        linkedList.insertAtEnd(9);
        linkedList.insertAtPos(10, 3);
        linkedList.display();
        linkedList.deleteAtPos(2);
        linkedList.display();
        //linkedList.swap(1, 5);
linkedList.sort();
        linkedList.display();
        System.out.println("\n" + linkedList.getSize());
    }
}

No comments:

Post a Comment