带头结点的单链表类
//带头结点的单链表类//建议，不声明成员变量rear和n，不安全，维护困难，子类需要同时修改3个成员变量，易出错。package dataStructure.linearList;import dataStructure.linearList.Node; //导入单链表结点类import java.util.Iterator; //导入迭代器接口public class HSLinkedList<E> extends AbstractList<E> implements LList<E> //带头结点的单链表类，实现线性表接口{ protected Node<E> head; //头指针，指向单链表的头结点 protected Node<E> rear; //尾指针，指向单链表最后一个结点 protected int n; //单链表长度 public HSLinkedList() //构造空链表 { this.head = new Node<E>(); //创建头结点，值为null this.rear = this.head; this.n=0; } public boolean isEmpty() //判断单链表是否为空，O(1) { return this.head.next==null; } public int length() //返回单链表长度，O(1) { return this.n; } public E get(int index) //返回序号为index的对象，index初值为0 { //若单链表空或序号错误返回null，O(n) if (index>=0) { int j=0; Node<E> p=this.head.next; while (p!=null && j<index) { j++; p = p.next; } if (p!=null) return (E)p.data; } return null; } public E set(int index, E element) //设置序号为index的对象为element，O(n) { //若操作成功返回原对象，否则返回null if (index>=0 && element!=null) { int j=0; Node<E> p=this.head.next; while (p!=null && j<index) { j++; p = p.next; } if (p!=null) { E old = (E)p.data; p.data = element; return old; //若操作成功返回原对象 } } return null; //操作不成功 } public boolean add(E element) //在单链表最后添加对象，O(1) { if (element==null) return false; this.rear.next = new Node<E>(element); //尾插入 this.rear = this.rear.next; //移动尾指针 this.n++; return true; } public boolean add(int index, E element) //在指定位置插入非空的指定对象 { //若操作成功返回true，O(n) if (element==null) return false; if (index>=this.n) return this.add(element); //插入在最后 else { int j=0; Node<E> p = this.head; while (p.next!=null && j<index) //若index<=0，插入在头结点之后 { j++; p = p.next; } p.next=new Node<E>(element, p.next); //插入在p结点之后，包括头插入、中间插入 this.n++; return true; } } public E remove(int index) //移去index位置的对象，O(n) { //若操作成功返回被移去对象，否则返回null E old = null; if (index>=0) //头删除、中间/尾删除 { int j=0; Node<E> p=this.head; while (p.next!=null && j<index) //定位到待删除结点的前驱结点 { j++; p = p.next; } if (p.next!=null) { old = (E)p.next.data; if (p.next==this.rear) this.rear=p; p.next = p.next.next; //删除p的后继结点 this.n--; } } return old; } public void clear() //清空单链表，O(1) { this.head.next = null; this.rear = this.head; this.n=0; } public String toString() //返回显示单链表所有元素值对应的字符串 { //单链表遍历算法，O(n) String str="("; Node<E> p = this.head.next; while (p!=null) { str += p.data.toString(); p = p.next; if (p!=null) str += ", "; } return str+")"; } //以上实现LList接口 public Iterator<E> iterator() //返回一个迭代器对象 { return new Itr(); } private class Itr implements Iterator<E> //私有内部类，实现迭代器接口 { private Node<E> cursor = head.next; public boolean hasNext() //若有后继元素，返回true { return cursor!=null && cursor.next!=null; } public E next() //返回后继元素 { if (cursor != null && cursor.next!=null) { E element = cursor.next.data; cursor = cursor.next; return element; } return null; } public void remove() //不支持该操作 { throw new UnsupportedOperationException(); } }//内部类Itr结束 public static void main(String args[]) { HSLinkedList<String> list = new HSLinkedList<String>(); for (int i=5; i>=0; i--) list.add(0,new String((char)('A'+i)+"")); System.out.println(list.toString()); }}/*程序运行结果如下： (A, B, C, D, E, F)*/?