2019.10.19双向链表

import java.util.nosuchelementexception;

public class linkedlistt<e> {
    private node<e> first;

    private node<e> last;

    long size = 0l;

    private void linklast(e e) {
        node<e> temp = last;
        node<e> newnode = new node<e>(temp, e, null);
        last = newnode;
        if (temp == null) {
            first = newnode;
        } else {
            temp.next = newnode;
        }
        size++;
    }

    public boolean add(e e) {
        linklast(e);
        return true;
    }

    public boolean add(long index, e e) {
        checkinsertindex(index);
        if (index > 0 && index < size) {
            //从前到后的查法
            /*long j = 0;
            for (node<e> i = first; i != null; i = i.next, j++) {
                if (j == index) {
                    node<e> newnode = new node<>(i.prev, e, i);
                    i.prev.next = newnode;
                    i.prev = newnode;
                }
            }*/
            //分前后查找法
            node<e> node = indexnode(issize(index), index);
            node<e> newnode = new node<>(node.prev, e, node);
            node.prev.next = newnode;
            node.prev = newnode;
            size++;
        } else if (index == 0) {
            addfirst(e);
        }
        if (index == size) {
            linklast(e);
        }
        return true;
    }

    public void checkinsertindex(long index) {
        if (index > size || index < 0) {
            throw new indexoutofboundsexception();
        }
    }

    public boolean addfirst(e e) {
        if (size == 0) {
            linklast(e);
        } else {
            node<e> newnode = new node<>(null, e, first);
            first.prev = newnode;
            first = newnode;
            size++;
        }
        return true;
    }

    public boolean addlast(e e) {
        linklast(e);
        return true;
    }

    public e getfirst() {
        if (first == null) {
            throw new nosuchelementexception();
        }
        return first.item;
    }

    public e getlast() {
        if (last == null) {
            throw new nosuchelementexception();
        }
        return last.item;
    }

    public long getsize() {
        return size;
    }

    public e get(long index) {
        e result = null;
        checkinsertindex(index);
        long j = 0;
        for (node<e> i = first; i != null; i = i.next, j++) {
            if (j == index) {
                result = i.item;
            }
        }
        return result;
    }

    public void removeall() {
        first = null;
        last = null;
        size = 0;
    }

    public e remove(long index) {
        e e = null;
        checkremoveindex(index);
        if (index != 0 && index != size - 1){
            node<e> node = indexnode(issize(index), index);
//            node<e> prev = node.prev;
            node.prev.next = node.next;
            node.next.prev = node.prev;
            e = node.item;
            node = null;
            size--;
        }else if(index == 0){
            e = removefirst();
        }else {
            e = removelast();
        }
        return e;
    }

    private void checkremoveindex(long index){
        if (index >= size || index < 0) {
            throw new indexoutofboundsexception();
        }
    }

    private node<e> indexnode(boolean flag, long index) {
        long j = 0;
        node<e> node = null;
        if (flag) {
            for (node<e> i = first; i != null; i = i.next, j++) {
                if (index == j) {
                    node = i;
                }
            }
        } else {
            j = size - 1;
            for (node<e> i = last; i != null; i = i.prev, j--) {
                if (index == j){
                    node = i;
                }
            }
        }
        return node;
    }

    private boolean issize(long index) {
        if (size / 2 >= index) {
            return true;
        } else {
            return false;
        }
    }

    public e remove(object obj) {
        e e = null;
        if (obj == null){
            for ( node<e> i = first;i != null;i = i.next){
                if (i.item == obj){
                    e = unlink(i);
                }
            }
        }else {
            for ( node<e> i = first;i != null;i = i.next){
                if (i.item.equals(obj)){
                    e = unlink(i);
                }
            }
        }
        return e;
    }

    e unlink(node<e> x) {
        e element = x.item;
        node<e> next = x.next;
        node<e> prev = x.prev;

        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }

        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        return element;
    }

    public e removefirst() {
        if (size == 0) {
            throw new indexoutofboundsexception();
        }
        node<e> second = first.next;
        e e = first.item;
        first.next = null;
        if (second == null) {
            last = null;
        } else {
            second.prev = null;
        }
        first = second;
        size--;
        return e;
    }

    public e removelast() {
        if (size == 0) {
            throw new indexoutofboundsexception();
        }
        node<e> secondlast = last.prev;
        e e = last.item;
        last.prev = null;
        if (secondlast == null) {
            first = null;
        } else {
            secondlast.next = null;
        }
        last = secondlast;
        size--;
        return e;
    }

    private static class node<e> {
        e item;
        node<e> next;
        node<e> prev;

        node(node<e> prev, e item, node<e> next) {
            this.item = item;
            this.next = next;
            this.prev = prev;
        }
    }

    @override
    public string tostring() {
        stringbuffer str = new stringbuffer("");
        for (node<e> i = first; i != null; i = i.next) {
            str.append(i.item);
            if (i.next != null) {
                str.append(",");
            }
        }
        return "[" + str.tostring() + "]";
    }
}