数据结构-Java实现-ArrayList&LinkedList，-java-arraylist

数据结构-Java实现-ArrayList&LinkedList，-java-arraylist

ArrayList的Java实现

//IList接口，声明基本的操作
public interface IList {
    //返回线性表的大小，即数据元素的个数。
    public int getSize();
    //如果线性表为空返回 true,否则返回 false.
    public boolean isEmpty();
    //判断线性表是否包含数据元素 e
    public boolean contains(Object e);
    //返回数据元素 e 在线性表中的序号
    public  int indexOf(Object e);
    //将数据元素 e 插入到线性表中 i 号位置
    public void insert(int i, Object e) throws OutOfBoundaryException;
    //将数据元素 e 插入到元素 obj 之前
    public boolean insertBefore(Object obj, Object e);
    //将数据元素 e 插入到元素 obj 之后
    public boolean insertAfter(Object obj, Object e);
    //删除线性表中序号为 i 的元素，并返回之
    public Object remove(int i) throws OutOfBoundaryException;
    //删除线性表中第一个与 e 相同的元素
    public boolean remove(Object e);
    //替换线性表中序号为 i 的数据元素为 e, 返回原数据元素
    public Object replace(int i, Object e) throws OutOfBoundaryException;
    //返回线性表中序号为 i 的数据元素为
    public Object get(int i) throws OutOfBoundaryException;
}

//对象比较策略接口，声明基本的比较方法
public interface IStrategy {
    //判断两个数据元素是否相等
    public boolean equal(object obj1, Object obj2);
    /**
    *比较两个数据元素的大小 * 如果 obj1 < obj2 返回-1
    *如果obj1 = obj2 返回0
    *如果obj1 > obj2 返回1
    */
    public int compare(Object obj1, Object obj2);

}

public class defaultStrategy implements IStrategy{
    @Override
    public boolean equal(Object obj1, Object obj2) {
        return obj1.equals(obj2);
    }

    @Override
    public int compare(Object obj2, Object obj2){
        return obj1.toString().compareTo(obj2.toString());
    }
}

//顺序表类
public class MyArrayList implements IList{
    public static void main(String[] args) {

    }
    private final int LEN = 8;     //数组默认大小
    private IStrategy strategy;    //数据元素比较策略
    private int size;              //线性表中数据元素的个数
    private Object[] elements;     //数据元素数组
    //构造方法
    public MyArrayList(){
        this(new DefaultStrategy());
    }

    public MyArrayList(IStrategy strategy){
        this.strategy = strategy;
        size = 0;
        elements = new Object[LEN];
    }
    @Override
    public int getSize() {
        return this.size;
    }

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

    @Override
    public boolean contanis(Object e) {
        for(int i = 0; i < size; i++){
            if(this.strategy.equal(e,elements[i])){
                return true;
            }
        }
        return false;
    }

    @Override
    public int indexOf(Object e){
        for(int i = 0; i < size; i++){
            if(strategy.equal(e,elements[i])){
                return i;
            }
        }
        return -1;
    }

    @Override
    public void insert(int i, Object e) throws OutOfBoundaryException {
        //检查下标越界
        if(i < 0 || i >= size){
            throw new OutOfBoundaryException("指定的插入序号越界。")；
        }
        //检查线性表数组的容量
        if(size >= elements.length){
            expandSpace();
        }
        //将插入位置后的数据元素依次向后移动一个单位
        for( int j = size; j > i; j-- ){
            elements[j] = elements[j-1];
        }
        //插入数据
        elements[i] = e;
        size++;
    }
    //扩展顺序表空间
    private void expandSpace(){
        Object[] a = new Object[elements.length*2];
        for (int i = 0; i<elements.length; i++) {
            a[i] = elements[i];
        }
        elements = a;
    }

    @Override
    public boolean insertBefore(Object obj, Object e) {
        //找到插入位置
        int i = indexOf(obj);
        if (i<0) {
            return false;
        }
        insert(i,e);
        return true;
    }

    @Override
    public boolean insertAfter(Object obj, Object e) {
        int i = indexOf(obj);
        if (i<0) {
            return false;
        }
        insert(i+1,e);
        return true;
    }
    @Override
    public boolean remove(int i) throws OutOfBoundaryException {
        //首先检查越界
        if(i<0 || i>=size) {
            throw new OutOfBoundaryException("错误，指定的删除序号越界。")；
        }
        Object obj = elements[i];
        //被删除的数据元素后的数据前移一个单位
        for (int j=i; i<size-1; j++) {
            elements[j] = elements[j+1];
        }
        //最后一个引用置为null
        elements[--size] = null;
        return obj;
    }
    @Override
    public boolean remove(Object e){
        return remove(indexOf(e));
    }
    @Override
    public Object replace(int i, Object e) throws OutOfBoundaryException {
        if (i<0||i>=size){
            throw new OutOfBoundaryException("错误，指定的删除序号越界。")
        }
        Object obj = elements[i];
        elements[i] = e;
        return obj;
    }
    @Override
    public Object get(int i) throws OutOfBoundaryException {
        if (i<0||i>=size){
            throw new OutOfBoundaryException("错误，指定的删除序号越界。")；
        }
        return elements[i];
    }
}

单向LinkedList的Java实现

//同ArrayList的接口
public interface IList {
    //返回线性表的大小，即数据元素的个数。
    public int getSize();
    //如果线性表为空返回 true,否则返回 false.
    public boolean isEmpty();
    //判断线性表是否包含数据元素 e
    public boolean contains(Object e);
    //返回数据元素 e 在线性表中的序号
    public  int indexOf(Object e);
    //将数据元素 e 插入到线性表中 i 号位置
    public void insert(int i, Object e) throws OutOfBoundaryException;
    //将数据元素 e 插入到元素 obj 之前
    public boolean insertBefore(Object obj, Object e);
    //将数据元素 e 插入到元素 obj 之后
    public boolean insertAfter(Object obj, Object e);
    //删除线性表中序号为 i 的元素，并返回之
    public Object remove(int i) throws OutOfBoundaryException;
    //删除线性表中第一个与 e 相同的元素
    public boolean remove(Object e);
    //替换线性表中序号为 i 的数据元素为 e, 返回原数据元素
    public Object replace(int i, Object e) throws OutOfBoundaryException;
    //返回线性表中序号为 i 的数据元素为
    public Object get(int i) throws OutOfBoundaryException;
}
//单链表结点接口
public interface INode {
    //获取结点数据域
    public Object getData();
    //设置结点数据域
    public void setData(Object obj);
}

public class SLNode implements INode {
    private Object element;//数据域
    private SLNode next；// SLNode的引用作为指针域

    public SLNode() {
        this(null,null);
    }

    public SLNode(Object ele, SLNode next) {
        this.element = ele;
        this.next = next;
    }

    public SLNode getNext(){
        return next;
    }

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

    @Override
    public Object getData(){
        return this.element;
    }

    @Override
    public void setData(Object obj) {
        this.element = obj;
    }
}

public class ListSLinked implements IList {
    private IStrategy strategy;  //数据元素比较策略
    private SLNode head;         //单链表首结点引用
    private int size;            //线性表中数据元素的个数 

    public ListSLinked () {
        this(new DefaultStrategy());
    }

    public ListSLinked (IStrategy strategy) {
        this.strategy = strategy;
        head = new SLNode();     //初始化首结点引用
        size = 0;
    }

    //辅助方法：获取数据元素 e 所在结点的前驱结点
    private SLNode getPreNode(Object e){
        SLNode p = head;    //将首结点引用赋予变量p
        while (p.getNext()!=null)    //利用首节点开始遍历
            if (strategy.equal(p.getNext().getData(),e))    //判断【 p 结点通过getNext()方法指向的下一个结点】通过getData()方法获取的element值与e是否相等
                return p;    //相等则 p结点 为元素 e 的前驱结点
            else p = p.getNext();    //不相等则往下遍历
        return null;
    }
    //辅助方法：获取序号为 0<=i<size 的元素所在结点的前驱结点
    private SLNode getPreNode(int i){
        SLNode p = head;
        for(;i>0;i--)
            p=p.getNext();
        return p;
    }
    //获取序号为 0<=i<size 的元素所在结点 
    private SLNode getNode(int i){
        SLNode p = head.getNext();
        for(;i>0;i--)
            p=p.getNext();
        return p;
    }
    //返回线性表的大小，即数据元素的个数。
    public int getSize(){
        return size;
    }
    //如果线性表为空返回 true,否则返回 false.
    public boolean isEmpty(){
        return size==0;
    }
    //判断线性表是否包含数据元素 e
    public boolean contains(Object e){
        SLNode p = head.getNext();    //通过头指针遍历
        while (p!=null)    //当前结点next引用不为空
            if (strategy.equal(p.getData(),e))
                return true;
            else p = p.getNext();    //临时引用p指向下一个结点
        return false;
    }
    //返回数据元素 e 在线性表中的序号
    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;
    }
    //将数据元素 e 插入到元素 obj 之前
    public boolean insertBefore(Object obj, Object e){
        SLNode p = getPreNode(obj);    //找到obj的前驱结点并赋予p
        if (p!=null){
            /**新建数据元素为 e 指针域为 p 的指针域的新结点并赋予 q 
              *相当于让结点 q 指向 obj
              */
            SLNode q = new SLNode(e,p.getNext());
            /*将新建的结点 q 的引用赋予 p 结点的指针域           
             *相当于让结点 p 指向 q 结点
             */
            p.setNext(q);    
            size++;
            return true;
            }
            else p = p.getNext();
        return false;
    }
    //将数据元素 e 插入到元素 obj 之后
    public boolean insertAfter(Object obj, Object e) {
        SLNode p = head.getNext();
        while (p!=null)
            //找出元素值为obj的p结点
            if (strategy.equal(p.getData(),obj))
            {
            //将 p 结点的指针域赋予元素为 e 的结点，也就是 q 结点
                SlNode q = new SLNode(e,p.getNext());
            //将q结点的引用赋予p结点的指针域
                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){
            p.setNext(p.getNext().getnext());
            size--;
            return true;
        }
        return false;
    }

    public Object replace(int i,Object e) throws OutOfBoundaryException{
        if (i<0||i>=size)
            throw new OutOfBoundaryException("错误，指定的删除序号越界。")；
        SLNode p = getNode(i);
        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 = getNode(i);
        return p.getData();
    }   

双向LinkedList的Java实现

//双向链表Java实现
public class DLNode implements INode {
    private Object element; //数据域
    private DLNode pre;     //前驱结点引用
    private DLNode next;    //后继结点引用

    public DLNode() {
        this(null,null,null);
    }

    public DLNode(Object ele, DLNode pre, DLNode next)
    {
        this.element = ele; this.pre = pre; this.next = next;
    }

    public DLNode getNext(){
        return next;
    }

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

    public DLNode getPre(){
        return pre;
    }

    public void serPre(DLNode pre){
        this.pre = pre;
    }   
}

public interface ILinkedList {
    //查询链接表当前的规模
    public int getSize();
    //判断列表是否为空
    public boolean isEmpty();
    //返回第一个结点
    public INode first() throws OutOfBoundaryException;
    //返回最后一个结点
    public INode last() throws OutOfBoundaryException;
    //返回 p 之后的结点
    public INode getNext(INode p) throws InvalidNodeExceprion, OutOfBoundaryException;
    //返回 p 之前的结点
    public INode getPre(INode p) throws InvalidNodeExceprion, OutOfBoundaryException;
    //将 e 作为第一个元素插入链接表，并返回 e 所在结点
    public INode insertFirst(Object e);
    //将 e 作为最后一个元素插入链接表， 并返回 e 所在结点
    public INode insertLast(Object e);
    //将 e 插入至 p 之后的位置，并返回 e 所在结点
    public INode insertAfter(INode p, Object e) throws InvalidNodeExceprion;
    //将 e 插入至 p 之前的位置，并返回 e 所在结点
    public INode insertBefore(INode p, Object e) throws InvalidNodeExceprion;
    //删除给定位置处的元素，并返回之
    public Object remove(INode p) throws InvalidNodeExceprion;
    //删除首元素，并返回之 
    public Object removeFirst() throws OutOfBoundaryException;
    //删除末元素，并返回之
    public Object removeLast() throws OutOfBoundaryException;
    //将处于给定位置的元素替换为新元素，并返回被替换的元素
    public Object replace(INode p, Object e) throws InvalidNodeExceprion;
}

public class ListDlinked implements ILinkedList {
    private int size;    //规模
    private DLNode head; //头结点，哑元结点
    private DLNode tail; //尾结点，哑元结点

    public ListDlinked(){
        size = 0;
        head = new DLNode();
        tali = new DLNode();
        head.setNext(tail);
        tail.setPre(head);    //头指向尾，尾指向头，只有头尾结点的链表
    }

    //辅助方法，判断结点 p 是否合法，如合法转换为 DLNode
    protected DLNode checkPosition(INode p) throws InvalidNodeExceprion {
        if (p==null)
            throw new InvalidNodeExceprion("错误：p 为空。")；
        if (p==head)
            throw new InvalidNodeException("错误：p 指向头结点，非法。")；
        if (p==tail)
            throw new InvalidNodeExceprion("错误：p 指向尾结点，非法。")；
        DLNode node = (DLNode)p;
        return node;
    }

    //查询链接表当前的规模
    public int getSize();
    //判断列表是否为空
    public boolean isEmpty();
    //返回第一个结点
    public INode first() throws OutOfBoundaryException{
        if (isEmpty())
            throw new OutOfBoundaryException("错误：链接表为空。")；
        return head.getNext();
    }
    //返回最后一个结点
    public INode last() throws OutOfBoundaryException{
        if (isEmpty())
            throw new OutOfBoundaryException("错误：链接表为空。")
        return tail.getPre();
    }
    //返回 p 之后的结点
    public INode getNext(INode p) throws InvalidNodeExceprion, OutOfBoundaryException{
        DLNode node = checkPosition(p);
        node = node.getNext();
        if (node==tail)
            throw new OutOfBoundaryException("错误：已经是链接表尾端。")
        return node;
    }
    //返回 p 之前的结点
    public INode getPre(INode p) throws InvalidNodeExceprion, OutOfBoundaryException{
        DLNode node = checkPosition(p);
        node = node.getPre();
        if (node==head)
            throw new OutOfBoundaryException("错误：已经是链接表首端。")
        return node;
    }
    //将 e 作为第一个元素插入链接表，并返回 e 所在结点
    public INode insertFirst(Object e){
        DLNode node = new DLNode(e,head,head.getNext());
        head.getNext().setPre(node);
        head.setNext(node);
        size++;
        return node;
    }
    //将 e 作为最后一个元素插入链接表， 并返回 e 所在结点
    public INode insertLast(Object e){
        DLNode node = new DLNode(e,head,head.getNext());
        tail.getPre().setNext(node);
        tail.setPre(node);
        size++;
        return node;
    }
    //将 e 插入至 p 之后的位置，并返回 e 所在结点
    public INode insertAfter(INode p, Object e) throws InvalidNodeExceprion{
        DLNode node = checkPosition(p);
        DLNode newNode = new DLNode(e,node,node,getNext());
        node.getNext().serPre(newNode);
        node.setNext(newNode);
        size++;
        return newNode;
    }
    //将 e 插入至 p 之前的位置，并返回 e 所在结点
    public INode insertBefore(INode p, Object e) throws InvalidNodeExceprion{
        DLNode node = checkPosition(p);
        DLNode newNode = new DLNode(e,node.getPre(),node);
        node.serPre.(newNode);
        node.getPre().setNext(newNode);
        size++;
        return newNode;
    }
    //删除给定位置处的元素，并返回之
    public Object remove(INode p) throws InvalidNodeExceprion{
        DLNode node = checkPosition(p);
        Object obj = node.getData();
        node.getPre().setNext(node.getNext());
        node.getNext().setPre(node.getPre());
        size--;
        return obj;
    }
    //删除首元素，并返回之
    public Object removeFirst() throws OutOfBoundaryException{
        return remove(head.getNext());
    }
    //删除末元素，并返回之
    public Object removeLast() throws OutOfBoundaryException{
        return remove(tail.getPre());
    }
    //将处于给定位置的元素替换为新元素，并返回被替换的元素
    public Object replace(INode p, Object e) throws InvalidNodeExceprion{
        DLNode node = checkPosition(p);
        Object obj = node.getData();
        node.setData(e);
        return obj;
    }
}