java实现链接表

链接表：     1、基于节点的操作：在前面的对线性表抽象数据类型的操作中，其提供的操作主要是对线性表中的数据元素及其序号的。例如插入操作就是基于序号和元素进行的insert(int i,Object e); 是在序号为i的地方插入e,这种基于序号的操作实际上并不适合采用链表来实现，因为为了在链表中定位数据元素或序号，不得不沿着节点的引用，从链表前端开始扫描。它的时间复杂度O（n^2)。

定义链接表的接口：

package 线性表.lianjiebiao; import 线性表.iterator.Iterator; import 线性表.linkedlist.Node; import 线性表.sunxu.OutOfBoundaryException; /** * 链接表接口的定义 * @author acer */ public interface LinkedList { //查询链接表当前的规模 public int getSize(); //判断列表是否为空 public boolean isEmpty(); //返回第一个节点 public Node first() throws OutOfBoundaryException; //返回最后一个节点 public Node last() throws OutOfBoundaryException; //返回p之后的节点 public Node getNext(Node p) throws OutOfBoundaryException; //返回p之前的节点 public Node getPre(Node p) throws OutOfBoundaryException; //将e作为第一个元素插入链接表，并返回e所在的节点 public Node insertFirst(Object c); //将e作为最后一个元素插入链接表，并返回e所在的节点 public Node insertLast(Object c); //将e插入p之后的位置，并返回节点 public Node insertAfter(Node o,Object c); //将e插入p之前的位置，并返回节点 public Node insertBefore(Node o,Object c); //删除给定位置的元素，并返回 public Object remove(Node p); //删除首元素，并返回 public Object removeFirst(); //删除尾元素，并返回 public Object removeLast(); //将处于给定位置的元素替换为新元素，并返回被替换的元素 public Object replace(Node p,Object c); //元素迭代器 public Iterator elements() throws OutOfBoundaryException; } 定义他的异常：

package 线性表.lianjiebiao; /** * 定义节点的异常 * @author acer * 1.p == null 2.p在链接表中不存在 3.调用p.getPre(node p)时，p已经是第一个节点 4.调用p.getNext()时，p已经是最后一个节点 */ public class InvalidNodeException extends RuntimeException{ public InvalidNodeException(String err) { super(err); } } 链接表的节点：它是双向链表：

package 线性表.linkedlist; /** * 双向链表的实现结构 * @author acer */ public class DLNode implements Node{ private Object data;//数据域 private DLNode next;//后续节点 private DLNode pre;//前驱节点 public DLNode(){ } public DLNode(Object o,DLNode next,DLNode pre) { this.data = o; this.next = next; this.pre = pre; } public DLNode getNext() { return next; } public void setNext(DLNode next) { this.next = next; } public DLNode getPre() { return pre; } public void setPre(DLNode pre) { this.pre = pre; } @Override public Object getData() { // TODO Auto-generated method stub return null; } @Override public void setData(Object o) { // TODO Auto-generated method stub } } 链接表的实现类：

package 线性表.lianjiebiao; import 线性表.iterator.Iterator; import 线性表.iterator.LinkedListIterator; import 线性表.linkedlist.DLNode; import 线性表.linkedlist.Node; import 线性表.sunxu.OutOfBoundaryException; /** * 基于双向链表实现的链接表 * @author acer */ public class LinkedListDLNode implements LinkedList{ private int size;//规模 private DLNode head;//头节点 private DLNode tail;//尾节点 public LinkedListDLNode() { size = 0; //构建只有头尾节点的链表 head = new DLNode(); tail = new DLNode(); head.setNext(tail); tail.setPre(head); } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return size == 0; } @Override public Node first() throws OutOfBoundaryException { if(isEmpty()) throw new OutOfBoundaryException("错误：链接表为空"); return head.getNext(); } @Override public Node last() throws OutOfBoundaryException { if(isEmpty()) throw new OutOfBoundaryException("错误：链接表为空"); return tail.getPre(); } @Override public Node getNext(Node p) throws OutOfBoundaryException { DLNode node = this.checkPosition(p); node = node.getNext(); if(node == tail) throw new OutOfBoundaryException("已经到达链表的尾段"); return node; } @Override public Node getPre(Node p) throws OutOfBoundaryException { DLNode node = this.checkPosition(p); node = node.getPre(); if(node == head) throw new OutOfBoundaryException("错误：已经到达链表的头部"); return node; } @Override public Node insertFirst(Object c) { DLNode node = new DLNode(c,head,head.getNext()); head.getNext().setPre(node); head.setNext(node); size ++; return node; } @Override public Node insertLast(Object c) { DLNode node = new DLNode(c,tail.getPre(),tail); tail.getPre().setNext(node); tail.setPre(node); size ++; return node; } @Override public Node insertAfter(Node o, Object c) { DLNode node = this.checkPosition(o); DLNode newNode = new DLNode(c,node,node.getNext()); node.setNext(newNode); node.getNext().setPre(newNode); size ++; return newNode; } @Override public Node insertBefore(Node o, Object c) { DLNode node = this.checkPosition(o); DLNode newNode = new DLNode(c,node.getPre(),node); node.setPre(newNode); node.getPre().setNext(newNode); size ++; return newNode; } @Override public Object remove(Node p) { DLNode node = this.checkPosition(p); node.getPre().setNext(node.getNext()); node.getNext().setPre(node.getPre()); size --; return node.getData(); } @Override public Object removeFirst() { return this.remove(head.getNext()); } @Override public Object removeLast() { // TODO Auto-generated method stub return this.remove(tail.getPre()); } @Override public Object replace(Node p, Object c) { DLNode node = (DLNode)p; Object o = node.getData(); node.setData(c); return o; } @Override public Iterator elements() throws OutOfBoundaryException { // TODO Auto-generated method stub return new LinkedListIterator(this); } //辅助方法，判断节点是否合法 protected DLNode checkPosition(Node p) throws InvalidNodeException{ if(p == null) throw new InvalidNodeException("错误：节点为空"); if(p == head) throw new InvalidNodeException("错误：指向头节点，非法"); if(p == tail) throw new InvalidNodeException("错误：指向尾节点，非法"); DLNode node = (DLNode)p; return node; } } 上面的实现类中应用到了迭代器：下面实现迭代器：

迭代器：     迭代器是程序设计的一种模式，它属于设计模式中的行为模式，它的功能是提供一种方法顺序访问一个聚集对象中的各个元素，而又不需要暴露该对象的内部实现。     多个对象聚集在一起形成的总体称之为聚集(Aggregate),聚集对象是能够包容一组对象的容器对象。聚集依赖于聚集结构的抽象化，具有复杂性和多样性。数组就是一组最基本的聚集。     聚集对象需要提供一种方法，允许用户按照一定的顺序访问其中所有元素。而迭代器提供了一个访问聚集对象中各个元素的统一接口，简单的说迭代器就是对遍历操作的抽象。     

    迭代器的实现可以根据不同的聚集对象给出不同的实现。

package 线性表.iterator; import 线性表.sunxu.OutOfBoundaryException; /** * 迭代器的java接口 * @author acer */ public interface Iterator { //移动到第一个元素 public void first() throws OutOfBoundaryException; //移动到下一个元素 public void next() throws OutOfBoundaryException; //检查迭代器中是否还有剩余元素 public boolean isDone(); //返回当前元素 public Object currentItem(); } 迭代器的实现：

package 线性表.iterator; import 线性表.lianjiebiao.*; import 线性表.linkedlist.Node; import 线性表.sunxu.OutOfBoundaryException; public class LinkedListIterator implements Iterator{ private LinkedList list;//链接表 private Node current;//当前节点 public LinkedListIterator(LinkedList list) throws OutOfBoundaryException { this.list = list; if(list.isEmpty()) current = null; current = list.first(); } @Override public void first() throws OutOfBoundaryException { if(list.isEmpty()) current = null; current = list.first(); } @Override public void next() throws OutOfBoundaryException { if(isDone()) throw new OutOfBoundaryException("错误：已经没有元素"); if(current == list.last()) current = null; current = list.getNext(current); } @Override public boolean isDone() { return current == null; } @Override public Object currentItem() { return current.getData(); } } 以上便是链接表的实现，它的效率得到了极大的提高。