3:Bagシングルチェーンテーブル実装


1:シンプルなシングルチェーンテーブル
配列ベースではありません
 
  
package com.algorithm.common;

import java.util.Iterator;

/**
 *   ( )
 * @author lijunqing
 */
public class Bag<Item> implements Iterable<Item> {

    private int N;

    private Node first;

    private class Node {

        private Item item;

        private Node next;
    }

    public Bag() {
        N=0;
        first=null;
    }

    public boolean isEmpty() {
        if(N == 0) {
            return true;
        }
        return false;
    }
    
    /**
     *  add 
     * @param item
     */
    public void add(Item item) {
        Node oldFirst = first;
        first = new Node();
        first.item = item;
        first.next = oldFirst;
        N++;
    }

    private class ListIterator implements Iterator<Item> {

        private Node current=first;

        @Override
        public boolean hasNext() {
            return current != null;
        }

        @Override
        public Item next() {
            Item item=current.item;
            current=current.next;
            return item;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }
    
    public static void main(String[] agrs){
        Bag<String> b = new Bag<String>();
        b.add("dd");
        b.add("11");
        b.add("dd");
        b.add("23");
        
        Iterator<String> i = b.iterator();
        while(i.hasNext()){
            System.out.println(i.next());
        }
        
    }

    @Override
    public Iterator<Item> iterator() {
        return new ListIterator();
    }

}

 
リストと区別:リストの追加順序と読み出し順序は同じです