中小型网站建设流程/济宁百度竞价推广

我前面写了一个笔记，【java】设计一个类ArrayBox，比数组更灵活（增删元素时不用纠结长度变化的问题）----底层依旧是数组，不过可以自动的扩容，不用担心增加元素，而数组空间不足的问题。（但是它存在一个问题，就是增删的效率特别底下，因为它是不断的移动元素的位置进行调整）

---

所以，
我现在，用双向链表设计一个类LinkedBox，比数组的增删的效率更高
虽然有一个缺点，查找就比较不方便了

---

上述我说到的两个 类似数组 的类，都必须要有这四个功能：

• 添加元素add()
• 获取元素get()
• 删除元素remove()
• 查看元素个数size()

假设我给用户提供这两个类，ArrayBox和LinkedBox，我们给用户调用的方法名最好要一样，这样用户才好记忆

于是，先定义一个规范（就是接口）

Box.java

将ArrayBox和LinkedBox这两个类都继承于Box.java这个接口

package util;public interface Box {public boolean add(int element); //增加元素public int get(int index);//获取元素public int remove(int index);//删除元素public int size();//查看元素个数
}

再将ArrayBox.java中的ArrayBox来实现这个Box接口就好

---

再来把LinkedBox的代码写了,以下代码都放在util包中：

Node.java

先把双向链表的数据结构定义了

package util;public class Node {private Node prev;//上一个Node对象private int item;  //当前的数据private Node next;//下一个Node对象public Node(Node prev,int element,Node next){this.item = element;this.next = next;this.prev = prev;}public int getItem() {return item;}public Node getNext() {return next;}public Node getPrev() {return prev;}public void setItem(int item) {this.item = item;}public void setNext(Node next) {this.next = next;}public void setPrev(Node prev) {this.prev = prev;}
}

LinkedBox.java

package util;public class LinkedBox implements Box{//先定义头节点和尾节点的属性private Node first;private Node last;private int size = 0;//记录有效元素的个数//1.增加元素的方法public boolean add(int element) {//将element元素存入一个新的node里，挂在链表的尾端//      调用linkLast方法this.linkLast(element);//告知添加成功return true;}private void linkLast(int element){ //将element元素存入一个新的node里，挂在链表的尾端//获取链表的尾节点Node l = last;//创建一个新的Node对象，将新数据包装起来Node newNode = new Node(l,element,null);//再将新节点设置为尾节点last = newNode;if(l == null){first = newNode;}else{l.setNext(newNode);}//有效元素增加一个size++;}//2.获取元素的方法public int get(int index) {//调用一个方法，先检验index是否合法this.rangeCheck(index);//找寻index对应位置的那个Node对象，将对象中的数据据取出来//调用node方法Node targetNode = this.node(index);//返回index位置的值return targetNode.getItem();}private void rangeCheck(int index){       //检验index是否合法if(index < 0 || index > this.size){//参考数组的操作，自己定义一个异常（自己创建的类）来说明这个问题throw new BoxIndexOutOfBoundsException("index:" + index + ",Size" + size);}}private Node node(int index){  //找寻index对应位置的那个Node对象，将对象中的数据据取出来Node targetNode;//用来存储当前目标元素的对象if(index < (index>>1)){targetNode = first;for(int i = 0; i < index; i++){targetNode = targetNode.getNext();}}else{targetNode = last;for(int i = size-1; i > index; i--){targetNode = targetNode.getPrev();}}return targetNode;}//3.删除元素的方法public int remove(int index) {//检测index是否合法this.rangeCheck(index);//找到index位置的那个Node//调用node方法Node targetNode = this.node(index);//将要删除的元素保存下来，返回给用户int oldValue = targetNode.getItem();//删除当前元素的目标节点//调用this.unLink(targetNode);//有效元素减少一个size--;//返回被删元素return oldValue;}private void unLink(Node targetNode){if(targetNode.getPrev() == null){first = targetNode.getNext();}else{targetNode.getPrev().setNext(targetNode.getNext());}if(targetNode.getNext() == null){last = targetNode.getNext();}else{targetNode.getNext().setPrev(targetNode.getPrev());}targetNode.setNext(null);targetNode.setPrev(null);}//4.获取元素个数的方法public int size() {return this.size;}
}

BoxIndexOutOfBoundsException.java

package util;public class BoxIndexOutOfBoundsException extends RuntimeException{public BoxIndexOutOfBoundsException(){}public BoxIndexOutOfBoundsException(String msg){super(msg);//msg提供给父类}
}