Unsorted implementation of the LinkedList ADT interface.

UnsortedLinkedList.java

package it.pm.algorithms.impl;

import it.pm.algorithms.LinkedList;

/**
 * Implementation of the {@link LinkedList} abstract class as unsorted list.
 *
 * @param <T>
 *      Type to use for Nodes' values
 *
 * @author Paolo Maresca <plo.maresca@gmail.com>
 */
public class UnsortedLinkedList<T extends Comparable<T>> extends LinkedList<T>
{

    public UnsortedLinkedList() { super(); }


    @Override
    public void iterativeReverse()
    {
        if(head == null || head.next == null)
            return;

        Node p1 = head, p2 = p1.next, tmp = null;
        p1.next = null;
        while(p1 != p2) {   // reverse links incrementally
            if(p2.next == null) {
                head = p2;
                tmp = null;
            } else
                tmp = p2.next;
            p2.next = p1;
            p1 = p2;
            if(tmp != null)
                p2 = tmp;
        }
    }

    @Override
    public void recursiveReverse()
    {
        if(head == null || head.next == null)
            return;

        Node p1 = head, p2 = p1.next;
        p1.next = null;
        _reverse(p1, p2);   // reverse recursively
    }

    private void _reverse(Node p1, Node p2)
    {
        if(p2.next == null) {
            head = p2;
            p2.next = p1;
            p1 = p2;
        } else {
            Node tmp = p2.next;
            p2.next = p1;
            p1 = p2;
            p2 = tmp;
            _reverse(p1, p2);
        }
    }

    @Override
    public void insert(T value)
    {
        Node elem = new Node(value);
        if(head != null) {
            elem.next = head;
            head = elem;
        } else
            head = elem;
    }

    @Override
    public Node search(T value)
    {
        if(head == null)
            return null;
        else
            return _search(head, value);
    }

    private Node _search(Node elem, T value)
    {
        if(elem.value.equals(value))
            return elem;
        else if(elem.next != null)
            return _search(elem.next, value);
        else
            return null;
    }

    @Override
    public Node delete(T value)
    {
        Node deleted = null, pred = null;
        if(head != null && head.value.equals(value)) {
            deleted = head;
            if(head.next != null)
                head = head.next;
            else
                head = null;
        } else {
            pred = _predecessor(head, value);
            if(pred != null) {
                deleted = pred.next;
                pred.next = pred.next.next;
            }
        }

        return deleted;
    }

    private Node _predecessor(Node elem, T value)
    {
        if(elem == null || elem.next == null)
            return null;
        else if(elem.next.value.equals(value))
            return elem;
        else
            return _predecessor(elem.next, value);
    }

    @Override
    public T min()
    {
        if(head == null)
            return null;
        else
            return _min((T) head.value, head);
    }

    private T _min(T min, Node elem)
    {
        min = (min.compareTo((T) elem.value) >= 0?(T) elem.value:min);
        if(elem.next == null)
            return min;
        else
            return _min(min, elem.next);
    }

    @Override
    public T max()
    {
        if(head == null)
            return null;
        else
            return _max((T) head.value, head);
    }

    private T _max(T max, Node elem)
    {
        max = (max.compareTo((T) elem.value) <= 0?(T) elem.value:max);
        if(elem.next == null)
            return max;
        else
            return _max(max, elem.next);
    }

}