Pacific-Design.com

    
Home Index

1. Algorithms

2. Linked List

Algorithms / Linked List /

/**
 * @author Kevin Duraj 
 * @DataStructure  LinkedList  
 */
    public class Node {

        Node next;
        Object data;

        public Node(Object data) {
            next = null;
            this.data = data;
        }

        public Node(Object data, Node next) {
            this.next = next;
            this.data = data;
        }

        public Object getData() {
            return data;
        }

        public void setData(Object data) {
            this.data = data;
        }

        public Node getNext() {
            return next;
        }

        public void setNext(Node next) {
            this.next = next;
        }
    }


/**
 * @author Kevin Duraj 
 * @DataStructure Store LinkedList in sorted order 
 * @Complexity O(n)
 */
public class LinkedList {

    private Node head;
    private int size;

    /*-------------------------------------------------------------------
    LinkedList Constructor
    */
    public LinkedList() {

        head = new Node(null);
        size = 0;
    }
    /*-------------------------------------------------------------------
     Get Size of the LinkedList
     */

    public int getSize() {
        return size;
    }
    /*-------------------------------------------------------------------
     Add Node based on index 
     */

    public void add(Object data, int index) {
        Node temp = new Node(data);
        Node node = head;

        for (int i = 1; i < index && node.getNext() != null; i++) {
            node = node.getNext();
        }

        temp.setNext(node.getNext());
        node.setNext(temp);
        size++;
    }

    /*-------------------------------------------------------------------
     Get Node based on index
     */
    public Object get(int index) {
        if (index <= 0) {
            return null;
        }

        Node node = head.getNext();
        for (int i = 1; i < index; i++) {
            if (node.getNext() == null) {
                return null;
            }

            node = node.getNext();
        }
        return node.getData();
    }

    /*-------------------------------------------------------------------
     Add Node into LinkedList in Sorted Order
     */
    public void addInOrder(int val) {

        int index = 0;
        int last = 0;
        boolean found = false;

        if (size == 0) {
            add(val, 1);
        } else {

            for (int i = 1; i <= size; i++) {

                int temp = (int) get(i);

                if (val < temp) {
                    index = i;
                    found = true;
                    break;
                }
                last = i;
            }

            if (found) {
                add(val, index);
            } else {
                add(val, last + 1);
            }
        }
    }
    /*-------------------------------------------------------------------
     Remove Node from LinkedList based on index
     */

    public void remove(int index) {

        if (index == 1) {
            head = head.getNext();
            size--;
            return;
        }
        if (index == size) {
            Node ptr = head;

            for (int i = 1; i < size - 1; i++) {
                ptr = ptr.getNext();
            }

            ptr.setNext(null);
            size--;
            return;
        }

        Node curent = head;
        index = index - 1;
        for (int i = 1; i < size - 1; i++) {
            if (i == index) {
                Node tmp = curent.getNext();
                tmp = tmp.getNext();
                curent.setNext(tmp);
                break;
            }
            curent = curent.getNext();
        }
        size--;
    }
    /*-------------------------------------------------------------------
     Override LinkedList Output
     */

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= size; i++) {
            sb.append(get(i)).append(" ");
        }
        return sb.toString().concat("\n");
    }
    /*-------------------------------------------------------------------*/
}


import java.util.Arrays;

/**
 * @author Kevin Duraj 
 * @DataStructure Store LinkedList in sorted order 
 * @Complexity O(n)
 */
public class App {

    public static void main(String[] args) {

        LinkedList list = new LinkedList();
        int[] array1 = {3, 1, 5, 0};
        int[] array2 = {2, 8, 1};

        for (int i = 0; i < array1.length; i++) {
            list.addInOrder(array1[i]);
        }
        for (int i = 0; i < array2.length; i++) {
            list.addInOrder(array2[i]);
        }

        System.out.println("input array1 = " + Arrays.toString(array1));
        System.out.println("input array2 = " + Arrays.toString(array2));
        System.out.println("------------------------------------");
        System.out.print("output linked list = ");
        System.out.print(list);
        System.out.println("------------------------------------");
        System.out.println("Remove Index 3");
        list.remove(3);
        System.out.print(list);
        System.out.println();
    }

}

/*
Output

input array1 = [3, 1, 5, 0]
input array2 = [2, 8, 1]
------------------------------------
output linked list = 0 1 1 2 3 5 8 
------------------------------------
Remove Index 3
0 1 2 3 5 8 
*/