列表分为三种类型:a.有序列表(其元素按照元素的某种内在特性进行排序) b.无序列表(元素不存在内在顺序,按照它们在列表中的位置进行排序) c.索引列表(其元素可以用数字索引来引用)
这里主要实现有序和无序两种列表:
两种列表的共有操作:
package xidian.sl.list; import java.util.Iterator; import xidian.sl.stack.EmptyCollectionException; import xidian.sl.tree.ElementNotFoundException; /** * 有序列表与无序列表的公共接口 * */ public interface ListADT<T> { /*从列表中删除第一个元素*/ public T removeFirst() throws ElementNotFoundException; /*从列表中删除最后一个元素*/ public T removeLast() throws ElementNotFoundException; /*从列表中删除一个特定元素*/ public T remove(T element) throws ElementNotFoundException, EmptyCollectionException; /*检查列表的第一个元素*/ public T first() throws ElementNotFoundException; /*检查列表的最后一个元素*/ public T last() throws ElementNotFoundException; /*确定列表中是否包含某个特殊元素*/ public boolean contains(T element); /*确定列表是否为空*/ public boolean isEmpty(); /*确定列表中元素的个数*/ public int size(); /*返回该列表的迭代*/ public Iterator<T> iterator(); /*重写toString方法*/ public String toString(); }
有序列表的特有操作:
package xidian.sl.list; /** * 有序列表特有的操作接口 * */ public interface OrderedListADT<T> extends ListADT<T>{ /*向列表中添加一个元素*/ public void add(T element); }
无序列表的特有操作:
package xidian.sl.list; import xidian.sl.tree.ElementNotFoundException; /** * 无序列表特有的操作接口 * */ public interface UnorderedListADT<T> extends ListADT<T>{ /*添加一个元素到列表头*/ public void addToFront(T element); /*添加一个元素到列表尾*/ public void addToRear(T element); /*添加一个元素到列表中某个特定元素之后*/ public void addAfter(T element, T target) throws ElementNotFoundException; }
以下我们还是使用两种方式来实现列表(数组与链表)
1.使用数组实现列表:
共有操作的实现:
package xidian.sl.list; import java.util.Iterator; import xidian.sl.tree.ElementNotFoundException; /** * 利用数组来实现 * */ public class ArrayList<T> implements ListADT<T>{ //默认初始数组大小 private final int DEFAULT_CAPACITY = 100; //未找个指定元素的返回常量 private final int NOT_FOUNND = -1; //表示了列表中的元素数目,以及把元素添加到列表末端时的下一个可用位置 protected int rear; protected T[] list; @SuppressWarnings("unchecked") public ArrayList(){ rear = 0; list = (T[]) new Object[DEFAULT_CAPACITY]; } @SuppressWarnings("unchecked") public ArrayList(int initialCapacity){ rear = 0; list = (T[]) new Object[initialCapacity]; } @Override public boolean contains(T element) { int index = find(element); return index != NOT_FOUNND; } @Override public T first() throws ElementNotFoundException { if(isEmpty()){ throw new ElementNotFoundException("list"); } return list[0]; } @Override public boolean isEmpty() { return rear == 0? true : false; } /** * 这里为了重用代码,我们专门为列表的数组实现创建一个iterator方法。但是,我们创建了一个通用的ArrayIterator类, * 它可以与任何集合的数组实现一起工作 * */ @SuppressWarnings("unchecked") public Iterator<T> iterator() { return new ArrayIterator<T>(list, rear); } @Override public T last() throws ElementNotFoundException { if(isEmpty()){ throw new ElementNotFoundException("list"); } return list[rear-1]; } /** * remove操作要求我们查找作为参数传递的元素,如果找到就从列表中进行删除, * 然后将数组中更高索引位的元素向下平移以填补空隙 * @throws ElementNotFoundException * * */ public T remove(T element) throws ElementNotFoundException { T result; int index = find(element); if(index == NOT_FOUNND){ throw new ElementNotFoundException("list"); } result = list[index]; rear--; for(int scan = index; scan < rear; scan++){ list[scan] = list[scan+1]; } list[rear] = null; return result; } /** * find方法用于查找指定元素,如果在列表中则返回该元素的索引,如果列表中不存在该元素,则返回一个名为NOT_FOUNND的常量 * */ private int find(T target){ int scan = 0, result = NOT_FOUNND; boolean found = false; if(!isEmpty()){ while(!found && scan < rear){ if(target.equals(list[scan])){ found = true; }else{ scan++; } } } //如果存在则返回该元素的索引 if(found){ result = scan; } return result; } @Override public T removeFirst() throws ElementNotFoundException { T result; if(isEmpty()){ throw new ElementNotFoundException("list"); } result = list[0]; rear--; for(int scan = 0; scan < rear; scan++){ list[scan] = list[scan+1]; } list[rear] = null; return result; } @Override public T removeLast() throws ElementNotFoundException { T result; if(isEmpty()){ throw new ElementNotFoundException("list"); } result = list[rear-1]; rear--; list[rear] = null; return result; } @Override public int size() { return rear; } /*扩容是将数组的大小进行加倍*/ @SuppressWarnings("unchecked") protected void expandCapacity(){ T[] larger = (T[])(new Object[list.length*2]); for(int index = 0; index< list.length; index++){ larger[index] = list[index]; //把原数组的内容复制到新数组中 } list = larger; } }
以上涉及到的ArrayIterator类:
package xidian.sl.list; import java.util.Iterator; import java.util.NoSuchElementException; @SuppressWarnings("unchecked") public class ArrayIterator<T> implements Iterator{ //记录集合中的元素数目 private int count; //记录迭代的位置 private int current; //需要迭代的集合 private T[] items; public ArrayIterator(T[] collection, int size){ items = collection; count = size; current = 0; } @Override public boolean hasNext() { return (current < count); } @Override public Object next() { if(!hasNext()){ throw new NoSuchElementException(); } current++; return items[current-1]; } @Override public void remove() { throw new UnsupportedOperationException(); } }
有序列表实现:
package xidian.sl.list; /** * 有序列表的实现 * */ public class ArrayOrderedList<T> extends ArrayList<T> implements OrderedListADT<T>{ /** * add操作时将一个元素添加到有序列表的唯一方式。调用中没有指定添加到的位置,因为元素本身就决定了它们的次序。 * 与remove操作类似,add操作也需要比较和平移操作:进行比较以找到元素在列表中的正确位置,然后平移元素以便为 * 新元素腾出一个位置。并且每次add操作时需要进行n次比较和平移操作(如果操作时第一个元素,则需1次比较,n-1次 * 平移,如果是最后一个元素,则需n次比较0次平移) * */ @SuppressWarnings("unchecked") @Override public void add(T element) { //首先查看列表大小,必须时进行扩容 if(size() == list.length){ expandCapacity(); } //将元素转化为Comparable对象 Comparable<T> temp = (Comparable<T>)element; //该元素与列表中的其他元素比较大小,选出插入位置 int scan = 0; while(scan < rear && temp.compareTo(list[scan]) > 0){ scan++; } //比插入位置索引值大的元素进行平移 for(int scan2 = rear; scan2 > scan; scan2--){ list[scan2] = list[scan2-1]; } //将该元素插入到列表 list[scan] = element; rear++; } }
无序列表实现:
package xidian.sl.list; import xidian.sl.tree.ElementNotFoundException; public class ArrayUnorderedList<T> extends ArrayList<T> implements UnorderedListADT<T>{ @Override public void addAfter(T element, T target) throws ElementNotFoundException { //首先查看列表大小,必须时进行扩容 if(size() == list.length){ expandCapacity(); } //查找应该插入的位置 int scan = 0; while(scan < rear && !target.equals(list[scan])){ scan++; } if(scan == rear){ throw new ElementNotFoundException("list"); } scan++; //平移 for(int scan2 = rear; scan2 > scan; scan2--){ list[scan2] = list[scan2-1]; } //将该元素插入到列表 list[scan] = element; rear++; } @Override public void addToFront(T element) { //首先查看列表大小,必须时进行扩容 if(size() == list.length){ expandCapacity(); } //对所有元素进行一次平移 for(int scan = rear; scan > 0; scan--){ list[scan] = list[scan-1]; } //将该元素插入到列表 list[0] = element; rear++; } @Override public void addToRear(T element) { //首先查看列表大小,必须时进行扩容 if(size() == list.length){ expandCapacity(); } //将该元素插入到列表 list[rear] = element; rear++; } }
2.使用链表实现列表(主要实现了remove方法)
package xidian.sl.list; import java.util.Iterator; import xidian.sl.stack.EmptyCollectionException; import xidian.sl.stack.LinearNode; import xidian.sl.tree.ElementNotFoundException; /** * 使用链表实现列表 * */ public class LinkedList<T> implements ListADT<T>{ protected int count; protected LinearNode<T> head, tail; public LinkedList(){ count = 0; head = tail = null; } @Override public boolean contains(T element) { return false; } @Override public T first() throws ElementNotFoundException { // TODO Auto-generated method stub return null; } @Override public boolean isEmpty() { return (count == 0); } @Override public Iterator<T> iterator() { return new LinkedIterator<T>(head, count); } @Override public T last() throws ElementNotFoundException { // TODO Auto-generated method stub return null; } /** * 利用单向链表来实现remove方法 * */ public T remove(T element) throws ElementNotFoundException, EmptyCollectionException { if(isEmpty()){ throw new EmptyCollectionException("list"); } boolean found = false; LinearNode<T> previous = null; LinearNode<T> current = head; while(current != null && !found){ if(element.equals(current.getElement())){ found = true; }else{ previous = current; current = current.getNext(); } } if(!found){ throw new ElementNotFoundException("list"); } if(size() == 1){ head = tail = null; }else if(current.equals(head)){ head = current.getNext(); }else if(current.equals(tail)){ tail = previous; tail.setNext(null); }else{ previous.setNext(current.getNext()); } count--; return current.getElement(); } @Override public T removeFirst() throws ElementNotFoundException { // TODO Auto-generated method stub return null; } @Override public T removeLast() throws ElementNotFoundException { // TODO Auto-generated method stub return null; } @Override public int size() { return count; } }
涉及到的LinkedIterator类:
package xidian.sl.list; import java.util.Iterator; import java.util.NoSuchElementException; import xidian.sl.stack.LinearNode; public class LinkedIterator<T> implements Iterator<T>{ private int count; private LinearNode<T> current; public LinkedIterator(LinearNode<T> collection, int size){ current = collection; count = size; } @Override public boolean hasNext() { return (current != null); } @Override public T next() { if(! hasNext()){ throw new NoSuchElementException(); } T result = current.getElement(); current = current.getNext(); return result; } @Override public void remove() { // TODO Auto-generated method stub throw new UnsupportedOperationException(); } }
下面我来介绍一下那个双向链表(存储着上一节点的引用和下一节点的引用),以前我们实现集合都是使用的是单向列表(只存储下一个节点的引用,)
package xidian.sl.list; /** * 双向链表:存储着上一节点的引用和下一节点的引用 * */ public class DoubleNode<T> { private DoubleNode<T> next; private T element; private DoubleNode<T> previous; public DoubleNode(){ next = null; element = null; previous = null; } public DoubleNode(T ele){ next = null; element = ele; previous = null; } public DoubleNode<T> getNext() { return next; } public void setNext(DoubleNode<T> next) { this.next = next; } public T getElement() { return element; } public void setElement(T element) { this.element = element; } public DoubleNode<T> getPrevious() { return previous; } public void setPrevious(DoubleNode<T> previous) { this.previous = previous; } }
列表的应用:组织赛程: