データ構造--ヘッドレス一方向非循環チェーンの実現

2529 ワード

無頭一方向非循環リンク表:構造が簡単で、データを単独で保存することは一般的ではない.実際には他のデータ構造としてのサブ構造が多い.

//     
public interface ILinked {
    //   
    void addFirst(int data);
    //   
    void addLast(int data);
    //      ,        0   
    boolean addindex(int index,int data);
    //         key        
    boolean contains(int key);
    //           key   
    int remove(int key);
    //      key   
    void removeAllKey(int key);
    //        
    int getLength();
    //    
    void display();
    //    
    void clear();
}

上のインターフェースを実現します.

public class ILinkedImpl implements ILinked {

//    Node 
    class Node {
        private int data;
        private Node next;

//     
        public Node(int data){
            this.data=data;
            this.next=null;
        }
    }

    private Node head;

    public ILinkedImpl(){
        this.head=null;
    }

//----------------------------------------------
    //   
    @Override
    public void addFirst(int data) {
        Node node=new Node(data);
        if(this.head==null){
            this.head=node;
        }else{
            node.next=this.head;
            this.head=node;
        }
    }
    
    //------------------------------------------

    //   
    @Override
    public void addLast(int data) {
        Node node=new Node(data);
        Node cur=this.head;
       if(this.head==null){
           this.head=node;
       }else{
           while(cur.next!=null){
               cur=cur.next;
           }
           cur.next=node;
       }
    }

  //------------------------------------------

    //      ,        0   
    //     index    
    public void checkindex(int index){
        if(index>getLength()||index<0){
            throw new UnsupportedOperationException("index    ");
        }
    }
    //  index-1   
    public Node indexbefore(int index){
        checkindex(index);
        Node cur=this.head;
        int count=0;
        if(index==0){
            return null;
        }
        while(cur.next!=null && count

Link単端リンク表