단일 체인 시트 작성 (자바 언어 설명)

체인 테이블
데이터 구조의 논 리 는 4 가지 유형 을 나타 낸다. (1) 집합: 요소 간 무관 (2) 선형: 요소 간 1 - > 1 의 관계 (3) 트 리: 요소 간 1 - > many 의 관계 (4) 그림: 요소 간 many - > many 의 관계
가장 기본 적 인 선형 구조의 간단 한 논 리 는 선형 표 라 고 불 리 며 선형 표 의 물리 구 조 는 보통 순서 표 와 링크 두 가지 가 있다.순서 표 의 기본 적 인 실현 은 지난 블 로그 에서 간단 한 링크 를 썼 다.
선형 표 인터페이스

public interface ListInterface<T> {
    
    /**
     *      
     */
    void printList();

    /**
     *        
     * @return
     */
    int length();

    /**
     *     
     * @param element
     * @return
     */
    int locate(T element);

    /**
     *     
     * @param i
     * @return
     * @throws ListException
     */
    T getElement(int i) throws ListException;

    /**
     *          
     * @param i
     * @param element
     * @throws ListException
     */
    void insert(int i, T element) throws ListException;

    /**
     *          
     * @param i
     * @return
     * @throws ListException
     */
    T delete(int i) throws ListException;

    /**
     *     
     * @return
     */
    boolean isEmpty();

}

이상 류

public class ListException extends RuntimeException {

    private static final long serialVersionUID = 1L;

    public ListException() {}

    public ListException(String message) {
        super(message);
    }

}

링크 노드 정의

public class LinkedNode<T> {
    
    private T data;
    
    private LinkedNode<T> next;
    
    public LinkedNode() {
        this.data = null;
        this.next = null;
    }
    
    public LinkedNode(T element) {
        this.data = element;
        this.next = null;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public LinkedNode<T> getNext() {
        return next;
    }

    public void setNext(LinkedNode<T> next) {
        this.next = next;
    }

}

첨삭 의 편 의 를 위해 서 우 리 는 두 결점 을 정의 했다.두 결점 은 체인 테이블 이 가지 고 있 고 뒤의 각 결점 간 의 연결 은 지침 (인용) 을 통 해 진행 되 며 각 결점 은 다음 결점 의 인용 을 가지 고 있다.
단일 체인 테이블 프로 그래 밍 실현

public class LinkedList<T> implements ListInterface<T> {
    
    private LinkedNode<T> first;
    
    public LinkedList() {
        first = new LinkedNode<T>();
    }
    
    //   
//    public LinkedList(T[] init) {
//        first = new LinkedNode();
//        for (int i = 0; i < init.length; i++) {
//            LinkedNode node = new LinkedNode<>(init[i]);
//            node.setNext(first.getNext());
//            first.setNext(node);
//        }
//    }
    
    //   
    public LinkedList(T[] init) {
        first = new LinkedNode<T>();
        LinkedNode<T> rear = first;
        for (int i = 0; i < init.length; i++) {
            LinkedNode<T> node = new LinkedNode<>(init[i]);
            rear.setNext(node);
            rear = node;
        }
    }

    @Override
    public void printList() {
        LinkedNode<T> p = first.getNext();
        while(p != null) {
            System.out.println(p.getData() + " ");
            p = p.getNext();
        }
    }

    @Override
    public int length() {
        int length = 0;
        LinkedNode<T> p = first.getNext();
        while(p != null) {
            p = p.getNext();
            length++;
        }
        return length;
    }

    @Override
    public int locate(T element) {
        LinkedNode<T> p = first.getNext();
        int count = 1;
        if (element == null) {
            while (p != null) {
                if (p.getData() == null) {
                    return count;
                }
                p = p.getNext();
                count++;
            }
        } else {
            while (p != null) {
                if (p.getData().equals(element)) {
                    return count;
                }
                p = p.getNext();
                count++;
            }
        }
        return 0;
    }

    @Override
    public T getElement(int i) throws ListException {
        LinkedNode<T> p = first.getNext();
        int count = 1;
        while (p != null && count < i) {
            p = p.getNext();
            count++;
        }
        if (p == null) {
            throw new ListException("      ");
        }
        return p.getData();
    }

    @Override
    public void insert(int i, T element) throws ListException {
        LinkedNode<T> p = first;
        int count = 1;
        while (p != null && count < i) {
            p = p.getNext();
            count++;
        }
        if (p == null) {
            throw new ListException("      ");
        }
        LinkedNode<T> node = new LinkedNode<>(element);
        node.setNext(p.getNext());
        p.setNext(node);
    }

    @Override
    public T delete(int i) throws ListException {
        LinkedNode<T> p = first.getNext();
        int count = 1;
        while (p != null && count < i-1) {
            p = p.getNext();
            count++;
        }
        if (p == null || p.getNext() == null) {
            throw new ListException("      ");
        }
        LinkedNode<T> q = p.getNext();
        T deleteNode = q.getData();
        p.setNext(q.getNext());
        return deleteNode;
    }

    @Override
    public boolean isEmpty() {
        if (first.getNext() == null) {
            return true;
        }
        return false;
    }

}

머리 삽입 법 과 꼬리 삽입 법 은 배열 매개 변수 구조 기 를 실현 하 는 서로 다른 실현 방법 으로 충돌 하기 때문에 설명 되 었 다.
테스트

public class ListTester {
    
    public static void main(String[] args) {
        String[] initialList = {"a", "b", "c", "d", "e", "f"};
        ListInterface<String> list = new LinkedList<>(initialList);
        System.out.println("     " + list.length());
        System.out.println("         ：");
        list.printList();
        String list_2 = list.getElement(2);
        System.out.println("2    ：" + list_2);
        int locate_d = list.locate("d");
        System.out.println("  d     ：" + locate_d);
        System.out.println("   3   k");
        list.insert(3, "k");
        String list_3 = list.getElement(3);
        System.out.println("3    ：" + list_3);
        System.out.println("     ：" + list.length());
        System.out.println("         ：");
        list.printList();
        System.out.println("    3   ");
        String deleteElement = list.delete(3);
        System.out.println("        ：" + deleteElement);
        System.out.println("     ：" + list.length());
        System.out.println("         ：");
        list.printList();
    }

}

테스트 결과

     6
         ：
a 
b 
c 
d 
e 
f 
2    ：b
  d     ：4
   3   k
3    ：k
     ：7
         ：
a 
b 
k 
c 
d 
e 
f 
    3   
        ：k
     ：6
         ：
a 
b 
c 
d 
e 
f 

이렇게 해서 간단 한 단일 체인 표 는 체인 표 의 구체 적 인 지식 과 모든 방법 에 대한 상세 한 분석 을 완성 했다. 여기 서 일일이 설명 하지 않 는 다.