데이터 구조 - Simple List 의 실현

이 SimepleList 는 가장 간단 한 배열 로 이 루어 진 시계 이다.표 라 는 구조의 특징 을 잘 표현 하기 위해 int 형 배열 만 저장 하 는 형식 입 니 다.또한 범 형, 인터페이스 등 체 제 를 결합 하여 더욱 높 은 차원 의 추상 적 인 처 리 를 하지 않 았 지만 앞으로 저 는 이 를 바탕 으로 JDK 의 Array List 류 와 유사 한 데이터 구 조 를 만 들 것 입 니 다.
이 Simple List 는 주로 다음 과 같은 기능 점 과 관련된다.

테이블 만 들 기;

리 셋 표;

조회 표 의 데이터 요소 갯 수;

위치 x 에 데이터 요 소 를 삽입 합 니 다.

위치 x 의 데이터 요 소 를 삭제 합 니 다.

끝부분 에 데이터 요 소 를 추가 합 니 다.

위치 x 의 요소 값 을 수정 합 니 다.

위치 x 의 요소 값 가 져 오기;

표 가 빈 표 인지 판단 한다.

표 가 가득 찼 는 지 판단 한다.

배열 의 현재 모든 요 소 를 출력 합 니 다.

속성

public static int DEFAULT_CAPACITY: 기본 테이블 크기

private int size: 표 의 요소 갯 수

private int [] elements: 요소 배열

구조 기
모두 두 개의 구조 기 가 있 는데 하 나 는 기본 용기 크기 로 표를 만 들 고 하 나 는 사용자 정의 크기 를 사용 합 니 다.clear () 와 init () 함수 기능 이 나타 나 면 구성원 변 수 를 초기 화 하 는 데 사 용 됩 니 다.

public SimpleList(){
    clear();
}

public SimpleList(int size){
    size = 0;
    init(size);
}

함수.
inti () 요소 배열 을 초기 화 합 니 다.

public void init(int capacity){
    elements = new int[capacity];
}

clear () 함수 가 기본 구조 함수 로 표 의 상 태 를 초기 화 합 니 다.

public void clear(){
    size = 0;
    init(DEFAULT_CAPACITY);
}

다음은 전형 적 인 코드 구현 기능 이다.

public int size(){return size;}
public boolean isEmpty(){
    return size == 0 ? true : false;
}
public boolean isFull(){
    return size() == elements.length ? true : false;
}

insert () 는 지정 한 위치 idx 에 요 소 를 삽입 합 니 다. idx 의 수치 범 위 는 0 ~ size 입 니 다. idx 는 size 이 고 꼬리 에 요 소 를 삽입 합 니 다. 나머지 는 idx 위치의 앞 에 요 소 를 삽입 합 니 다.삽입 작업 에서 그 비용 은 비교적 비싸다.요 소 를 삽입 할 때 요소 의 이동 과 관련 되 기 때문이다.최 악의 경우 머리 에 요 소 를 삽입 하면 원래 의 모든 요 소 를 한 자리 뒤로 옮 겨 야 한다. 이 함수 의 시간 복잡 도 는 선형 으로 증가한다.

public boolean insert(int idx, int ele){
    /*     */
    if(isFull())
        return false;
    /*        pos     ,= =,          ？*/
    if(idx < 0 || idx > size)
        return false;
    /* idx              */
    for(int i=size()-1; i >= idx; i--){
        elements[i+1] = elements[i];
    }
    elements[idx] = ele;
    size++;
    return true;
}

append () 는 insert () 방법 을 재 활용 하여 배열 끝 에 만 삽 입 된 요소 입 니 다.이 방법의 시간 복잡 도 는 상수 로 원소 의 이동 과 관련 이 없다.

public boolean append(int ele){
    return insert(size(), ele);
}

제 공 된 색인 에 따라 대응 하 는 요소 의 값 을 가 져 옵 니 다. 이 는 제 공 된 색인 이 불법 인 경우 와 관련 될 수 있 습 니 다. 이 경우 이 상황 은 이상 을 던 지 는 것 으로 처 리 됩 니 다.색인 에 따라 새로운 요소 값 을 설정 하 는 것 도 유사 하 다.

public int getElementByPos(int idx) throws IllegalArgumentException{
    if(idx < 0 || idx > size())
        throw new IllegalArgumentException("The param idx is illegal.");
    return elements[idx];
}

public void setElementByPos(int idx, int ele) throws IllegalArgumentException{
    if(idx < 0 || idx > size())
        throw new IllegalArgumentException("The param idx is illegal.");
    elements[idx] = ele;
}

배열 의 요 소 를 제거 하 는 시간 복잡 도 역시 선형 으로 증가 했다.요소 가 삭제 되 었 을 때 이 요소 뒤의 모든 요 소 를 한 자리 로 옮 겨 야 할 수도 있 습 니 다. 최 악의 경 우 는 첫 번 째 요 소 를 삭제 하 는 것 입 니 다.

public boolean remove(int idx){
    /*        */
    if(isEmpty())
        return false;
    /*   idx     */
    if(idx<0 || idx>size()-1)
        return false;
    /* idx          */
    for(int i=idx; i<size()-1; i++){
        elements[i] = elements[i+1];
    }
    size--;
    elements[size] = 0; /*              */
    return true;
}

여기에 toString () 방법 을 다시 썼 습 니 다. 배열 요 소 를 인쇄 하 는 것 은 테스트 를 편리 하 게 하기 위해 서 입 니 다.하하하하...

@Override
public String toString() {
    return "ArrayTable [element=" + Arrays.toString(elements) + "] size=" + size;
}

총결산
이 데이터 구조 가 실현 되 는 것 은 매우 간단 하 며, 순 전 히 입문 한 숙련 된 작품 이다.
소스 코드

import java.util.Arrays;

/** *                *              ： * 1.   ; * 2.        ; * 3.          ; * 4.   x      ; * 5.    x     ; * 6.         ; * 7.          ; * 8.          ; * 9.        ; * 10.          . * * PS:          . * @author Bingo * @version 0.1 */
public class SimpleList {
    private int[] elements;
    private int size;

    /** *       */
    private final static int DEFAULT_CAPACITY = 8;

    /** *       ，       64      */
    public SimpleList(){
        clear();
    }

    /** *                 * @param size       */
    public SimpleList(int size){
        size = 0;
        init(size);
    }

    /** *              * @return */
    public int size(){
        return size;
    }

    /** *          * @return     true，    false */
    public boolean isEmpty(){
        return size == 0 ? true : false;
    }

    /** *       * @param capacity        */
    public void init(int capacity){
        elements = new int[capacity];
    }

    /** *         0 */
    public void clear(){
        size = 0;
        init(DEFAULT_CAPACITY);
    }

    /** *         * @return      true，    false */
    public boolean isFull(){
        return size() == elements.length ? true : false;
    }

    /** *    idx      ,  idx   0~size, * idx 0         ,idx size        , *          idx         ,size           . * @param ele        * @param idx       * @return       true，      false */
    public boolean insert(int idx, int ele){
        /*     */
        if(isFull())
            return false;
        /*        pos     ,= =,          ？*/
        if(idx < 0 || idx > size)
            return false;
        /* idx              */
        for(int i=size()-1; i >= idx; i--){
            elements[i+1] = elements[i];
        }
        elements[idx] = ele;
        size++;
        return true;
    }

    /** *          . * @param ele     * @return         true,    false. */
    public boolean append(int ele){
        return insert(size(), ele);
    }

    /** *      idx   ，     0~(size-1). * @param idx      * @return          * @throws IllegalArgumentException  pos            . */
    public int getElementByPos(int idx) throws IllegalArgumentException{
        if(idx < 0 || idx > size())
            throw new IllegalArgumentException("The param idx is illegal.");
        return elements[idx];
    }

    /** *     idx          . * @param ele       * @param idx       * @throws IllegalArgumentException  idx            . */
    public void setElementByPos(int idx, int ele) throws IllegalArgumentException{
        if(idx < 0 || idx > size())
            throw new IllegalArgumentException("The param idx is illegal.");
        elements[idx] = ele;
    }

    /** *        idx   ，idx      0~(size-1). * @param idx      * @return       true，    false */
    public boolean remove(int idx){
        /*        */
        if(isEmpty())
            return false;
        /*   idx     */
        if(idx<0 || idx>size()-1)
            return false;
        /* idx          */
        for(int i=idx; i<size()-1; i++){
            elements[i] = elements[i+1];
        }
        size--;
        elements[size] = 0; /*              */
        return true;
    }

    @Override
    public String toString() {
        return "ArrayTable [element=" + Arrays.toString(elements) + "] size=" + size;
    }

}