/**
* 自定義鏈表
*/
public interface CustomizeList<E> extends Collection<E> {
? ?//先自定義List接口，增加使用索引的方法
? ?E remove(int index);
? ?E set(int index,E e);
? ?E get(int index);
}

class CustomizeOneWayLinkedList<E> implements CustomizeList<E>{
? ?//自定義單向鏈表

? ?private static final class Node<E> {
? ? ? ?//結(jié)點 內(nèi)部類
? ? ? ?E item;
? ? ? ?Node<E> next;
? ? ? ?//單向鏈表只有直接后繼結(jié)點一個指針
? ? ? ?public Node(E item, Node<E> next) {
? ? ? ? ? ?this.item = item;
? ? ? ? ? ?this.next = next;
? ? ? ?}
? ?}

? ?private Node<E> first;
? ?private int size;

? ?private void indexCheck(int index){
? ? ? ?//執(zhí)行需要索引的方法時都先進行索引檢查
? ? ? ?if (index<0||index>=size) throw new IndexOutOfBoundsException("index:"+index+" size:"+size);
? ? ? ?//對現(xiàn)有結(jié)點進行操作時范圍為[0,size)，執(zhí)行插入操作時范圍為[0,size]
? ?}

? ?private Node<E> getNode(int index){
? ? ? ?Node<E> n = first;
? ? ? ?for (int i = 0;i<index;i++){
? ? ? ? ? ?n = n.next;
? ? ? ?}
? ? ? ?return n;
? ?}

? ?@Override
? ?public E remove(int index) {
? ? ? ?indexCheck(index);
? ? ? ?//先進行索引檢查，包括空容器index=0時也會報索引越界，所以能通過檢查說明容器內(nèi)有元素
? ? ? ?Node<E> temp;
? ? ? ?if (index==0){
? ? ? ? ? ?//單向鏈表的刪除結(jié)點是將前驅(qū)結(jié)點跳過當前結(jié)點鏈到后繼結(jié)點上，所以先要判斷是否存在前驅(qū)結(jié)點，單向鏈表沒有prev屬性，只能用index-1來調(diào)用，當index=0時-1會報錯，所以要單獨判斷
? ? ? ? ? ?temp = first;
? ? ? ? ? ?first = first.next;
? ? ? ?}else {
? ? ? ? ? ?Node<E> prev = getNode(index-1);
? ? ? ? ? ?temp = prev.next;
? ? ? ? ? ?prev.next = temp.next;
? ? ? ?}
? ? ? ?//用temp緩存要刪除的結(jié)點
? ? ? ?E e = temp.item;
? ? ? ?temp.item = null;
? ? ? ?temp.next = null;
? ? ? ?size--;
? ? ? ?return e;
? ?}

? ?@Override
? ?public E set(int index, E e) {
? ? ? ?indexCheck(index);
? ? ? ?Node<E> n = getNode(index);
? ? ? ?E oldE = n.item;
? ? ? ?n.item = e;
? ? ? ?return oldE;
? ?}

? ?@Override
? ?public E get(int index) {
? ? ? ?indexCheck(index);
? ? ? ?return getNode(index).item;
? ?}

? ?@Override
? ?public int size() {
? ? ? ?return size;
? ?}

? ?@Override
? ?public boolean isEmpty() {
? ? ? ?return size==0;
? ?}

? ?public int indexOf(Object o){
? ? ? ?if (o==null)return -1;
? ? ? ?Node<E> n = first;
? ? ? ?for (int i = 0 ;i<size;i++,n = n.next){
? ? ? ? ? ?//size=0時不執(zhí)行循環(huán)
? ? ? ? ? ?if (o.equals(n.item))return i;
? ? ? ?}
? ? ? ?return ?-1;
? ?}

? ?@Override
? ?public boolean contains(Object o) {
? ? ? ?return indexOf(o)!=-1;
? ?}

? ?@Override
? ?public Iterator<E> iterator() {
? ? ? ?return new Iterator<E>() {
? ? ? ? ? ?//匿名內(nèi)部類
? ? ? ? ? ?int next = -1;
? ? ? ? ? ?int cursor = 0;
? ? ? ? ? ?@Override
? ? ? ? ? ?public boolean hasNext() {
? ? ? ? ? ? ? ?return cursor!=size;
? ? ? ? ? ?}

? ? ? ? ? ?@Override
? ? ? ? ? ?public E next() {
? ? ? ? ? ? ? ?next = cursor++;
? ? ? ? ? ? ? ?return CustomizeOneWayLinkedList.this.get(next);
? ? ? ? ? ?}

? ? ? ? ? ?@Override
? ? ? ? ? ?public void remove() {
? ? ? ? ? ? ? ?CustomizeOneWayLinkedList.this.remove(next);
? ? ? ? ? ? ? ?//外部類的remove方法中已經(jīng)size--了
? ? ? ? ? ? ? ?next = -1;
? ? ? ? ? ? ? ?//將next變?yōu)?1，禁止連續(xù)刪除
? ? ? ? ? ? ? ?cursor--;
? ? ? ? ? ?}
? ? ? ?};
? ?}

? ?@Override
? ?public Object[] toArray() {
? ? ? ?Object[] o = new Object[size];
? ? ? ?Node<E> n = first;
? ? ? ?for (int i = 0;i<size;i++,n = n.next){
? ? ? ? ? ?o[i] = n.item;
? ? ? ?}
? ? ? ?return o;
? ?}

? ?@Override
? ?public <T> T[] toArray(T[] a) {
? ? ? ?if (a.length<size) {
? ? ? ? ? ?a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
? ? ? ? ? ?//Array類的方法.newInstance(Class<T>,int)生成一個新的數(shù)組，數(shù)組類型為T[],將新數(shù)組作為Object對象返回，所以需要對返回值強轉(zhuǎn)回T[]
? ? ? ? ? ?//.getClass()返回對象的類的類對象Class<T[]> ? .getComponentType()返回數(shù)組類對象的組成成分/元素的類對象Class<T>
? ? ? ?}
? ? ? ?Node<E> n = first;
? ? ? ?for (int i = 0; i < size; i++, n = n.next) {
? ? ? ? ? ?a[i] = (T) n.item;
? ? ? ?}
? ? ? ?if (a.length>size){
? ? ? ? ? ?a[size] = null;
? ? ? ?}
? ? ? ?return a;
? ?}

? ?@Override
? ?public boolean add(E e) {
? ? ? ?if (isEmpty()) {
? ? ? ? ? ?first = new Node<>(e, null);
? ? ? ?}else {
? ? ? ? ? ?getNode(size-1).next = new Node<>(e,null);
? ? ? ? ? ?//將結(jié)點鏈至表尾
? ? ? ?}
? ? ? ?size++;
? ? ? ?return true;
? ?}


? ?@Override
? ?public boolean remove(Object o) {
? ? ? ?if (o==null)return false;
? ? ? ?Node<E> p = null;
? ? ? ?for (Node<E> m = first;m!=null;p=m,m=m.next){
? ? ? ? ? ?//first==null時不執(zhí)行循環(huán)
? ? ? ? ? ?if (o.equals(m.item)){
? ? ? ? ? ? ? ?if (p==null){
? ? ? ? ? ? ? ? ? ?//當m為first時p還沒有賦值，判斷p==null即判斷m==first
? ? ? ? ? ? ? ? ? ?first=first.next;
? ? ? ? ? ? ? ?}else {
? ? ? ? ? ? ? ? ? ?p.next = m.next;
? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ?m.item=null;
? ? ? ? ? ? ? ?m.next=null;
? ? ? ? ? ? ? ?size--;
? ? ? ? ? ? ? ?return true;
? ? ? ? ? ?}
? ? ? ?}
? ? ? ?return false;
? ?}

? ?@Override
? ?public boolean containsAll(Collection<?> c) {
? ? ? ?if (c==null||c.isEmpty()||isEmpty())return false;
? ? ? ?for (Object o :
? ? ? ? ? ? ? ?c) {
? ? ? ? ? ?if (!contains(o)) return false;
? ? ? ?}
? ? ? ?return true;
? ?}

? ?@Override
? ?public boolean addAll(Collection<? extends E> c) {
? ? ? ?//形參類型為Collection接口，只要元素同類或子類就可以使不同類型的容器取并集
? ? ? ?if (c==null||c.isEmpty())return false;
? ? ? ?Node<E> n;
? ? ? ?Iterator<? extends E> itr = c.iterator();
? ? ? ?//使用迭代器來添加
? ? ? ?if (isEmpty()){
? ? ? ? ? ?first = new Node<>(itr.next(),null);
? ? ? ? ? ?n = first;
? ? ? ?}else {
? ? ? ? ? ?n = getNode(size-1);
? ? ? ? ? ?//要調(diào)用size-1所以需要單獨處理size=0的情況
? ? ? ?}
? ? ? ?while (itr.hasNext()){
? ? ? ? ? ?n.next = new Node<>(itr.next(),null);
? ? ? ? ? ?//將元素從原容器中取出封入新的結(jié)點中添加至表尾
? ? ? ? ? ?n = n.next;
? ? ? ?}
? ? ? ?size += c.size();
? ? ? ?return true;
? ?}

? ?@Override
? ?public boolean removeAll(Collection<?> c) {
? ? ? ?if (c == null||c.isEmpty()||isEmpty())return false;
? ? ? ?boolean modified = false;
? ? ? ?for (Object o :
? ? ? ? ? ? ? ?c) {
? ? ? ? ? ?while (remove(o)) {
? ? ? ? ? ? ? ?//remove()方法中已經(jīng)將size--了，這里不需要再次修改size
? ? ? ? ? ? ? ?modified = true;
? ? ? ? ? ?}
? ? ? ?}
? ? ? ?return modified;
? ?}

? ?@Override
? ?public boolean retainAll(Collection<?> c) {
? ? ? ?if (c==null||c.isEmpty()||isEmpty())return false;
? ? ? ?boolean modified = false;
? ? ? ?for (Iterator<E> it = iterator();it.hasNext();){
? ? ? ? ? ?if (!c.contains(it.next())) {
? ? ? ? ? ? ? ?it.remove();
? ? ? ? ? ? ? ?modified = true;
? ? ? ? ? ?}
? ? ? ?}
? ? ? ?return modified;
? ?}

? ?@Override
? ?public void clear() {
? ? ? ?for (Node<E> n = first;first!=null;n =first){
? ? ? ? ? ?first = first.next;
? ? ? ? ? ?n.item = null;
? ? ? ? ? ?n.next = null;
? ? ? ?}
? ? ? ?size =0;
? ?}

? ?@Override
? ?public String toString() {
? ? ? ?if (isEmpty())return "[]";
? ? ? ?StringBuilder str = new StringBuilder("[");
? ? ? ?for (Node<E> n = first;;){
? ? ? ? ? ?//循環(huán)條件空著為死循環(huán)，迭代因子放在語句內(nèi)
? ? ? ? ? ?str.append(n.item);
? ? ? ? ? ?n=n.next;
? ? ? ? ? ?if (n==null){
? ? ? ? ? ? ? ?return str.append("]").toString();
? ? ? ? ? ?}
? ? ? ? ? ?str.append(", ");
? ? ? ?}
? ?}

? ?//單向鏈表實現(xiàn)棧容器方法
? ?public boolean empty(){
? ? ? ?return first==null;
? ?}
? ?public E pop(){
? ? ? ?if (empty()){
? ? ? ? ? ?return null;
? ? ? ?}
? ? ? ?Node<E> n = first;
? ? ? ?first = first.next;
? ? ? ?E e = n.item;
? ? ? ?n.item = null;
? ? ? ?n.next = null;
? ? ? ?size--;
? ? ? ?return e;
? ?}
? ?public E peek(){
? ? ? ?return empty()?null:first.item;
? ?}
? ?public void push(E e){
? ? ? ?first = new Node<>(e,first);
? ? ? ?size++;
? ?}
? ?public int search(E e){
? ? ? ?if (empty()||e==null)return -1;
? ? ? ?int i = 1;
? ? ? ?for (Node<E> n = first;n!=null;n = n.next){
? ? ? ? ? ?if (e.equals(n.item))return i;
? ? ? ? ? ?i++;
? ? ? ?}
? ? ? ?return -1;
? ?}


? ?public static void main(String[] args) {
? ? ? ?CustomizeOneWayLinkedList<String> ll1 = new CustomizeOneWayLinkedList<>();
? ? ? ?CustomizeOneWayLinkedList<String> ll2 = new CustomizeOneWayLinkedList<>();
? ? ? ?//測試略
? ?}
}