Java数据结构-单链表

List.java

package com.linearlist;

public interface List {
    public int getSize();
    public boolean isEmpty();
    public boolean contains(Object e);
    public int indexOf(Object e);
    public void insert(int i, Object e) throws OutOfBoundaryException;
    public boolean insertBefore(Object obj, Object e);
    public boolean insertAfter(Object obj, Object e);
    public Object remove(int i) throws OutOfBoundaryException;
    public boolean remove(Object e);
    public Object replace(int i, Object e) throws OutOfBoundaryException;
    public Object get(int i) throws OutOfBoundaryException;
}

Node.java

package com.linearlist;

public interface Node {
    public Object getData();
    public void setData(Object obj);
}

SLNode.java

package com.linearlist;

public class SLNode implements Node{
    private Object element;
    private SLNode next;

    public SLNode(){
        this(null, null);
    }
    public SLNode(Object elem, SLNode next){
        this.element = elem;
        this.next = next;
    }
    public SLNode getNext(){
        return next;
    }
    public void setNext(SLNode next){
        this.next = next;
    }

    // 方法重写
    public Object getData(){
        return element;
    }

    public void setData(Object obj){
        element = obj;
    }
}

ListSLinked.java

package com.linearlist;

public class ListSLinked implements List{
    private Strategy strategy;
    private SLNode head;
    private int size;

    public ListSLinked(){
        // 默认比较策略
    }
    public ListSLinked(Strategy strategy){
        this.strategy = strategy;
        head = new SLNode();
        size = 0;
    }


    //--------------------新增方法---------------------------
    // 获取数据元素 e 所在结点的前驱结点
    private SLNode getPreNode(Object e){
        SLNode p = head;
        while(p.getNext()!=null)
            if(strategy.equal(p.getNext().getData(), e)) return p;
            else p = p.getNext();
        return null;
    }
    // 获取序号为 0<=i<size 的元素所在结点的前驱结点
    private SLNode getPreNode(int i){
        SLNode p = head;
        for(int j=0; j<i; j++)
            p = p.getNext();
        return p;
    }

    //--------------------方法重写---------------------------

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean contains(Object e) {
        SLNode p = head.getNext();
        while (p != null){
            if(strategy.equal(p.getData(), e)) return true;
            else p = p.getNext();
        }
        return false;
    }

    public int indexOf(Object e) {
        SLNode p = head.getNext();
        int index = 0;
        while (p!=null){
            if(strategy.equal(p.getData(), e)) return index;
            else {index++; p=p.getNext();}
        }
        return -1;
    }

    public void insert(int i, Object e) throws OutOfBoundaryException {
        if (i<0||i>size)
            throw new OutOfBoundaryException("错误，指定的插入序号越界。");
        SLNode p = getPreNode(i);
        SLNode q = new SLNode(e, p.getNext());
        p.setNext(q);
        size++;
    }

    public boolean insertBefore(Object obj, Object e) {
        SLNode p = getPreNode(obj);
        if(p!=null){
            SLNode q= new SLNode(e, p.getNext());
            p.setNext(q);
            size++;
            return true;
        }
        return false;
    }

    public boolean insertAfter(Object obj, Object e) {
        SLNode p = head.getNext();
        while (p!=null){
            if(strategy.equal(p.getData(), obj)){
                SLNode q = new SLNode(e, p.getNext());
                p.setNext(q);
                size++;
                return true;
            }
            else p = p.getNext();
        }
        return false;
    }

    public Object remove(int i) throws OutOfBoundaryException {
        if (i<0||i>size)
            throw new OutOfBoundaryException("错误，指定的插入序号越界。");
        SLNode p = getPreNode(i);
        Object obj = p.getNext().getData();
        p.setNext(p.getNext().getNext());
        size--;
        return obj;
    }

    public boolean remove(Object e) {
        SLNode p = getPreNode(e);
        if(p!=null){
            SLNode q = new SLNode(e, p.getNext());
            p.setNext(q);
            size++;
            return true;
        }
        else return false;
    }

    public Object replace(int i, Object e) throws OutOfBoundaryException {
        if (i<0||i>size)
            throw new OutOfBoundaryException("错误，指定的插入序号越界。");
        SLNode p = getPreNode(i).getNext();
        Object obj = p.getData();
        p.setData(e);
        return obj;
    }

    public Object get(int i) throws OutOfBoundaryException {
        if (i<0||i>size)
            throw new OutOfBoundaryException("错误，指定的插入序号越界。");
        SLNode p = getPreNode(i).getNext();
        return p.getData();
    }
}