0001 /* 0002 * 基于双向链表实现列表结构 0003 */ 0004 0005 package dsa; 0006 0007 public class List_DLNode implements List { 0008 protected int numElem;//列表的实际规模 0009 protected DLNode header, trailer;//哨兵:首节点+末节点 0010 0011 //构造函数 0012 public List_DLNode() { 0013 numElem = 0;//空表 0014 header = new DLNode(null, null, null);//头节点 0015 trailer = new DLNode(null, header, null);//尾节点 0016 header.setNext(trailer);//头、尾节点相互链接 0017 } 0018 0019 /**************************** 辅助方法 ****************************/ 0020 //检查给定位置在列表中是否合法,若是,则将其转换为*DLNode 0021 protected DLNode checkPosition(Position p) throws ExceptionPositionInvalid { 0022 if (null == p) 0023 throw new ExceptionPositionInvalid("意外:传递给List_DLNode的位置是null"); 0024 if (header == p) 0025 throw new ExceptionPositionInvalid("意外:头节点哨兵位置非法"); 0026 if (trailer == p) 0027 throw new ExceptionPositionInvalid("意外:尾结点哨兵位置非法"); 0028 DLNode temp = (DLNode)p; 0029 return temp; 0030 } 0031 0032 /**************************** ADT方法 ****************************/ 0033 //查询列表当前的规模 0034 public int getSize() { return numElem; } 0035 0036 //判断列表是否为空 0037 public boolean isEmpty() { return (numElem == 0); } 0038 0039 //返回第一个元素(的位置) 0040 public Position first() throws ExceptionListEmpty { 0041 if (isEmpty()) 0042 throw new ExceptionListEmpty("意外:列表空"); 0043 return header.getNext(); 0044 } 0045 0046 //返回最后一个元素(的位置) 0047 public Position last() throws ExceptionListEmpty { 0048 if (isEmpty()) 0049 throw new ExceptionListEmpty("意外:列表空"); 0050 return trailer.getPrev(); 0051 } 0052 0053 //返回紧靠给定位置之前的元素(的位置) 0054 public Position getPrev(Position p) 0055 throws ExceptionPositionInvalid, ExceptionBoundaryViolation { 0056 DLNode v = checkPosition(p); 0057 DLNode prev = v.getPrev(); 0058 if (prev == header) 0059 throw new ExceptionBoundaryViolation("意外:企图越过列表前端"); 0060 return prev; 0061 } 0062 0063 //返回紧接给定位置之后的元素(的位置) 0064 public Position getNext(Position p) 0065 throws ExceptionPositionInvalid, ExceptionBoundaryViolation { 0066 DLNode v = checkPosition(p); 0067 DLNode next = v.getNext(); 0068 if (next == trailer) 0069 throw new ExceptionBoundaryViolation("意外:企图越过列表后端"); 0070 return next; 0071 } 0072 0073 //将e插入至紧靠给定位置之前的位置 0074 public Position insertBefore(Position p, Object element) 0075 throws ExceptionPositionInvalid { 0076 DLNode v = checkPosition(p); 0077 numElem++; 0078 DLNode newNode = new DLNode(element, v.getPrev(), v); 0079 v.getPrev().setNext(newNode); 0080 v.setPrev(newNode); 0081 return newNode; 0082 } 0083 0084 //将e插入至紧接给定位置之后的位置 0085 public Position insertAfter(Position p, Object element) 0086 throws ExceptionPositionInvalid { 0087 DLNode v = checkPosition(p); 0088 numElem++; 0089 DLNode newNode = new DLNode(element, v, v.getNext()); 0090 v.getNext().setPrev(newNode); 0091 v.setNext(newNode); 0092 return newNode; 0093 } 0094 0095 //将e作为第一个元素插入列表 0096 public Position insertFirst(Object e) { 0097 numElem++; 0098 DLNode newNode = new DLNode(e, header, header.getNext()); 0099 header.getNext().setPrev(newNode); 0100 header.setNext(newNode); 0101 return newNode; 0102 } 0103 0104 //将e作为最后一个元素插入列表 0105 public Position insertLast(Object e) { 0106 numElem++; 0107 DLNode newNode = new DLNode(e, trailer.getPrev(), trailer); 0108 if (null == trailer.getPrev()) System.out.println("!!!Prev of trailer is NULL!!!"); 0109 trailer.getPrev().setNext(newNode); 0110 trailer.setPrev(newNode); 0111 return newNode; 0112 } 0113 0114 //删除给定位置处的元素,并返回之 0115 public Object remove(Position p) 0116 throws ExceptionPositionInvalid { 0117 DLNode v = checkPosition(p); 0118 numElem--; 0119 DLNode vPrev = v.getPrev(); 0120 DLNode vNext = v.getNext(); 0121 vPrev.setNext(vNext); 0122 vNext.setPrev(vPrev); 0123 Object vElem = v.getElem(); 0124 //将该位置(节点)从列表中摘出,以便系统回收其占用的空间 0125 v.setNext(null); 0126 v.setPrev(null); 0127 return vElem; 0128 } 0129 0130 //删除首元素,并返回之 0131 public Object removeFirst() 0132 { return remove(header.getNext()); } 0133 0134 //删除末元素,并返回之 0135 public Object removeLast() 0136 { return remove(trailer.getPrev()); } 0137 0138 //将处于给定位置的元素替换为新元素,并返回被替换的元素 0139 public Object replace(Position p, Object obj) 0140 throws ExceptionPositionInvalid { 0141 DLNode v = checkPosition(p); 0142 Object oldElem = v.getElem(); 0143 v.setElem(obj); 0144 return oldElem; 0145 } 0146 0147 //位置迭代器 0148 public Iterator positions() 0149 { return new IteratorPosition(this); } 0150 0151 //元素迭代器 0152 public Iterator elements() 0153 { return new IteratorElement(this); } 0154 }