Answer to Question #317293 in Java | JSP | JSF for inder

Question

Implement your own version of the linked list using java with mentioned functionalities: insert, insert at position, delete, delete at position, center, reverse, size, iterator, traverse/print.

Use of similar data structures already present in the language/framework is not allowed.

Answer 1

class LinledList
{
    static class Node<T>
    {
        public T item;
        public Node<T> next;
        public Node()
        {
            this.next = null;
        }
    }
    static class LinkList<T>
    {
        public Node<T> head;
        public LinkList()
        {
            this.head = null;
        }
        public void insert(T item)
        {
            Node<T> newNode = new Node<T>();
            newNode.item = item;
            if (this.head == null)
            {
                this.head = newNode;
            }
            else
            {
                Node<T> tempNode = this.head;
                while (tempNode.next != null)
                {
                    tempNode = tempNode.next;
                }
                tempNode.next = newNode;
            }
        }
        private Node<T> getNodeByPosition(int position)
        {
            if (position < 0)
            {
                System.out.println("Wrong index. Index: " + position);
            }
            Node<T> currentNode = head;
            int i = 0;
            try
            {
                for (; i < position; ++i)
                {
                    currentNode = currentNode.next;
                }
            }
            catch (NullPointerException e)
            {
                System.out.println("Wrong index. Index: " + position + ", Size: " + i);
            }
            return currentNode;
        }
        public void insertAt(int position, T item)
        {
            Node<T> newNode = new Node<T>();
            newNode.item = item;
            newNode.next = null;
            if (position == 0)
            {
                newNode.next = head;
                head = newNode;
            }
            else if (position == size())
            {
                insert(item);
            }
            else
            {
                Node<T> prevNode = getNodeByPosition(position - 1);
                Node<T> nextNode = getNodeByPosition(position);
                prevNode.next = newNode;
                newNode.next = nextNode;
            }
        }
        public Boolean isEmpty()
        {
            return head == null;
        }
        public T center()
        {
            Node<T> node1 = head;
            Node<T> node2 = head;


            if (head != null)
            {
                while (node2 != null && node2.next != null)
                {
                    node2 = node2.next.next;
                    node1 = node1.next;
                }
            }
            return node1.item;
        }
        public void delete(T item)
        {
            if (this.head.item.equals(item))
            {
                head = head.next;
            }
            else
            {
                Node<T> tempNode = head;
                Node<T> tempPrevious = head;
                Boolean isFound = false;
                while (!(isFound = tempNode.item.equals(item)) && tempNode.next != null)
                {
                    tempPrevious = tempNode;
                    tempNode = tempNode.next;
                }
                if (isFound)
                {
                    tempPrevious.next = tempNode.next;
                }
                else
                {
                    System.out.println("Item not found!");
                }
            }
        }
        public void deleteAt(int position)
        {
            if (head == null)
                return;


            Node<T> tempNode = head;
            if (position == 0)
            {
                head = tempNode.next;
                return;
            }
            // Find previous node
            for (int i = 0; tempNode != null && i < position - 1; i++)
            {
                tempNode = tempNode.next;
            }
            if (tempNode == null || tempNode.next == null)
            {
                return;
            }
            Node<T> next = tempNode.next.next;
            tempNode.next = next;
        }
        public int size()
        {
            Node<T> tempNode = head;
            int numberNodes = 0;
            while (tempNode != null)
            {
                numberNodes++;
                tempNode = tempNode.next;
            }
            return numberNodes;
        }
        public void reverse()
        {
            Node<T> previousNode = null;
            Node<T> currentNode = head;
            Node<T> tempNode = null;
            while (currentNode != null)
            {
                tempNode = currentNode.next;
                currentNode.next = previousNode;
                previousNode = currentNode;
                currentNode = tempNode;
            }
            head = previousNode;
        }
        public void print()
        {
            System.out.println("Link List Items:");
            Node<T> tempNode = this.head;
            while (tempNode != null)
            {
                System.out.println(tempNode.item);
                tempNode = tempNode.next;
            }
        }
    }


    static class LinkListIterator<T>
    {
        private Node<T> currentNode;



        public LinkListIterator(LinkList<T> linkList)
        {
            this.currentNode = linkList.head;
        }
        // returns false if next node does not exist
        public Boolean hasNext()
        {
            return this.currentNode != null;
        }


        // return current item
        public T next()
        {
            T data = this.currentNode.item;
            this.currentNode = this.currentNode.next;
            return data;
        }
    }
    public static void main(String[] args)
    {
        try
        {
            System.out.println("Intger items");
            LinkList<Integer> linkList = new LinkList<Integer>();
            linkList.insert(5);
            linkList.insert(10);
            linkList.insert(7);
            linkList.insert(2);
            linkList.insertAt(2, 11);
            linkList.print();
            System.out.println("The middle element is: " + linkList.center() + "\n");
            System.out.println("Reverse: ");
            linkList.reverse();
            linkList.print();
            System.out.println("Size = " + linkList.size());


            System.out.println("\nDisplay items using LinkListIterator");
            LinkListIterator<Integer> linkListIterator = new LinkListIterator<Integer>(linkList);
            while (linkListIterator.hasNext())
            {
                System.out.println(linkListIterator.next());
            }


            System.out.println("Delete 2 from the link list");
            linkList.delete(2);
            System.out.println("DeleteAt position 1 from the link list");
            linkList.deleteAt(1);
            linkList.print();

            System.out.println("\n\nString items");
            LinkList<String> linkListNames = new LinkList<String>();
            linkListNames.insert("Mary");
            linkListNames.insert("Peter");
            linkListNames.insertAt(1, "Mike");
            linkListNames.print();
            System.out.println("The middle element is: " + linkListNames.center() + "\n");
            System.out.println("Reverse: ");
            linkListNames.reverse();
            linkListNames.print();
            System.out.println("Size = " + linkListNames.size());


            System.out.println("\nDisplay items using LinkListIterator");
            LinkListIterator<String> linkListIteratorNames = new LinkListIterator<String>(linkListNames);
            while (linkListIteratorNames.hasNext())
            {
                System.out.println(linkListIteratorNames.next());
            }


            System.out.println("Delete 'Mary' from the link list");
            linkListNames.delete("Mary");
            System.out.println("DeleteAt position 1 from the link list");
            linkListNames.deleteAt(1);
            linkListNames.print();
        }
        catch (Exception ex) {
            System.out.println(ex.getMessage());
        }
    }
}